作为计算机科学与技术领域最基础、最原始的问题之一,装箱问题的研究已延续四十年之久,许多关键结果相继涌现,一些隶属于计算机科学以及组合优化学科内的重大理论均起源于对装箱问题的研究,由此可见对装箱问题的研究意义深远。此外,装箱问题在实际生活中应用极其广泛,不论是计算机科学领域中的多处理器任务调度、负载均衡,还是工业制造领域中的切割存储和卡车装载都是装箱问题的具体例子。近年来,基于受限空间的在线装箱问题以及带建议的在线装箱问题成为在线装箱问题的两个研究热点,其中只打开两个箱子的二维在线装箱问题的最好的结果是Januszewski提出的近似度为3.8的算法,而带建议的一维在线装箱问题,到目前为止结果最好的是由Boyar等人提出的算法,其近似度达到了4/3。本论文主要针对这两个结果分别进行了改进和相应的扩展研究,具体工作如下：1.对于只开两个箱子的正方形在线装箱问题,基于Januszewski提出的在箱子划分块的思想,通过继续划分放大物体的混合箱子,使之包括一种新类型的块,从而达到只放小物体的简单箱子中划分出的块占用率提高的目的,另外采用将一部分小物体与大物体混合装入复杂箱子的方法,弥补混合箱子的空闲空间。最终使得打开的两种类型的箱子的占用率都得到提高。通过分析得出,本文提出的只开两个箱子的正方形在线装箱算法的近似度为3.63556。2.将正方形块划分的思想扩展到只开两个箱子的立方体在线装箱和超级立方体在线装箱问题上,通过不同维度的块划分技巧,分别提出一个近似度为5.43的立方体在线装箱算法和一个近似度为32/21·2d的超级立方体在线装箱算法,在只开两个箱子的在线多维立方体装箱问题上,这两个结果均为这类问题的首次的研究结果。3.对于带建议的在线装箱问题,本文通过细化物体分类,增加物体组合拼装的种类,以及设定最少数目的建议位来表示对应的组合物体类型,最终将一维带建议的在线装箱问题的近似算法的结果改进为5/4。对于最少要用到的建议位数目问题,通过构建一类特定形式的到来物体序列,本文分析出最少需要的建议位数为(n-3OPT) log OPT来达到最优装箱效果。4.将相应的思想扩展到二维的带建议的在线装箱问题上,分别提出了近似度为2的正方形在线装箱算法和近似度为2.25的可旋转长方形在线装箱算法,这两个结果不仅是这类问题的首次研究,而且均比目前最好的不带建议位的同类问题的结果要好。5.本论文研究了二维正方形在线装箱的并行化问题,提出了一个SIMD模型,并分析出基于此模型的并行装箱算法的近似度为9/4,时间复杂度为θ(n)。