全 文 ：第 52 卷 第 5 期
2 0 1 6 年 5 月
林 业 科 学
SCIENTIA SILVAE SINICAE
Vol. 52，No. 5
May，2 0 1 6
doi:10．11707 / j．1001-7488．20160518
收稿日期: 2015 － 10 － 21; 修回日期: 2015 － 12 － 09。
基金项目: 中国林业科学研究院林业新技术所基本科研业务费专项(CAFINT2012K01) ; 河北省自然科学基金资助项目(E2015204039) ;
河北省科技计划项目(15217218)。
* 侯晓鹏为通讯作者。
面向零件的人造板材矩形件锯切排样数学
建模及遗传算法求解*
张国梁1，2，3 蔡小娜1，4 侯晓鹏2，3 赵 旦5 周玉成2，3 葛浙东2，3
(1．河北农业大学木材科学与工程研究所 保定 071000; 2．中国林业科学研究院林业新技术研究所 北京 100091;
3．中国林业科学研究院木材工业研究所 北京 100091; 4． 河北农业大学基础课部 沧州 061100;
5．中国科学院遥感与数字地球研究所 北京 100094)
摘 要: 【目的】探讨人造板材矩形零件锯切排样的启发式规则，建立锯切排样的数学模型并研究求解方法，为
解决由于整体套排导致国产排样系统使开料锯在工作过程中锯路变化繁琐、降低切割效率的问题提供科学依据。
【方法】基于一套板式家具下料清单中往往有 2 种或 2 种以上零件存在相互配合尺寸的情况，提出基于配合尺寸
的分组降维启发式规则，按配合尺寸由大到小排序并将所有矩形零件分组，使每组零件种类不大于 4 种; 以余料面
积最小为评价指标，建立面向零件的锯切排样数学模型，通过设定冗余系数估算基材板需求量，以矩形零件数量及
在基材板上的排样长度、宽度和面积不超限为约束条件，设立排样宽度系数并通过为矩形零件和基材板的长、宽尺
寸增加一个单位的锯路宽度以抵消在基材板最下端和最右端的“虚拟锯路损失”; 采用遗传算法进行模型求解并
利用惩罚函数法处理约束条件，经染色体整数编码、初始种群建立、具有一定自适应性的惩罚因子建立、基于外点
惩罚函数的适应度函数建立和遗传操作，利用结合 MATLAB 遗传算法工具箱而建立的排样算法计算出描述排样方
案的向量; 通过实例验证模型和算法的可行性。【结果】所有矩形零件的排样方案通过 4 个参数来描述，即某个排
样零件的排放目标板材号、在基材板上的排放行号及横向或竖向的排放方式; 排样矩阵的行数为 4，列数为矩形零
件总数，每列表示 1 个零件的排样结果。应用实例表明，基于配合尺寸的启发式规则使多种矩形零件分组排样，每
组排样方案的最优控制向量可明显划分为高低不同的 4 段，分别表示 4 个参数; 遗传运算在限定的迭代次数内都
趋于收敛，体现出较好的全局寻优能力，排样方案的可视化图形满足“一刀切”的锯切工艺要求，且锯路规整，有利
于提高锯切效率。【结论】基于配合尺寸的启发式规则和面向零件的锯切排样模型对于人造板材优化排样具有一
定可行性，可为板式家具锯切排样提供新的解决方法，但要提高开料锯的锯切效率，还需将走刀次数、惩罚因子的
优化选择等加以综合考虑。
关键词: 锯切排样; 分组降维; 配合尺寸; 面向零件; 遗传算法; 惩罚函数
中图分类号: TP391 文献标识码: A 文章编号: 1001 － 7488(2016)05 － 0150 － 10
Part-Oriented Cutting Layout Mathematical Modeling and Solving by
Genetic Algorithm for Rectangular Wood Based Panel Parts
Zhang Guoliang 1，2，3 Cai Xiaona 1，4 Hou Xiaopeng2，3 Zhao Dan5 Zhou Yucheng2，3 Ge Zhedong2，3
(1 ． Institute of Wood Science and Engineering，Agricultural University of Hebei Baoding 071000;
2 ． Research Institute of Forestry New Technology，CAF Beijing 100091; 3 ． Research Institute of Wood Industry，CAF Beijing 100091;
4 ． Department of Basic Courses，Agricultural University of Hebei Cangzhou 061100;
5 ． Institute of Remote Sensing and Digital Earth，Chinese Academy of Sciences Beijing 100094)
Abstract: 【Objective】In order to find gap of non-availability in most domestic literatures，which sawing velocity was
dropped down due to the frequent change of saw line，this research investigated a heuristic rule for rectangular parts cutting
layout of wood-based panel，built mathematical model and studied solving method． 【Method】Based on the situation that in
a suit of material list，coupled dimension existed among two or more kinds of parts，therefore，a grouping and dimension
reducing heuristic rule was put forward． All rectangle parts were sorting by coupled dimension in descending order，each
第 5 期 张国梁等: 面向零件的人造板材矩形件锯切排样数学建模及遗传算法求解
group consisting no more than four kinds parts． Taking the minimum remaining area as evaluation index，a part-oriented
mathematical model was set up． In this model，the quantity demanded for base panel was estimated by setting redundancy
factor，and four aspects including quantity，length，width and area of placed parts on base panel should be all wlthin the
limitation value． Moreover，layout width ratio was set and single unit saw line width was added on length and width of both
rectangular parts and base panel so as to offset fictitious saw line loss located at undermost and rightmost side of base
panel． Genetic algorithm (GA) was adopted to find global optimal solution for layout and punishment function was used to
deal with constrains． By integer coding of chromosome，establishing of initial population，punishment factors with certain
adaptability and fitness function based on exterior point punishment function and genetic manipulation，vector on behalf of
layout solution was calculated through the layout algorithm which was built in cooperation with GA toolbox of MATLAB．
Instances were applied to test feasibility of the model and algorithm．【Result】Layout solution of all rectangular parts was
described by four parameters，consisting of code，row and direction ( vertical and transverse) ． Layout matrix has 4 rows，
and the column was the total quantity of all parts． Each column represented layout solution of each part． The instances
showed that multiple parts could be grouped based on coupled dimension-based heuristic rule，optimal controlled vector
standing for layout solution for each group was divided into four sections with varied height，and these four sections meant
the four parameters． It was also demonstrated that GA tended to convergence within limited iterations and gave relatively
good capability of global optimization． In addition， visualization of layout solution displayed meet the demand of
“guillotine cutting” and the regular saw line was good for increasing sawing efficiency．【Conclusion】 The coupled
dimension-based heuristic rule and part-oriented mathematical model were suitable for cutting layout of wood-based panel
and therefore a new method was presented for cutting layout of panel-type furniture． However，in order to enhance cutting
productivity，the elements such as feeding times of cutting saw，optimized selection of punishment factor should also be
taken into account comprehensively．
Key words: cutting layout; grouping and dimension-reducing; coupled dimension; part-oriented; genetic algorithm
(GA); punishment function
优化排样也称优化下料，对于提高工业化生产
效率至关重要，也因此受到了越来越广泛的关注和
研究(董德威等，2013; Furini et al．，2013; Rostom et
al．，2014; Aiello et al．，2012)。对优化排样的研究
是随计算复杂性理论及若干相关学科如信息科学、
管理科学、工程科学和运筹学等的发展而不断革新
的。优化排样算法按求解类型不同主要可以分为数
学规划算法、迭代算法和现代优化算法等。针对具
体的应用问题，数学规划算法往往与各种启发式规
则结合求解，如动态规划算法(孙英等，2008)、“同
质块”两段矩形排样算法(季君等，2012)、混合整
数线性规划模型及列生技术(Movasher et al．，2012)
等。迭代算法应用于优化排样问题的求解更多是随
不同启发式算法的设计而发展的，如基于递归的分
支定界算法(Cui et al．，2008)、三阶段顺序启发式算
法(Suliman，2006)等。作为现代优化算法的重要
组成部分，遗传算法因具有同时处理多个个体的群
体搜索特性而体现出良好的全局寻优性能( Patel et
al．，2015; de Magalhaes et al．，2014; Sathya et al．，
2013)，从而在优化排样问题中得到了广泛应用
(Bennell et al．，2013; Hoseini et al．，2013)。笔者针
对人造板材大规模矩形零件的优化排样，设计了基
于面积的分组降维启发式规则，并应用遗传算法进
行了求解(张国梁等，2014)，但由于每行只排样 1
种零件，存在行末剩余面积较大的问题。基于此，本
文研究基于配合尺寸的分组降维启发式规则，分析
数学模型改进方法，建立面向零件的锯切排样数学
模型并研究基于遗传算法的求解方法。
1 基于配合尺寸的分组降维启发式规则
设共有 M 种矩形零件参与排样，分组的组数为
g，第 j 组零件的种类数为 Mj，则
M = ∑
g
j = 1
Mj(1 ≤ j ≤ g)。 (1)
1) 组合尺寸配合的 2 种零件。由于厚度一致，
仅考虑零件长度和宽度的尺寸。根据家具的结构特
点，一套家具排样清单中一定会出现 2 种或 2 种以上
零件在长度或宽度方向上尺寸能够相互配合。例如，
第 1 种零件尺寸为 680 × 400，第 2 种零件尺寸为
900 × 400，则 400 为相互配合的尺寸。取具有相等某
一维尺寸的 2 种零件组合排样并定义: Dim_P1 为第
1 种零件组合的配合尺寸，Dim_P2 为第 2 种零件组
合的配合尺寸，Dim_Pn 为第 n 种零件组合的配合尺
寸; 且有 Dim_P1≥Dim_P2≥…Dim_Pn。
151
林 业 科 学 52 卷
2) 选出 4 种零件进行分组。根据所定原则，在
一张基材板上最多排布 3 ～ 4 种不同规格的零件，因
此需要对所有 M 种零件进行分组。
第 1 步，取出前 2 种零件组合共计 4 种零件;
第 2 步，依次取出第 3 至第 n 种零件组合中的 2 种
组合，如果 n 为偶数，则分组数总计为 n /2; 如果 n
为奇数，则第 n 种零件组合与剩余的 M － 2·n 种零
件中前2种零件组成一组，设至此共提取了 s 组; 第
3 步，对剩余的没有分组的零件进行分组，提取前 4
种面积最大的矩形零件为第 s + 1 组，然后再次提取
剩余矩形零件中面积最大的 4 种零件为第 s + 2 组，
依次类推，直到所有 M 种零件分组完毕。
2 面向零件的锯切排样数学建模
以排样矩形零件为出发点建立排样模型，如此，
确定第 j 组内 Mj种矩形零件的排样方案可转化为本
组内任一矩形零件排样的排放位置和排放方式问
题。通俗地表述如下: 第几种矩形零件的第几个零
件排放在第几张基材板的第几行上，是横排还是竖
排即排放方式。模型建立和算法求解过程详述
如下:
1) 设基材板尺寸为 L × W。
2) 在第 j 组矩形零件中，称第 k 种矩形零件为
Mjk，需求量为 Njk，尺寸为 l jk × wjk (1≤ j≤g; 1≤k≤
Mj)，且定义 l jk ≥ wjk 。
3) 根据第 j 组内所有矩形零件的总面积计算
出第 j 组零件排样完毕最少需要基材板张数为 Nj，
设 α 为冗余系数(α≥1)，则第 j 组矩形零件排样完
毕基材板用量为:
Nαj = α·Nj。 (2)
4) 将本组内所有需要排样的矩形零件统一考
虑，设变量 Njt表示第 j 组矩形零件的总个数，则
Njt = ∑
M j
k = 1
Njk。 (3)
取出本组内 4 种零件的平均宽度尺寸，设
wmjk = mean(wjk)， (4)
则对任一个排样矩形零件而言，基材板上所能排样
的最大行数为:
Rmj =
W
wmjk
。 (5)
为使排样零件在基材板宽度和长度方向排样满
足约束条件，设定排样宽度系数 γ(0 ＜ γ ＜ 1)，使
Rmj = γ·R
m
j 。 (6)
5) 设变量 pjtsk表示任一个排样矩形零件在第 t
张基材板上第 s 行的排放方式，长度方向与基材板
长度方向一致时，pjtsk = 1; 长度方向与基材板长度
方向垂直时，pjtsk = 0; pjtsk ∈［0，1］。
6) 设数控板材开料锯的锯路宽度为 w s，不失
一般性，为每个矩形零件的长度和宽度都加上一个
单位的 w s，同时，原料板的长度和宽度方向也各加
上一个单位的 w s，以此抵消在原料板最下端和最右
端的“虚拟锯路损失”。
7) 取出排放在第 t 张基材板第 s 行上所有列的
矩形零件的尺寸信息和数量 njtsk，所有零件 (同一
行)长度之和应不大于基材板长度 L，即
(L + w s) －∑
M j
k = 1
［( l jk + ws)·njtsk·pjtsk +
(wjk + w s)·njtsk·(1 － pjtsk)］≥ 0。 (7)
8) 取出排放在第 t 张基材板的每一行上矩形
零件的最大宽度尺寸，在基材板的宽度方向，每一行
排样矩形零件的最大宽度之和应不大于基材板宽度
W，即
(W + w s) －∑
Rmj
s = 1
max［(wjk + w s)·pjtsk +
( l jk + w s)·(1 － pjtsk)］≥ 0。 (8)
9) 矩形零件排样中数量的限制。每一种矩形
零件在 Nαj 张基材板上排样数量总和应等于所要求
的排样总数，即
∑
Nαj
t = 1
∑
Rmj
s = 1
njtsk － Njk = 0。 (9)
10) 矩形零件在基材板上排样面积的限制。在
每一张基材板上，所排样的矩形零件总面积应小于
基材板面积，即
L·W －∑
M j
k = 1
l jk·wjk·njtsk ＞ 0。 (10)
以余料最小为目标函数，根据上述约束条件，构
建面向零件的数学模型如下:
s． t．
(L + w s) － Σ
M j
k = 1
［( l jk + w s)·njtsk·pjtsk +
(wjk + w s)·njtsk·(1 － pjtsk)］≥ 0
(W + w s) － Σ
Rmj
s = 1
max［(wjk + w s)·pjtsk +
( l jk + w s)·(1 － pjtsk)］≥ 0
Σ
Naj
t = 1
Σ
Rmj
s = 1
njtsk － Njk = 0
pjtsk ∈［0，1］
L·W － Σ
M j
k = 1
l jk·wjk·njtsk ＞




 0
