潘卫平¹, 樊治平¹, 黄敏^2,3
1. 东北大学 工商管理学院, 辽宁 沈阳 110169;
2. 东北大学 信息科学与工程学院, 辽宁 沈阳 110819;
3. 东北大学 流程工业综合自动化国家重点实验室，辽宁 沈阳 110819
收稿日期：2020-11-17
基金项目：国家自然科学基金资助项目(71871049)；国家自然科学基金重点国际合作研究项目(71620107003)；辽宁省“兴辽英才计划”项目(XLYC1802115)；流程工业综合自动化国家重点实验室基础科研业务费资助项目(2013ZCX11)；东北大学博士后基金资助项目(01270012810165)；中央高校基本科研业务费专项资金资助项目(N2106008)。
作者简介：潘卫平(1989-)，男，湖北黄冈人，东北大学博士后研究人员;
樊治平(1961-)，男，江苏镇江人，东北大学教授，博士生导师;
黄敏(1968-)，女，福建长乐人，东北大学教授，博士生导师。

摘要：针对二维板材圆形件剪冲下料问题, 提出一种基于四块排样方式的下料算法.这种排样方式将一张板材划分成四个块, 在每块中排放具有相同长度和方向的条带; 条带中排放若干行同种圆形件.构造排样算法生成单张板材上圆形件的四块排样方式, 首先确定圆形件在条带中的布局; 然后构造递归算法生成条带在块中的布局; 最后采用隐式枚举算法确定板材的最优四块划分.采用列生成算法调用上述排样方法生成多个不同的排样方式, 按照单纯型原理择优选择一组排样方式形成下料方案, 并对小数解进行圆整操作.使用文献例题和实际生产实例将本文算法与文献算法进行对比, 结果表明: 本文算法下料方案板材利用率比四种文献算法分别高0.49%, 0.32%, 6.04%和1.50%, 计算时间能满足实际应用需要.
关键词：剪冲排样四块排样算法递归算法列生成算法板材圆形件
Four-Block Layout Algorithm for Two-Dimensional Plate Shearring and Punching of Circular Parts
PAN Wei-ping¹, FAN Zhi-ping¹, HUANG Min^2,3
1. School of Business Administration, Northeastern University, Shenyang 110169, China;
2. School of Information Science & Engineering, Northeastern University, Shenyang 110819, China;
3. State Key Laboratory of Synthetical Automation for Process Industries, Northeaastern University, Shenyang 110819, China
Corresponding author: PAN Wei-ping, E-mail: panweiping@mail.neu.edu.cn.

