装箱问题是经典的组合优化问题之一,它作为一种最早研究的NP-难解问题和复杂性理论的研究平台,为其它NP-难解问题的研究提供了诸多借鉴。装箱问题在多处理器调度、资源分配和日常生活中的计划、包装、调度等各领域有着广泛的应用背景。装箱问题已经有五十多年的研究历史,在此期间,许多著名的组合优化领域的学者,如：E. G. Coffman, D. S. Johnson以及图灵奖获得者A. C. Yao等为装箱问题创建了比较完善的理论和丰富的算法。目前,对于装箱问题及其算法的研究仍然是组合最优化领域的重要问题之一,具有广阔的研究空间。按照Coffman等人的总结,装箱问题的启发式算法研究可以分成三个方面：提出有效的近似算法并分析算法的性能；确定算法的性能界限；考虑与实际应用关系更紧密的、带各类约束的装箱问题。本文遵循该思路进行了研究,其主要内容如下：对于一维装箱问题提出一种带缓冲箱的启发式算法,通过对Benchmark问题的求解,对所提算法与其他经典算法的性能进行了对比分析；对所提算法进行了时间及空间复杂性分析和最坏性能比分析。分析该算法自身参数对性能的影响。关于带约束装箱问题的研究：本文根据实际应用需要,提出了一种工件分批到达的装箱问题,同时给出了该问题一个基于动态规划的近似算法,分析该算法的时间及空间复杂度,最坏性能比。最后,总结了本文的工作并展望了进一步的研究方向。