251
第 5 期 张国梁等: 面向零件的人造板材矩形件锯切排样数学建模及遗传算法求解
F = min∑
Nαj
t = 1
(L·W －∑
Mj
k = 1
ljk·wjk·njtsk) ＞ 0。(11)
3 面向零件的锯切排样模型遗传算法求解
3. 1 染色体编码和初始种群的建立
采用整数编码的方法，定义一条染色体是当前
组所有矩形零件排样结果。包括 4 方面内容: 第几
个零件、排样在第几张基材板的第几行和排放方式，
称之为 4 个变量。调用 MATLAB 遗传算法工具箱
中的基向量创建函数，并且令 BaseV = crtbase ( rep
(Njt，［1，4］)，［Mj，Nja，Rjm，1］)，从而得到锯切排样
模型求解所需的基向量 BaseV，向量中的元素代表
染色体中基因位的基本字符。其中: Mj，即零件种
类基本字符，表示任一个零件必然是 Mj种零件中的
一种; Nja，即基材板张数基本字符，表示任一个零件
排样在第几张基材板; Rjm，即行基本字符，表示任
一个零件可能排在某一张基材板的第几行;1，即排
样方式基本字符，表示任一个零件在某一张基材板
的某一行上是横排还是竖排。
将由 基 向 量 创 建 函 数 得 到 的 BaseV 代 入
MATLAB 遗传算法工具箱的初始种群创建函数，并
令: Chrom = crtbp(Nind，BaseV) + ones(Nind，length
(BaseV))，得到初始种群，用 Chrom 表示。其中:
Nind 表示初始种群规模; crtbp( )表示随机种群创
建函数; ones( )表示保证矩阵处理中行、列序号不
为零的函数。
3. 2 基于惩罚函数的适应度函数建立
在遗传运算中，根据适应度函数值大小对种群
中的个体进行取舍，因此必须建立适应度函数。
根据式(3)，Njt表示第 j 组排样矩形零件的总个
数。在初始种群 Chrom 中，令: p1 = Chrom (:，1:
Njt)，为所有零件的种类; p2 = Chrom(:，Njt + 1:2*
Njt )，为所有零件所在基材板; p3 = Chrom (:，
2* Njt + 1:3* Njt)，为所有零件所在行; p4 = Chrom
(:，3* Njt + 1:4* Njt)，为所有零件的排样方式。
基于式(11)建立锯切排样模型的目标函数:
ObjV_0 = Cutting_pattern( p1，p2，p3，p4)。
其中: p1 ～ p4 为编码后的染色体针对 4 个变量的分
解量; ObjV_0 为所有基材板面积总和与所有已排
样零件面积和的差值，即剩余面积。
基于式(7) ～ (10)分别建立 4 个惩罚函数与其
对应:
Penalty_1 = Punishment_1( p1，p2，p3，p4);
Penalty_2 = Punishment_2( p1，p2，p3，p4);
［Penalty_3_Min，Penalty_3_Max］= Punishment_3
( p1，p2，p3，p4);
Penalty_4 = Punishment_4( p1，p2，p3，p4)。
其中: Penalty_1 为基材板长度尺寸与其上每一行所
排零件长度方向尺寸和的差值; Penalty_2 为基材板
宽度尺寸与其上每一行所排零件的最大宽度之和的
差值; Penalty_3_Min 为每一种矩形零件在所有基材
板上排样数量总和与所要求排样总数差值的最小
值; Penalty_3 _Max 为每一种矩形零件在所有基材
板上排样数量总和与所要求排样总数的差值的最大
值; Penalty_4 为每张基材板排样零件面积之和与基
材板面积的差值; Punishment_1( )为惩罚函数 1，约
束类型为不等式; Punishment_2( )为惩罚函数 2，约
束类型为不等式; Punishment_3( )为惩罚函数 3，约
束类型为等式; Punishment_4( )为惩罚函数 4，约束
类型为不等式;
本文使用外点惩罚函数法处理约束条件，这是
因为在多次试验中发现，遗传算法初始种群中有部
分个体并不满足约束条件，对惩罚函数法而言即初
始点落于可行域外，外点法可以适用这种限制 (骆
志高等，2009)，而内点法并不满足使用要求。因此
采用外点惩罚函数法处理约束条件，构造具有惩罚
项的目标函数:
ObjV = ObjV_0 + a1 ．* min(0，Penalty_1) ．
2 +
a2 ．* min(0，Penalty_2) ．
2 +
a31 ．* (Penalty_3_Min．
2) +
a32 ．* (Penalty_3_Max．
2) +
a4 ．* min(0，Penalty_4) ．
2。 (12)
式中: ObjV 为含惩罚项的目标函数值; a1，a2，a31，
a32，a4 为初始惩罚因子。
对应锯切排样数学模型的等式和不等式约束，
惩罚项具有如下作用:
1) 对 3 个不等式约束，当满足约束条件时，惩
罚项为 0，即
ai ．* min(0，Penalty_i) ．
2 = 0(i = 1，2，4); (13)
当违反某一约束条件时，
ai ．* min(0，Penalty_i) ．
2 = ai ．* Penalty_i．
2 ＞ 0。
(14)
这表示零件在基材板上的排样不满足长度、宽
度或面积的约束条件，则惩罚项起作用，且距离约束
边界越远，惩罚力度越大，从而迫使迭代点回到可行
域内。
2) 对等式约束所表示的零件数量限制，若满足
约束条件，则
a31 ．* (Penalty_3_Min．
2) + a32 ．*
351
林 业 科 学 52 卷
(Penalty_3_Max．2) = 0， (15)
惩罚项不起作用，若不能满足约束条件，则
a31 ．* (Penalty_3_Min．
2) + a32 ．*
(Penalty_3_Max．2) ＞ 0。 (16)
从而使遗传种群中对应个体的适应度值降低，减小
遗传到下代的概率。
3. 3 惩罚因子自适应算法
惩罚因子的大小适度是保证求解结果满足约束
条件的关键。在遗传运算中，利用每次迭代过程中
的约束项反馈信息调整惩罚因子，从而使惩罚因子
具有一定的自适应性，有利于提高求解精度 (张国
英等，2010; 桑志祥等，2013; 甘敏等，2010)。
在程序运行中发现，对惩罚函数 1，2 和 4，约束
条件不满足程度越大，种群均值越小; 对惩罚函数
3，约束条件不满足程度越大，种群均值的平方越大。
由此，定义惩罚因子适应性规则为:
ai =
ai·β(1)，case1
ai·β(2)，case2
ai·β(3)，
{
case3
(17)
式中:β(1) ＜ 1，β(2) = 1，β(3) ＞ 1。对惩罚函数 1，
2 和 4，case1 表示第 g 代种群均值大于第 g － 1 代种
群均值，case2 表示第 g 代种群均值等于第 g － 1 代
种群均值，case3 表示第 g 代种群均值小于第 g － 1
代种群均值; 对惩罚函数 3，case1 表示第 g 代种群
均值平方小于第 g － 1 代种群均值平方，case2 表示
第 g 代种群均值平方等于第 g － 1 代种群均值平方，
case3 表示第 g 代种群均值平方大于第 g － 1 代种群
均值平方。
3. 4 遗传操作
适应度分配函数采用 ranking． m，即基于秩的排
序，选择压差为 2，线性排序; 选择函数采用 sus． m，
即随机遍历抽样方式; 交叉函数采用 xovdp． m，即
两点交叉，交叉概率根据实际情况设定; 变异函数
采用 mutbga． m，即实值种群的变异，变异概率取缺
省值; 重插入子代到新种群函数采用 reins． m。实
践证明，上述选择方式的应用效果是比较理想的，基
本达到了人造板材锯切排样工艺的要求。
3. 5 排样矩阵输出
经染色体编码、初始种群建立、基于惩罚函数的
目标函数建立和遗传操作，利用结合 MATLAB 遗传
算法工具箱而建立的排样算法计算出描述排样方案
的向量，向量长度为 4 × Njt。设变量 Variable_Last
表示算法优化求解后的最优染色体，即排样方案向
量，为清楚描述 4 个变量，对最优染色体即排样方案
向量进行分解:
Ma = Variable_Last(1，1:Njt )——— 描述所有零
件种类的数组;
Mb = Variable_Last(1，Njt + 1:2* Njt)———描述
所有零件所在基材板序号的数组;
Mc = Variable_Last(1，2* Njt + 1:3* Njt)———描
述所有零件所在行的数组;
Md = Variable_Last(1，4 * Njt + 1:5 * Njt )———
描述所有零件的排样方式的数组;
Matrix =［Ma;Mb;Mc;Md］——— 每一列表示一
个零件的排样结果。
最终得到排样矩阵 Matrix，矩阵维数为 4 行，
Njt列。
4 应用实例
4. 1 实例 1
1) 基本排样数据与遗传求解。本着由简到繁
的原则，实例 1 共有 4 种零件参与排样，且存在尺寸
的配合关系，试验数据如表 1 所示。
表 1 面向零件排样模型的矩形件数据
Tab． 1 Data of rectangular parts for part-oriented model
编号 No． 数量 Quantity 长 Length /mm 宽 Width /mm
1 15 900 400
2 8 680 400
3 8 320 240
4 22 400 320
基材板尺寸为 1 220 mm × 2 440 mm。经试验
修正，初始惩罚因子取为: a1 = 1 × 10
20，a2 = 1 ×
1020，a31 = 1 × 10
30，a32 = 1 × 10
30，a4 = 1 × 10
20;惩
罚因子适应系数 β1 = β2 = β31 = β32 = β4 =［0. 8，1，
5］，初始群体规模 50，最大遗传代数 300，代沟
0. 9，交叉概率 0. 7，基材板冗余系数 α = 1. 1，排样
宽度系数 γ = 0. 6，锯路宽度 w s = 5 mm。运行遗传
算法得到排样矩阵 Matrix，将矩阵中数值单独列出
如图 1 所示。
从图 1 可见，排样矩阵 Matrix 共 4 行 53 列，第 1
行表示所有排样零件的每一个个体; 第 2 行表示零
件排样在第几张基材板; 第 3 行表示零件排样在基
材板的第几行; 第 4 行表示零件的排样方式。每列
表示 1 个零件的排样结果，例如第 1 列转置后为
［4 1 1 0］，表示第 4 种零件的 1 个零件排在了第 1
张基材板上的第 1 行上，且为竖排。排样结果显示
共使用了 4 张基材板，每张基材板的排样信息矩阵
如图 2 所示。
451
第 5 期 张国梁等: 面向零件的人造板材矩形件锯切排样数学建模及遗传算法求解
图 1 实例排样矩阵
Fig． 1 Layout matrix of the instance
图 2 每张基材板排样矩阵
Fig． 2 Layout matrix for each base panel
定义基材板利用率向量为 Efficieny，第 1 ～ 4 张
基材板利用率依次为向量 Efficieny 中的第 1 ～ 4 个
值。基材板利用率向量为: Efficiency = ［0. 933 1
0. 933 1 0. 920 0 0. 910 5］。
遗传算法求解过程中最优控制向量如图 3 所
示。图 3 中，折线图中的各个实心点表示排样矩阵
Matrix 中的各个值，从左至右看，每 4 个实心点表示
排样矩阵中的每一列，即 1 个零件的排样结果。例
如，图中倒数 4 个实心点的数值依次为［4 4 3 1］，表
示第 4 种零件的 1 个零件排放在了第 4 张基材板的
第 3 行上，方式为横排。
遗传运算中，含惩罚项的目标函数值 ObjV 迭
代变化如图 4 所示。从图 4 可以看出，遗传搜索大
约在 25 次迭代后趋于收敛，即图中的曲线迅速下
降，然后迅速平稳，说明本文建立的遗传算法的全局
寻优能力达到设计要求。图 5 所示是将第 2 张基材
板排样方案图形化的结果，图中每个零件排在了基
材板的相应位置，并且锯切路径清晰，满足人造板材
开料锯“一刀切”的锯切工艺要求。
2) 排样方案优化。由图 5 可知，每一行排样零
件中同种矩形零件并未排列在一起而影响开料锯的
锯切速度，这与遗传算法的随机性不无关系，需进一
551
林 业 科 学 52 卷
图 3 最优控制向量分布
Fig． 3 Distribution of optimal controlled vector
图 4 目标函数均值和最优值迭代变化曲线
Fig． 4 Iterative changes of objective function mean
value and optimal value
图 5 第 2 张基材板排样方案
Fig． 5 Layout solution figure of the second base panel
步优化。优化的准则为: 将每行排样零件按基材板
宽度方向尺寸降序排列。将这一准则应用到矩阵输
出算法中，以达到规整锯路的目的。优化后的第 2
张基材板排样方案如图 6 所示。
4. 2 实例 2
实例 2 待排样的矩形零件数据为床头柜的部分
零件，共 7 种，来自于河北省某家具公司的生产数
据，规格和用量如表 2 所示。零件均为 12 mm 厚，
基材板统一使用 2 440 mm × 1 220 mm × 12 mm 的
中密度纤维板。
图 6 第 2 张基材板优化排样方案
Fig． 6 Optimized layout solution figure of the second base panel
表 2 实例 2 排样零件数据表
Tab． 2 Data sheet of layout parts for instance two
编号
No．
数量
Quantity
长度
Length /mm
宽度
Width /mm
1 30 557 395
2 20 1 124 420
3 28 984 338
4 30 557 520
5 40 515 400
6 57 347 97
7 50 515 100
基材板尺寸为 1 220 mm × 2 440 mm，选取种群
规模为 80，遗传代数为 200，代沟 0. 9，基材板冗余
系数α = 1. 2，交叉概率 0. 8; 初始惩罚因子 α1 = 1 ×
1010，α2 = 1 × 10
10，α31 = 1 × 10
20，α32 = 1 × 10
20，α4 =
1 × 1010;惩罚因子适应系数为 β1 = β2 = β31 = β32 =
β4 =［0. 8，1，1. 2］，排样宽度系数 γ = 0. 6，锯路宽度
w s = 5 mm，运行遗传运算。按基于配合尺寸的分组
降维启发式规则，所有 16 种零件分为 2 组，分组情
况见表 3。
表 3 实例 2 排样零件分组方式
Tab． 3 Grouping of layout parts for instance two
组号
Group
序号
No．
长度
Length /mm
宽度
Width /mm
数量
Quantity
1
1 557 395 30
4 557 520 30
5 515 400 40
7 515 100 50
2
2 1 124 420 20
3 984 338 28
6 347 97 57
1) 第 1 组零件排样方案。第 1 组零件的整体
排样方案由 10 张个体基材板排样方案组成，如表 4
所示，其中第 2 张基材板的利用率最高为 92. 10%，
平均利用率为 87. 65%。
651
第 5 期 张国梁等: 面向零件的人造板材矩形件锯切排样数学建模及遗传算法求解
表 4 实例 2 第 1 组零件排样方案表
Tab． 4 Layout solution of group one instance two
基材板序号
No． of base panel
利用率
Efficiency(% )
零件序号 ×数量
No． of parts × quantity
1 89. 38 1 × 2，4 × 5，5 × 2，7 × 7
2 92. 10 1 × 5，4 × 3，5 × 2，7 × 7
3 87. 87 1 × 2，4 × 2，5 × 7，7 × 3
4 86. 61 1 × 3，4 × 4，5 × 3，7 × 3
5 88. 30 1 × 2，4 × 4，5 × 4，7 × 4
6 86. 57 1 × 2，4 × 4，5 × 4，7 × 3
7 88. 86 1 × 5，4 × 0，5 × 6，7 × 6
8 87. 18 1 × 1，4 × 5，5 × 3，7 × 6
9 87. 56 1 × 5，8 × 2，3 × 3，7 × 6
10 82. 03 1 × 2，8 × 3，3 × 5，7 × 2
2) 第 2 组零件排样方案。第 2 组零件的整体
排样方案由 8 张个体基材板排样方案组成，如表 5
所示，其中第 6 张基材板的利用率最高为 90. 14%，
平均利用率为 86. 81%。
2 组排样零件的遗传运算过程中，最优控制向
量即排样矩阵的折线图描述如图 7 所示。与实例 1
所示最优控制向量分布图的表示不同，本例以排样
矩阵的“行”向量为顺序绘图。从图 7 可以看出，由
于每组的排样零件数量和尺寸不同，第 1 组和第 2
组的排样矩阵数值各不相同; 但 2 幅分图都可明显
划分为高低不同的 4 段。以“第 1 组”为例，段 1 表
示零件种类，段 2 表示所在基材板，段 3 表示所在
行，段 4 表示排放方式，分别对应锯切排样的 4 个
基本变量。
表 5 实例 2 第 2 组零件排样方案表
Tab． 5 Layout solution of group two instance two
基材板序号
No． of base panel
利用率
Efficiency(% )
零件序号 ×数量
No． of parts × quantity
1 84. 32 2 × 2，3 × 4，6 × 7
2 84. 32 2 × 2，3 × 4，6 × 7
3 89. 01 2 × 3，3 × 3，6 × 7
4 89. 01 2 × 3，3 × 3，6 × 7
5 84. 32 2 × 2，3 × 4，6 × 7
6 90. 14 2 × 3，3 × 3，6 × 8
7 89. 01 2 × 3，3 × 3，6 × 7
8 84. 32 2 × 2，3 × 4，6 × 7
遗传运算中，含惩罚项的目标函数值迭代变化
如图 8 所示。图 8 表明，遗传运算在限定的迭代次
数内都趋于收敛，即图中曲线由下降变为水平状态，
表明算法搜索到较优值。之所以说是较优值，是因
为遗传运算受本身的启发式随机搜索特性和排样参
数的影响很大，参数不同，搜索结果亦会有所变化。
根据行内排样零件按基材板宽度方向尺寸降序
排列的优化准则对输出矩阵进行优化。第 1 组第 2
张排样方案和第 2 组第 6 张排样方案可视化如图 9
所示，可见，排样方案清晰且满足“一刀切”的锯切
工艺要求。
图 7 实例 2 最优控制向量分布
Fig． 7 Distribution of optimal controlled vector for instance two
5 结论与讨论
本文针对人造板材矩形件锯切排样，提出了基
于配合尺寸的分组降维启发式规则，建立了面向零
件的锯切排样数学模型，使排样方案描述为 4 方面
内容，即第几个零件排样在第几张基材板的第几行
上及其排放方式。遗传编码采用整数编码方式，采
用外点惩罚函数法处理约束条件，并且设计了具有
一定自适应性的惩罚因子，应用实例表明了该模型
和算法的可行性。
遗传算法群体搜索性使其具有较好的全局搜索
751
林 业 科 学 52 卷
图 8 实例 2 目标函数均值和最优值迭代变化曲线
Fig． 8 Iterative changes of objective function mean value and optimal value for instance two
图 9 实例 2 排样方案可视化示例
Fig． 9 Visualization example of layout solution of instance two
能力，正确的编码是遗传算法能够成功运行的关键，
对于不同问题应选择不同的编码策略。针对目标优
化问题，已有研究表明整数编码能够提高运行效率
(陈瑶等，2013; 覃柏英，2011)，但遗传编码方式的
选择还有待进一步研究，以期解决更为复杂的实际
问题。
惩罚函数法是求解具有约束条件的数学模型时
常用的策略，内点法适用于等式约束，外点法适用于
不等式约束，问题关键在于惩罚因子的选择。根据
具体的问题，惩罚因子多根据经验选择，但这需要大
量的试验和先验知识，如何更为合理地确定惩罚因
子依然是研究的热点问题。
本文以基材利用率作为评价指标研究人造板材
锯切优化排样，并根据每行排样零件按基材板宽度
方向尺寸降序排列的原则对排样方案进行优化，从
而使尺寸相同或相近的零件连排在一起，有利于提
高锯切效率。但仍会发现，排样图中存在零件纵横
向排列的方向性问题，这与面向零件的锯切排样数
学模型的约束条件以及遗传算法的随机性有一定关
系。如何将走刀次数和排样方向纳入评价指标并建
立对应的约束条件和数学模型是又一需要讨论的
问题。
参 考 文 献
陈 瑶，霍佳震 ． 2013．整数编码的组群遗传算法在分组优化中的设
计和应用 ．上海交通大学学报，47(3) : 472 － 478．
(Chen Y，Huo J Z． 2013． Number-coded grouping genetic algorithm for
solving grouping problem: design and application． Journal of
Shanghai Jiaotong University，47(3) : 472 － 478． ［in Chinese］)
董德威，颜云辉 ． 2013． 缺陷板材非规则件优化排样 ． 图学学报，34
(2) :31 － 37．
(Dong D W，Yan Y H． 2013． Optimal packing of irregular parts on
plates with defects． Journal of Graphics，34 ( 2 ) : 31 － 37． ［in
Chinese］)
甘 敏，彭 辉，王 勇 ． 2010．多目标优化与自适应惩罚的混合约束
优化进化算法 ．控制与决策，25(3) :378 － 382．
(Gan M， Peng H，Wang Y． 2010． Multiobjective optimization and
adaptive penalty function based constrained optimization evolutionary
algorithm． Control and Decision， 25 ( 3 ) : 378 － 382． ［ in
Chinese］)
季 君，陆一平，查建中，等 ． 2012．生成矩形毛坯最优两段排样方式
的确定型算法 ．计算机学报，35(1) :183 － 191．
( Ji J，Lu Y P，Cha J Z，et al． 2012． A deterministic algorithm for
optimal two-segment cutting patterns of rectangular blanks． Chinese
Journal of Computers，35(1) :183 － 191． ［in Chinese］)
骆志高，王 洋，李 举，等 ． 2009． 遗传算法与惩罚函数法在辗轧成
形工艺参数优化中的应用 ． 中国机械工程，20 ( 14 ) :1704 －
1707．
(Luo Z G，Wang Y，Li J，et al． 2009． Application of genetic algorithm
851
第 5 期 张国梁等: 面向零件的人造板材矩形件锯切排样数学建模及遗传算法求解
and penalty function method in roll-forming process parameters
optimization． Chinese Mechanical Engineering，20 ( 14 ) : 1704 －
1707． ［in Chinese］)
覃柏英，林贤坤，张令弥，等 ． 2011． 基于整数编码遗传算法的传感器
优化配置研究 ．振动与冲击，30(2) :252 － 257．
(Qin B Y，Lin X K，Zhang L M，et al． 2011． Optimal sensor placement
based on integer-coded genetic algorithm． Journal of Variation and
Shock，30(2) :252 － 257． ［in Chinese］)
桑志祥，李绍军，张 杰 ． 2013．基于 AEA 算法的自适应惩罚函数求
解约束优化及其在丁烯烷化过程的应用 ．高校化学工程学报，27
(1) :136 － 141．
( Sang Z X，Li S J，Zhang J． 2013． A new adaptive penalty function
based on AEA algorithm for solving constrained optimization
problems and its application in process optimization of butane
alkylation． Journal of Chemical Engineering of Chinese Universities，
27(1) :136 － 141．［in Chinese］)
孙 英，崔耀东 ． 2008．简化同尺寸矩形毛坯排样方式的动态规划算
法 ．计算机应用与软件，25(12) :91 － 92．
( Sun Y， Cui Y D． 2008． A dynamic programming algorithm for
simplifying the cuting patterns of equal rectangular blanks． Computer
Applications and Software，25(12) :91 － 92．［in Chinese］)
张国梁，侯晓鹏，苗 虎，等 ． 2014． 基于分组降维规则和遗传算法的
人造板材矩形件优化下料方法 ．林业科学，50(6) :181 － 186．
( Zhang G L，Hou X P，Miao H， et al． 2014． Layout method of
rectangular wood based panel parts based on grouping and dimension
reducing heuristic rule and genetic algorithm． Scientia Silvae
Sinicae，50(6) :181 － 186． ［in Chinese］)
张国英，刘冠洲，徐 宁，等 ． 2010． 自适应约束惩罚的粒子群聚类算
法 ．郑州大学学报: 理学版，42(2) :47 － 52．
(Zhang G Y，Liu G Z，Xu N，et al． 2010． Particle swarm clustering
algorithm based on adapative constrained penalty． Journal of
Zhengzhou University: Natural Science Edition，42(2) :47 － 52．［in
Chinese］)
Aiello G， La Scalia G， Enea M． 2012． A multi objective genetic
algorithm for the facility layout problem based upon slicing structure
encoding． Expert Systems with Applications，39 ( 12 ) : 10352 －
10358．
Bennell J A，Lee L S，Potts C N． 2013． A genetic algorithm for two-
dimensional bin packing with due dates． International Journal of
Production Economics，145(2) : 547 － 560．
Cui Y，Yang Y，Cheng X，et al． 2008． A recursive branch-and-bound
algorithm for the rectangular guillotine strip packing problem．
Computers ＆ Operations Research，35(4) : 1281 － 1291．
de Magalhes C S，Almeida D M，Barbosa H J C，et al． 2014． A
dynamic niching genetic algorithm strategy for docking highly flexible
ligands． Information Sciences，289(12) :206 － 224．
Furini F，Malaguti E． 2013． Models for the two-dimensional two-stage
cutting stock problem with multiple stock size． Computers ＆
Operations Research，40(8) : 1953 － 1962．
Hoseini P， Shayesteh M G． 2013． Efficient contrast enhancement of
images using hybrid ant colony optimisation，genetic algorithm，and
simulated annealing． Digital Signal Processing，23(3) : 879 － 893．
Mobasher A，Ekici A． 2013． Solution approaches for the cutting stock
problem with setup cost． Computers ＆ Operations Research，40(1) :
225 － 235．
Patel N， Padhiyar N． 2015． Modified genetic algorithm using box
complex method: application to optimal control problems． Journal of
Process Control，26(2) :35 － 50．
Rostom M R，Nassed A O，Metwalli S M． 2014. 3D overlapped grouping
Ga for optimum 2D guillotine cutting stock problem． Alexandria
Engineering Journal，53(3) :491 － 503．
Sathya S S， Radhika M V． 2013． Convergence of nomadic genetic
algorithm on benchmark mathematical functions． Applied Soft
Computing，13(5) :2759 － 2766．
Suliman S M A． 2006． A sequential heuristic procedure for the two-
dimensional cutting-stock problem． International Journal of
Production Economics，99(1 /2) :177 － 185．
(责任编辑 石红青)
951