Abstract: A cutting stock algorithm based on four-block layout was proposed to solve the two-dimensional plate shearring and punching of circular parts. With this layout, a sheet was divided into four blocks. Only the strips with the same direction and length were arranged in each block, and several rows of the same circular parts were arranged in the strips. A four block layout method for generating circular parts on a single sheet by constructing a layout algorithm. Firstly, the layout of circular parts in the strips was determined. Secondly, recursive algorithm was constructed to generate the layout of the strips in blocks. Finally, implicit enumeration algorithm was used to determine the optimal four-block partition. The column generation algorithm was used to call the above layout algorithm to generate a number of different layouts. Based on the simplex principle, a group of layouts were selected to form the cutting plan, and the decimal solution was rounded. The results showed that the plate utilization ratio of the algorithm in the study is 0.49%, 0.32%, 6.04% and 1.50% higher than those of the four literature algorithms, respectively, and the calculation time can meet the needs of practical applications.
Key words: shearring and punching layoutfour-block layout algorithmrecursive algorithmcolumn generation algorithmplatecircular part
制造业每年消耗大量硅钢板材来生产电动机的定子和转子.对于一个普通的电动机制造企业, 一年可能消耗几千吨硅钢板材^[1].优化下料方案对提高板材利用率具有重要意义^[2-4].一般而言, 定子和转子属于圆形件，经常使用剪冲工艺将这些圆形件从硅钢板材上切割下来.剪冲工艺包括剪切和冲压两个阶段, 在剪切阶段用剪床将板材剪成条带; 在冲压阶段用冲床将条带冲出圆形件.由于设备的限制, 冲压工艺要求条带中圆形件按行排放, 且只排放一种圆形件^[5-6].
本文讨论圆形件二维板材剪冲下料问题: 采用剪冲工艺将原料板材切割出若干种已知尺寸和数量的圆形件, 在满足圆形件的需求量前提下使得消耗的板材总面积最小.
针对二维板材剪切下料问题, 目前多数文献研究的是零件为矩形的情形^[7-10], 对零件为圆形的情形研究相对较少.对零件为圆形的情形, 文献[1]提出了应用T型排样方式的下料方案, 这种排样方式将板材分成两个段, 一个段中排放水平条带, 另一个段中排放竖直条带.构造背包算法生成条带在段上的布局方式, 按照板材排样价值最大原则确定板材的两段划分.采用列生成算法调用上述排样方法择优选择一组排样方式构成下料方案.文献[2]提出了应用直切排样方式的顺序启发式算法.文献[4]提出了一种基于四块排样方式的求解算法, 这种排样方式将板材分成四个块, 块中排放方向和长度均相同的条带.采用动态规划生成条带在块中的布局方式, 采用穷举法确定板材的最优四块划分.最后将上述排样算法与列生成相结合求解下料方案.上述文献下料算法的板材利用率和计算速度有待进一步提高.文献[11]将四块排样方式和顺序价值修正启发式相结合, 提出了启发式排样算法.
本文提出一种新的基于四块排样方式的下料算法, 采用递归技术确定圆形件在单张板材上的排样方式, 同时运用隐式枚举剔除不必要的分支; 采用列生成算法调用该排样算法生成下料方案, 对小数解进行圆整操作得到更加精确的下料方案.采用文献例题和实际生产实例测试本文算法, 并与文献算法进行对比, 验证本文算法的有效性.
本文的创新点主要有: ①构造了四块排样方式的递归生成算法；②提出了规范尺寸概念, 在排样时候只需考察规范尺寸的块, 可大幅提高排样算法的计算速度；③在生成下料方案时对下料方案的小数解进行了圆整操作, 可进一步减少板材使用量.
1 问题描述和四块排样方式1.1 问题描述和模型二维板材圆形件剪冲下料问题: 用剪冲工艺将尺寸为L×W(L为长, W为宽)的板材剪冲出m种圆形件, 其中第i种圆形件的直径为d_i, 需求量为r_i, i=1, …, m; 问题目标为在满足所有圆形件的需求量前提下使得消耗的板材总面积最小.
令A为下料方案耗费的板材总面积; 下料方案包含α种排样方式; Q=[q₁, …, q_α], 其中q_j为第j个排样方式对应的板材的面积; P为m行α列矩阵, 其中元素p_ij表示第j种排样方式包含第i种圆形件的个数; R=[r₁, …, r_m]^T为圆形件的需求量向量, 元素r_i表示第i种圆形件的需求量; X=[x₁, …, x_α]^T, 其中x_j表示按照第j种排样方式切割的板材张数; N为正整数集合.则该问题的数学模型为

(1)

模型(1)优化目标为下料方案切割的板材总面积最小.
1.2 条带条带中排放一行或多行同种圆形件^[1].图 1给出了冲压阶段所需的条带的几何特征, 其中D为圆形件的直径, g为冲压余量.连接三个相邻的圆形件的圆心组成一个等边三角形, 其边长为D+g.本文不妨令g=0, 这不影响本文算法的通用性, 如果g>0, 可以在排样时将圆形件的直径设为D+g, 不影响排样方式的质量.
图 1(Fig. 1)

