二维一刀切装箱问题,指在给定无限多个固定大小的二维板材(箱子)上,将不同规格的待排矩形件,在保证彼此不重叠的前提下,逐个摆放至二维箱子内,使得占用箱子的个数最少,并且在切割时满足一刀切条件约束(此处的一刀切约束是指切割时刀口走线不能弯曲,必须从一条边经直线切割到对边)。二维一刀切装箱问题隶属于组合优化问题中的二维布局问题,最典型的应用是在家具生产过程中玻璃切割的布局优化。从计算复杂性理论的角度来看,该问题属于具有最高计算复杂性的NP完全问题,并涉及到计算几何、运筹学等多学科知识,具有较高的理论研究和实用价值。本文对二维一刀切装箱过程中的相关问题进行了深入研究,主要的研究工作如下:1、首次给出G-区域和GR-区域的概念,用以定量描述排样过程中可被一刀切的区域所需要满足的相关条件。2、提出了顺时针切割线组以及逆时针切割线组等定义。在使用三叉排样树对布局结构进行描述的基础上,相继构造了G-区域的判断算法、GR-区域的延展算法及全局更新算法等子算法。3、在上述工作的基础上,提出了二维一刀切装箱问题的启发式算法,并对其进行了数值实验和结果分析。4、利用所提算法,编制了可被实用的排样软件,并在其中考虑了切割线宽度及边角磨损等实际工业生产过程中的相关因素。数值实验结果表明,相对于传统的二维一刀切装箱算法而言,本文所提概念和相关算法可以更有效地、快速的获取相应的排样布局结果。