第41卷第9期 Vol. 41No. 9
假压技木
FORGING & STAMPING TECHNOLOGY
约束二维排样问题的一种求解算法
朱
强，薛
峰，郑仕勇2，管卫利3
2016年9月 Sep-2016
（1.中原工学院信息商务学院，河南郑州450007；2.贺州学院计算机科学与信息工程学院，广西贺州452899；
3.南宁学院信息工程学院，广西南宁530200）
摘要：讨论有约束二维切制排样间题，即将板材切剂成若干种矩形毛坏，其中每种毛坏的数量有上界约束，优化目标以使板材所切制的毛坏总价值（排样价值）最大。采用五块排样方式简化切制工艺，将板材切割成五块，每块切制成所需毛坏。构造一种基于隐式枚举和分支定界思想的算法生成五块排样方式：（1）计算所有可能尺寸的块的排样价值；（2）选择排样价值
最大的五块组合生成五块排样方式；（3）：
采用文献中的基准测题，
验证文中的有约束五块排样算法。研究结果表明，文中算
法平均排样价值比文献中的3种算法分别高出12.85%，4.52%和1.89%，」
且算法计算时间较短。
关键词：有约束排样间题；排样算法：
隐式枚举；矩形毛；五块排样方式
DOI: 10. 13330/j. issn. 1000-3940. 2016. 09, 028
中图分类号：TP391
文献标识码：A
文章编号：1000-3940（2016）09-0148-05
Analgorithmof theconstrainedtwo-dimensionalnesting
Zhu Qiang', Xue Feng', Zheng Shiyong’, Guan Weili?
(1. College of Information & Beusiness, Zhongyuan University of Texchnology, Zhengzhou 450007, China; 2. Computer and Electroric Information College , Hezhou University , Hezhou 542899, China; 3. Infomation Engineering College, Nanning University, Nanning 530200, China) Abstract : The constrained two-dimensional nesting problem was discussed, and the total value of the blank was in the maximum when one blank was cut to meet upper bound and optimization objective. The cutting process was simplified by five-block pattem. The blank was cut into five-blocks, and then each block was cut into the required blanks. An algorithm based on implicit enumeration and branch bound al-gorithm was constructed to generate five-block pattem. Finstly, the nesting valses of all possible size blocks were calculated, and then the five-block combination which had the maximal value was chosen to generate five-block pattem. Finally, the five-block pattem algorithm with constrain was tested by the benchmark problems of the literature. The research results show that the average value of the proposed al-gorithm is higher than those of the literature about 12. 85% , 4. 52% , 1. 89% respectively, and the computation time is shorter.
Key words : two-dimensional nesting problem with constrain; nesting algorithm; implicit enumeration; rectangular blanks; five block nesting pattem
下料问题广泛出现在机械制造业领域，通过计算机辅助设计技术进行下料能够节省板材消耗，降低生产成本，提高企业竞争力[1-3]。本文讨论有约束二维切制排样间题[4)）（Constrained two-dimen-sional cuttingproblem，CTDC）：将板材LW切割成 m种毛坏，第i种毛坏的尺寸为l③w、价值为、数量上界为d。设排样方式P包含z；个第i种毛坏，
收稿日期：20160113；修订日期：20160720
基金项目：广西自热科学基金资助项目（2015GXNFBA139264）；贺州市科技开发项目（贺科能1506006）
作者筒介：朱强（1985-），男，颈士，讲师 E-mail: networkerazy@ 163. cm
通讯作者：郑仕勇（1983-），男，额士，高级工程师 E-mail; plgh2361@ 163. com
S为排样价值，N为自然数集。CTDC问题的数学模
型为：

1。.t.P为一个合理的排样方式 2, e N nz, ≤d,i e M
与CTDC密切相关的是二维下料问题
(1)(Two di-
mensional cutting stock problem, TDCS),
即用板材切
制出若干种毛坏，在每种毛坏需求量6，得到满足的前提下使所用板材张数最少。下料问题的解是由一组排样方式按照一定数量组合而成。经常采用顺序启发式（SHP）与CTDC算法相结合来求解 TDCS[5]。其求解步骤为：
Stepl：初始化各种毛坏的剩余需求量d，为原始