图 1 条带几何特征Fig.1 Geometric features of strips (a)—包含一行圆形件的条带；(b)—包含多行圆形件的条带.

设第i种圆形件的直径为d_i, 价值为c_i, 在条带中最大允许排放的行数为e_i, 其中i=1, …, m.于是第i种圆形件对应的条带的宽度有e_i种.第k种条带包含k行圆形件, 其宽度为「d_i[1+(k-1)sin(π/3)], 这里“「”为向上取整数符号, k=1, …, e_i.设条带长度为x, 则根据条带的几何性质可得^[12]: 当k为奇数时, 第k种条带的价值; 当k为偶数时, 第k种条带的价值; 其中n₁=分别为奇数行和偶数行中圆形件的个数, 这里“」”为向下取整数符号.令条带宽度向量为S=[s₁, …, s_M], 其中.设v(x, s_j)为条带x×s_j(长度为x, 宽度为s_j)中包含的圆形件的价值, 其中j=1, …, M.
1.3 块块中排放一组具有相同方向和长度的条带.称排放水平条带的块为X向块, 排放竖直条带的块为Y向块.
块的价值为块中排放的条带的价值之和.设f(x, y)为块x×y(长为x, 宽为y)的价值, 其中x≤L, y≤W.当块为X向块时, 设其价值为f_X(x, y); 当块为Y向块时, 设其价值为f_Y(x, y).通过如下递归模型^[13-15]计算块的价值.

(2)

(3)

(4)

1.4 四块方式四块排样方式由四个矩形块组成^[18], 每个块中排放具有相同长度和方向的条带, 每根条带中按行排放一种圆形件.剪冲过程: 首先用剪床将板材剪成四个块, 然后将块剪成条带, 最后用冲床将条带冲压出所需要的圆形件.四块划分过程：首先用一条父分界线将板材划分为2个子板, 然后用两条垂直于父分界线的子分界线将2个子板划分为4个块.如图 2所示, 当父分界线为竖直方向时, 称这种四块方式为X向四块方式; 当父分界线为水平方向时, 称这种四块方式为Y向四块方式.
图 2(Fig. 2)

图 2 板材的四块划分Fig.2 Four block division of a plate (a)—X向四块方式；(b)—Y向四块方式.

设V为四块排样方式的价值, V_X和V_Y分别为X向四块排样方式和Y向四块排样方式的价值.则有

(5)

(6)

(7)

式(5)、式(6)通过枚举父分界线和子分界线的位置, 得到所有可能的四块组合, 选择排样价值最大的一个作为最优四块方式.选择X向四块方式和Y向四块方式价值较大者作为最终的四块排样方式.式(5)中x为父分界线位置, y₁和y₂分别为两条子分界线的位置, 如图 2a所示.同理, 式(6)中y为父分界线位置, x₁和x₂分别为两条子分界线的位置, 如图 2b所示.
2 递归和隐式枚举排样算法2.1 规范尺寸对于包含第i种圆形件长度为x, 宽度为s_j的条带, 如果v(x, s_j)>v(x-1, s_j), 则称x为该条带的规范长度.如果条带只包含一行圆形件, 则条带的规范长度为qd_i, 其中0 ≤ q ≤max(L, W)/d_i」.如果条带中包含的圆形件行数不止一行, 则条带的规范长度为qd_i和「(q+0.5)d_i, 其中「(q+0.5)d_i≤max(L, W).称具有规范长度的条带为规范条带.
令H={h₁, …, h_β}为所有条带的宽度和规范长度集合, 其中β为集合的元素个数.令A为块的规范长度集合, B为块的规范宽度集合, n_i为非负整数, 其中i=1, …, β.定义A和B:

(8)

(9)

