装箱问题简单地说就是按一定规则将若干物体互不重叠地放入有一定容量的容器中,并达到某种最佳目标的问题。装箱问题无处不在,被广泛地应用于计算机科学、工业领域和管理科学,如多处理器任务调度、内存管理、集成电路设计、货物装载、材料切割、新闻排版等都可以形式化为一个装箱问题。由于装箱问题的广泛应用,早在二十世纪七十年代它就得到了学术界的广泛而深入的研究。装箱问题已经成为计算机科学和组合优化领域的一个重要问题。由于装箱问题是一个NP完全问题,具有高度复杂性,对于规模较大的装箱问题,精确算法无法在合理的时间内求得满意的解,因此,目前研究得最多的是该问题的启发式算法。　　 本文首先对装箱问题的研究现状及已有算法进行了阐述和分析,重点研究了二维矩形装箱问题；在BF算法和PH算法的基础上设计了一个新的启发式算法一砌墙式BF(BBF)算法。BBF算法与BF算法类似,在装箱前对待装矩形进行了旋转和排序,在装箱过程中每次选择最低的可行位置、选择“最合适”的矩形进行填充；不同的是,BBF算法引入了PH算法中设置“基准砖”、空间动态分层的策略。应当指出,这里“基准砖”的设置与PH算法不同。在BBF算法的基础上我们提出了基于SWO(“Squeaky Wheel”Optimization)方法的启发式算法-SBBF算法。SBBF算法按BBF的矩形放置策略放置矩形；根据每一次装箱的结果,对影响装箱效果的矩形设置惩罚度,惩罚度高的矩形在下一次装箱时优先装入。借助于SWO方法的全局优化能力,SBBF算法能够改进BBF算法的装箱效果。实验表明,我们提出的两种算法比原有的BF算法和PH算法有了很大的改进。而且SBBF算法对多组实验实例获得了最优解,其余实例的解与最优解相当接近,胜过了当前大多数的启发式算法和现代启发式算法,在效率和解的质量上可以与SPGAL算法和HRBB算法相媲美。