即块的规范长度为条带的宽度和条带的规范长度的线性组合加上0, L两个元素.块的规范宽度为条带的宽度和条带的规范长度的线性组合加上0, W两个元素.将规范尺寸按照升序排列, 即A={a₁, …, a_|A|}, B={b₁, …, b_|B|}, 其中|A|为集合A的元素个数, |B|为集合B的元素个数, 0=a₁ < … < a_|A|=L, 0=b₁ < … < b_|B|=W.令A(x)为不大于x的最大规范长度, B(y)为不大于y的最大规范宽度.规范尺寸具有如下性质: 对于任意尺寸的块x×y(0 ≤ x ≤L, 0 ≤ y ≤ W), 其价值等于其对应的规范尺寸块的价值, 即f(x, y)=f(A(x), B(y)).
由于对称性, 在生成X向四块排样方式过程中, 父分界线的位置x只需从0隐式枚举到「L/2 , 子分界线位置y₁和y₂只需从0隐式枚举到「W/2 .记a_r为板材规范长度集合的枢纽元素, b_t为板材规范宽度集合的枢纽元素, 它们满足如下条件: a_r>「L/2 且a_r-1 < 「L/2 , 其中1 < r < |A|; b_t>「W/2 且, 其中1 < t < |B|.
2.2 块生成算法X向块包含具有相同长度和方向的水平条带, Y向块包含具有相同长度和方向的竖直条带.块生成算法确定块中条带的优化布局, 得到价值最大的块, 即最优块.生成最优块的算法步骤:
步骤1 ??令i=0.
步骤2 ??令x=a_i.采用递归模型(2), 一次性求出所有长度等于x的X向块的价值f_X(x, y), 其中y∈B.
步骤3 ??令i=i+1.如果i≤|A|, 则转步骤2.
步骤4 ??令j=0.
步骤5 ??令y=b_j.采用递归模型(3), 一次性求出所有宽度等于y的Y向块的价值f_Y(x, y), 其中x∈A.
步骤6 ??令j=j+1.如果j≤|B|, 则转步骤5.
步骤7 ??令i=0.
步骤8 ??令j=0.
步骤9 ??令x=a_i, y=b_j.如果f_X(x, y)>f_Y(x, y), 则令f(x, y)=f_X(x, y), 否则令f(x, y)=f_Y(x, y).
步骤10 ??令j=j+1.如果j≤|B|, 则转步骤9.
步骤11 ??令i=i+1.如果i≤|A|, 则转步骤8.
步骤12 ??输出所有尺寸的最优块的价值f(x, y), 其中x∈A, y∈B.
算法的终止条件为j=|B|+1且i=|A|+1.步骤1~步骤3求出所有尺寸的X向块的价值; 步骤4~步骤6求出所有尺寸的Y向块的价值; 步骤7~步骤11, 比较相同尺寸的X向块和Y向块的价值, 选择价值较大者作为最优块.
2.3 四块方式生成算法本节仅考虑X向四块方式的生成; 对于Y向四块方式, 可将板材的长度和宽度对换, 变成X向四块方式进行处理.生成最优X向四块方式的算法步骤如下:
步骤1 ??令V_X=0, V₁=0, V₂=0.
步骤2 ??令i=0.
步骤3 ??令x=a_i.
步骤4 ??令j₁=0.
步骤5 ??令y₁=b_j1.令U₁=f(x, B(W-y₁))+f(x, y₁), 如果V₁ < U₁, 则令V₁=U₁.
步骤6 ??令j₁=j₁+1, 如果j₁≤t, 则转步骤5.
步骤7 ??令j₂=0.
步骤8 ??令y₂=b_j2.令U₂=f(A(L-x), B(W-y₂))+f(A(L-x), y₂), 如果V₂ < U₂, 则令V₂=U₂.
步骤9 ??令j₂=j₂+1, 如果j₂≤t, 则转步骤8.
步骤10 ??令U_X=V₁+V₂, 如果V_X < U_X, 则令V_X=U_X.
步骤11 ??令i=i+1, 如果i≤r, 则转步骤3.
步骤12 ??输出X向四块方式的价值V_X.
算法的终止条件为i=r+1.
2.4 四块排样方式生成算法本文排样算法, 首先得到条带的规范长度和宽度以及条带的价值, 然后得到块的规范尺寸并确定条带在块中的优化布局, 最后确定板材的最优四块划分.算法步骤:
步骤1 ??根据2.1节求出条带的规范长度.
步骤2 ??根据1.2节得到条带的宽度集合S={s₁, …, s_M}, 求出所有规范条带x×s_i的价值v(x, s_i), 其中x=0, …, max(L, W), 1 ≤ i ≤ M.
步骤3 ??根据2.1节得到块的规范长度集合A和规范宽度集合B.
步骤4 ??调用X向四块方式生成算法生成最优X向四块方式, 并得到其价值V_X.
步骤5 ??调用Y向四块方式生成算法生成最优Y向四块方式, 并得到其价值V_Y.
步骤6 ??选择X向四块方式和Y向四块方式中的价值较大者作为最优四块排样方式, 并得到其价值V=max(V_X, V_Y).
步骤1至步骤3时间复杂度为O(m(|A|+|B|)), 空间复杂度为O(|A|+|B|); 步骤4至步骤5时间复杂度为O(m|A‖B|), 空间复杂度为O(|A‖B|); 步骤6时间复杂度为O(|A‖B|), 空间复杂度为O(1).故算法总的时间复杂度为O(m|A‖B|), 空间复杂度为O(|A‖B|).
3 列生成下料算法上节排样算法可与列生成算法相结合构成下料算法^[8-10].本文下料问题的线性规划模型为

(10)

模型(10)中, Z为下料方案耗费的板材总面积; Q=[q₁, …, q_m], 其中q_j为第j个排样方式对应的板材的面积; U为m行m列矩阵, 其中元素u_ij表示第j种排样方式包含第i种圆形件的个数; R=[r₁, …, r_m]^T为圆形件的需求量向量, 元素r_i表示第i种圆形件的需求量; X=[x₁, …, x_m]^T, 其中x_j表示按照第j种排样方式切割的板材张数.
采用如下步骤求解上述模型.
步骤1 ??确定初始可行解.令矩阵U为单位矩阵, 则初始可行解X=R, 即第j(j=1, …, m)种排样方式只包含一个第j种圆形件, 不包含其他圆形件.
步骤2 ??计算圆形件的当前价值向量.令V=QU^-1=[v₁, …, v_m]为圆形件的当前价值向量.
步骤3 ??寻找能改善目标函数的下料方案.用P=[p₁, …, p_m]^T表征当前考察的排样方式, 其中元素p_i表示排样方式P中包含圆形件i的个数.设排样方式P对应的板材的面积为q.由线性规划理论可知, 如果q-VP < 0, 则当前排样方式P能改善下料方案(P可通过2.4节排样算法求得), 用P替换矩阵A的第k(k由单纯型法确定)列, 令q_k=q, 转步骤2.否则, 不存在能改善模型(10)目标函数的排样方式, 当前下料方案即为最优下料方案, 按照每种排样方式切割的板材张数向量为X=[x₁, …, x_m]^T=U^-1R.
步骤4 ??令x_i=「x_i, i=1, …, m.
步骤5 ??令i=1.
步骤6 ??令x_i=x_i」, 如果UX < R, 则令x_i=x_i+1.
步骤7 ??令i=i+1, 如果i≤m, 则转步骤6.
步骤8 ??得到整数解X.
算法的终止条件为i=m+1.步骤1~步骤3得到的下料问题的解为小数解, 即按照每种排样方式切割的板材张数可能为小数不满足实际生产要求.步骤4~步骤8对小数解进行圆整操作, 得到整数解.
4 实验结果用C#实现本文算法, 实验所用计算机为CPU主频2.4 GHz, 内存4 GB.通过文献随机例题和实际生产实例将本文算法与4种文献算法进行对比.
4.1 随机例题测试采用文献[1]的20道随机例题.板材尺寸为2 000 mm×1 000 mm, 剪冲工艺的冲压余量为8 mm, 每根条带中最多允许排放3行圆形件.文献[1]算法和文献[4]算法平均每道例题耗费的计算时间分别为0.73 s和0.96 s.本文算法平均每道例题耗时0.31 s.文献[1]算法、文献[4]算法和本文算法下料方案的平均板材利用率分别为71.73%, 71.90%和72.22%.本文算法下料方案板材利用率比文献[1]算法和文献[4]算法分别高0.49%和0.32%.
4.2 实例1采用文献[11]的电机制造厂实例, 板材尺寸为3 000 mm×1 500 mm, 圆形件为8种, 剪冲工艺余量为6 mm, 每根条带中最多允许排放3行圆形件, 每种圆形件的尺寸在区间[253 mm, 403 mm]取值, 需求量(单位: 个)在区间[1 000, 2 600]取值, 具体可参见文献[11]的表 2.文献[2]算法、文献[11]算法和本文算法的下料方案板材利用率分别为69.62%, 74.16%和75.66%.可见本文算法比文献[2]算法和文献[11]算法分别高6.04%和1.50%.
4.3 实例2某电动机厂需要用尺寸为2 440 mm×1 220 mm的板材剪冲出15种圆形件, 冲压工艺余量为0, 每根条带中最多允许排放3行圆形件.圆形件的直径(单位: mm)分别为: 180, 205, 226, 260, 280, 320, 342, 360, 375, 390, 400, 420, 440, 455, 485;圆形件的需求量(单位：个)分别为: 50 000, 10 000, 11 000, 7 000, 20 000, 45 000, 30 000, 8 000, 9 000, 50 000, 30 000, 10 000, 5 000, 10 000, 10 000.
文献[1]算法和文献[4]算法计算时间分别为2.69 s和3.47 s, 下料方案板材利用率分别为76.05%和76.83%.本文算法求解该实例, 算法计算时间为1.35 s, 共使用板材11 780张, 板材利用率为77.54%.
5 结语构造了圆形件条带在块中布局的递归算法, 给出了块的规范尺寸用以减少算法计算量.然后用列生成算法迭代调用上述排样算法生成下料方案, 并对小数解进行圆整操作得到更加精确的下料方案.实验结果表明, 所提下料算法在计算时间和提高板材利用率方面均有效.本文下料算法的框架是将单张板材上圆形件数量无约束的剪冲排样算法与列生成算法相结合.设计单张板材上圆形件数量有约束的剪冲排样算法, 并将其与顺序启发式算法相结合形成下料算法可作为今后的研究内容.
参考文献

[1]	Cui Y. Generating optimal T-shape cutting patterns for circular blanks[J]. Computers & Operations Research, 2005, 32(1): 143-152.
[2]	张瑞友, 潘卫平, 刘士新. 基于匀质块五块模式的矩形件非剪切排样算法[J]. 东北大学学报(自然科学版), 2018, 39(6): 771-775. (Zhang Rui-you, Pan Wei-ping, Liu Shi-xin. Non-guillotine cutting algorithm of rectangular items based on five-homogeneous-block mode[J]. Journal of Northeastern University(Natural Science), 2018, 39(6): 771-775.)
[3]	侯桂玉, 崔耀东, 黄少丽, 等. 一种求解圆形件下料问题的启发式算法[J]. 计算机工程, 2010, 36(13): 227-229. (Hou Gui-yu, Cui Yao-dong, Huang Shao-li, et al. Heuristic algorithm for cutting stock problem of circular item[J]. Computer Engineering, 2010, 36(13): 227-229. DOI:10.3969/j.issn.1000-3428.2010.13.081)
[4]	王峰, 张军, 胡钢. 圆形片剪冲下料问题的一种求解算法[J]. 锻压技术, 2015, 40(10): 39-44. (Wang Feng, Zhang Jun, Hu Gang. An algorithm for solving the shearing problem of circular blanks[J]. Forging & Stamping Technology, 2015, 40(10): 39-44.)
[5]	Cui Y, Huang B. A heuristic for constrained T-shape cutting patterns of circular items[J]. Engineering Optimization, 2011, 43(8): 867-877. DOI:10.1080/0305215X.2010.522708
[6]	Cui Y, Gu T, Hu W. A bi-objective guillotine cutting problem of stamping strips of equal circles[J]. International Journal of Computer Mathematics, 2010, 87(12): 2716-2721. DOI:10.1080/00207160902745325
[7]	Furini F, Malaguti E. Models for the two-dimensional two-stage cutting stock problem with multiple stock size[J]. Computers & Operations Research, 2013, 40(8): 1953-1962.
[8]	Silva E, Alvelos F, Carvalho J. An integer programming model for two-and three-stage two-dimensional cutting stock problems[J]. European Journal of Operational Research, 2010, 205(3): 699-708. DOI:10.1016/j.ejor.2010.01.039
[9]	Chen Q, Cui Y, Chen Y. Sequential value correction heuristic for the two-dimensional cutting stock problem with three-staged homogenous patterns[J]. Optimization Methods and Software, 2016, 31(1): 68-87. DOI:10.1080/10556788.2015.1048860
[10]	Cui Y, Yao Y, Cui Y P. Hybrid approach for the two-dimensional bin packing problem with two-staged patterns[J]. International Transactions in Operational Research, 2016, 23(3): 539-549. DOI:10.1111/itor.12188
[11]	胡钢, 杨瑞, 潘立武. 基于价值修正的圆片下料顺序启发式算法[J]. 图学学报, 2016, 37(3): 337-341. (Hu Gang, Yang Rui, Pan Li-wu. Sequential value correction heuristic algorithm for the circle cutting stock problem[J]. Journal of Graphics, 2016, 37(3): 337-341.)
[12]	Cui Y, Wang Q. Exact and heuristic algorithms for the circle cutting problem in the manufacturing industry of electric motors[J]. Journal of Combinatorial Optimization, 2007, 14(1): 35-44. DOI:10.1007/s10878-006-9039-z
[13]	Birgin E, Lobato R, Morabito R. Generating unconstrained two-dimensional non-guillotine cutting patterns by a recursive partitioning algorithm[J]. Journal of the Operational Research Society, 2012, 63(2): 183-200. DOI:10.1057/jors.2011.6
[14]	Dolatabadi M, Lodi A, Monaci M. Exact algorithms for the two-dimensional guillotine knapsack[J]. Computers & Operations Research, 2012, 39(1): 48-53.
[15]	Pedroso J, Cunha S, Tavares J. Recursive circle packing problems[J]. International Transactions in Operational Research, 2016, 23(1/2): 355-368.
[16]	Cui Y. Dynamic programming algorithms for the optimal cutting of equal rectangles[J]. Applied Mathematical Modeling, 2005, 29(11): 1040-1053. DOI:10.1016/j.apm.2005.02.007
[17]	Ozlen M, Burton B, MacRae C. Multi-objective integer programming: an improved recursive algorithm[J]. Journal of Optimization Theory and Applications, 2014, 160(2): 470-482. DOI:10.1007/s10957-013-0364-y
[18]	杨传民, 王树人, 王心宇. 基于4块结构的斩断切割布局启发性算法[J]. 机械设计, 2007, 24(2): 25-26. (Yang Chuan-min, Wang Shu-ren, Wang Xin-yu. Heuristic algorithm on layout of chopped cutting based on 4 pieces of structure[J]. Journal of Machine Design, 2007, 24(2): 25-26. DOI:10.3969/j.issn.1001-2354.2007.02.008)