暂存区受限瓦楞纸板生产线下料问题研究

吴青松， 杨宏兵， 陈睿卿

(苏州大学 机电工程学院， 江苏 苏州 215137)

随着纸板行业自动化控制技术的快速发展[1-2]，原料和人力成本的急剧增加，如何制订最优的切割下料(rectangles coil cutting，RCC)方案以最大程度地降低原纸损耗率已成为纸板加工业管控的难点。类似问题也广泛存在于如皮革切割、型材切割等加工领域[3]。切割下料关键点是如何在原材料上合理地排布矩形件(如不同规格纸板等)的位置，从而在满足客户订单要求的前提下，达到原材料消耗最小，加工时间最短，操作复杂度最小等目标。与板材下料不同的是，RCC问题中各卷材的宽度为固定值，但长度视为无限。该问题归属于二维开放布局问题[4-5]，具备NP难计算复杂度。

在多品种、大批量订单的生产背景下，受限于加工便利性和可行性要求，RCC问题往往采用2阶段切割模式(exact 2-stage guillotine cutting pattern)[6]，其解称为下料方案，由一组排样方式按照一定数量、一定顺序组合而成。排样方式的宽度等于选用卷材的宽度。各排样方式由多条条带平行拼接组成，各条带采用同质带构造方法，即每条条带内仅能同向排布一个订单的矩形件。

针对这种生产模式，扈少华等[7]、朱强等[8]均设计混合启发式规则，依次排布条带和各条带长度，但规则中阈值的引入导致优化过早停止，解的质量较低；邓国斌等[9]基于矩形件价值设计，嵌套使用动态规划和顺序启发式算法，可以获得质量较优的解，但这是以段尾插入异质子条带，增加加工难度为代价的；黎凤洁等[10]68面向可加工性，设计基于矩形件价值修正的剪切排样算法，在满足限制性加工工艺的同时优化材料利用率，但该算法仅能应用于单规格卷材问题，与实际生产应用仍存在差距。

立足于多品种、大批量订单的生产模式，课题组在综合瓦楞纸板行业下料问题[11-12]的基础上，提炼出一类带强顺序限制的一般纸板排样下料问题。受限于高昂的图案平均准备成本，纸板生产过程中排样方式不重复使用，为了与其他问题区别，下文中排样方式均用图案(pattern)代称。

该问题为RCC问题的子问题，并具备以下特性：

1) 可选用多规格卷材；

2) 强制性的二阶段切割生产模式；

3) 高昂的图案平均准备成本(置换损失)；

4) 图案顺序的强约束关系。

关于一般纸板排样下料问题，只有少量文章[13]534与本文选题相符，其采用多目标遗传算法，同时优化原料利用率和图案数量。但该方法染色体设计较为繁琐，面对大规模算例时优化效果不佳。

目前，该类复杂优化问题的求解方法主要可分为3类，即精确求解、构造启发式和智能优化方法。精确求解方法在求解小规模问题时可以快速得到最优解，对大中规模问题，因其时间和空间复杂度随问题维度的增加计算量呈指数增长，导致“维数灾难”；构造启发式方法基于调度规则快速构造可行解，很难保证解的质量；智能优化方法基于特定操作通过迭代搜索不断改善解的质量，具备适用性广、结果鲁棒及全局优化等特点，但易陷于局部优解。面对较为复杂的问题，往往会采用3者嵌套设计优化方法[14]。

1 问题描述

一般纸板生产模式为多规格卷材高速切割模式下排样下料模式，如图1所示。该模式定义为：在多种规格(宽度)的卷材集上排布出满足订单集要求的图案集，使得原料使用量最小。各订单所需纸板的基础参数为宽度，长度和需求量。图案的宽度等于选用的卷材宽度，长度为其内排布条带长度的最大值。

图1 纸板切割一般工艺示意Figure 1 General process illustration of cutting paperboards

图案在切割时，切裁机器先用纵切刀将卷材切成条带，后由横切刀将条带加工成相应的工件。横切刀对条带进行周期性裁剪，故任一条带仅能排布一种订单。考虑到实际纸板生产时的压楞需求，本文模型中纸板长宽不能互换生产。

纵横切刀的数量与图案排样的复杂度有关联。由于纸板在成型过程中幅宽边缘的定量不稳定，因此卷材在纵切时需要切边。考虑切边，故图案可排条带数等于纵切刀数量减1；横切刀数量为任一图案内能够排布的订单数量上限。

2 模型

基于纸板生产工艺构建数学模型，其中涉及到的变量或常量符号如下：

K为卷材集合(各卷材标记为k);

I为订单集合(各订单标记为i)；

P为有序图案集合(各图案标记为p)；

B和J分别为切裁机器的纵切刀数和横切刀数；

Wk为卷材k的宽度；

li,wi和di分别为订单i的长度、宽度与需求量;

Lp为图案p的长度；

nip为决策变量，订单i在图案p上排布的纸板数量;

cip为决策变量，订单i在图案p上排布的条带数;

hpk为决策变量，若图案p选用卷材k，则取值为1，否则为0;

xip为中间变量，若订单i在图案p上排布则取值为1，否则为0;

rip为中间变量，若订单i在图案p正在加工时处于已生产未完成的状态，则取值为1，否则为0;

C为图案平均置换损失(表示为原料损失)。

2.1 基础模型

一般纸板排样下料数学模型可以表述为：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

nip,cip∈N,hpk∈{0,1}。

(8)

该模型将一般纸板排样问题转化为关于(nip,cip,hpk)3类变量的决策问题，综合优化原料使用量和图案置换次数，如式(1)所示，其中图案置换损失被转用原料用量表示。式(2)约束所得方案必须满足订单足量生产的要求;式(3)限制图案内条带宽度之和不能大于其选用卷材的宽度；式(4)～(6)为切纸机横、纵切刀数导致的排样限制。对于有B个纵切刀的切割机，其可切割条带数为B+1;由于外侧2个条带被用于修边，故图案内排布条带数不应大于B-1；由于一个横切刀同时切割属于一个订单的所有条带，故其数量决定图案内的订单上限；式(7)表明了图案的长度计算方法。式(8)为模型决策变量的取值范围。

2.2 暂存区约束(图案顺序强约束)

纸板生产过程中存在一类限制订单多图案排布和图案顺序的约束。每个横切刀座附近都存在一个纸板暂存区，其在同一时间仅可存放一个订单的纸板，每当某个订单所需纸板全部被满足，暂存区清空并可容纳下一个订单[15]。

增加式(9)～(10)，保证在任何阶段，当前已进行但未完成的订单的数量不应大于暂存区数量，即横切刀数。δ表示图案p正在加工的状态，δ∈(0,1)。

(9)

(10)

3 算法设计

3.1 算法总框架

针对模型特点，算法将暂存区虚拟为排样池，设计2层嵌套算法(Two-layer nesting algorithm，TNA)。上层为下料方案层，负责决策订单放入排样池的顺序；下层为图案排样层，负责生成具体的排样图案。中间采用排样池连接。

3.2 排样池

为了满足暂存区存放限制，设计排样池用于放置预排样的订单，其容量等于暂存区数量J。在一个图案完成排布并结单一定数量的订单后，这些订单会被移出排样池，同时一些新订单会被添加进去，始终保持排样池内在制订单数等于其容量。

排样池的设计，不仅将模型约束转化为算法框架约束，简化了保证可行解的计算复杂度，同时也作为2层算法数据交互的通道，将下料方案优化需要的算法能力拆分，有利于提高算法性能，减少运算资源需求。

3.3 排样方式生成方法(图案排样层)

为了便于下料方案层迭代优化，该层采用2阶段精确算法。

首先求解宽度方向上条带排布样式，其为一维下料等同问题。受排样池的作用，每个图案的条带排布需要决策的变量数为J+|K|，且无需考虑横切刀数的限制。故采用如下线性规划方法：

(11)

s.t.

(12)

(13)

在此基础上决策每个条带上排布的纸板数量，该数量最终决定各条带的长度。两两条带的长度差距越大，其造成的材料浪费也就越大(称为段差损失)。在相关文献中，该部分往往采用“最小段差损失原则”[16]作为纸板数量决策依据。

在本模型中，排样方式综合考虑暂存区存储规则和切换图案的准备活动损耗，需要满足：每个图案至少存在一个订单结单。因而模型内存在一类权衡：

对于订单集|I|,若每个图案内结单一个订单，则共有|P|个图案需要处理。在此基础上，1个图案中的订单结单数每多1个，下料方案所需的准备活动次数|P|也就相应减1。因此，段差损失和置换损失存在一定程度的资源互斥。为了减少图案集的规模，一些“快要生产完”的订单可能不会选择在段差最小的时候切割订单，反之亦然。

3) 步骤3。计算/更新当前图案的长度：

4) 步骤4。计算对当前订单(r)条带采用“最小段差损失原则”截断后减少的段差损失R：

5) 步骤5。如果R>C×结单订单减少数量，更新截断条带上排布的纸板数量：

3.4 订单下料顺序优化算法(下料方案层)

借助排样池和排样方式2阶段精确求解算法，在下料方案层仅需决策放入排样池的顺序，其所需决策变量数为|I|。

该部分采用Wang等[17]提出的单链编码遗传算法求解。作为一种群体智能算法，其具备并行、高效和全局搜索等优点。根据已有研究，遗传算法在处理规模中等、编码结构简单的问题时具备稳定且优异的表现。受益于嵌套优化结构，该部分已满足上述2点特征。

染色体设计采用单链实值编码模式，长度等于|I|，各基因取值为[1,|I|]，染色体规模N=100。

4 实验分析

4.1 仿真环境、基础数据及分析指标

本算法采用Eclipse编程工具，基于JAVA语言实现。测试计算机为intel i7-6700HQ，主频2.6 GHz，内存16 GiB。

对比算法为：①VLGA——Mellouli等[13]539于2019年提出的矩阵结构变长遗传算法；②VCIA——黎凤洁等[10]69于2020年提出的价值修正迭代算法，采用遗传算法分配图案宽度以满足算法要求。

仿真算例中，订单参数(wi，li，di)/(mm，mm，片)分别为在区间[150,800]，[500,2 000]，[100,8 000]的离散平均随机输入变量，卷材宽度Wk可选值为2 000，2 100，2 200，2 300，2 400和2 500 mm。

算法结果评价指标为原料利用率：

式中：QTNA为本文算法的原料利用率；QVLGA/VCIA为对比算法的原料利用率。

4.2 仿真结果对比

在J=3，|I|=500,C=500的算例下，各算法随迭代次数的变化如图2所示。

图2 原料利用率随迭代次数变化对比Figure 2 Comparison of change of raw material utilization with iterations

VLGA算法采用矩阵结构变长编码。将全部决策变量交由算法寻优。解空间过于庞大，不仅初始解质量难以提高，同时收敛速度缓慢，最终解质量不稳定，难以处理大规模调度问题。

本文算法与VCIA算法均在遗传算法的框架下嵌套算法求解最优排样方式，因而可以在初始解中便获得较优的下料方案解。其中，本文算法初始解较优的原因在于其采用线性规划算法同时求得最优的图案宽度分配，而VCIA算法需要通过上层迭代算法分配图案宽度，解空间相对较大。

该算例中本文算法在30代达到稳定，VCIA算法在65代稳定。迭代结束时本文算法利用率为99.18%，VCIA算法为99.04%，Δ=+0.14%，本文算法结果较优。

在J=3，|I|=500，迭代次数E=100的算例下，本文算法与VCIA算法在不同平均置换损失C的结果对比如表1所示。

表1 不同平均置换损失下算法结果对比Table 1 Comparison of results under different average changeover losses

当C=0时，2种算法均采用“最小段差损失原则”生成排样方式，本文算法受益于解空间规模的缩小，存在+0.12%的优势。

随着平均置换损失的增大，2种算法获得下料方案的原料利用率均在减小，但算法间的优化差距逐渐增大。由于VCIA算法不包含考虑置换损失的优化模块，故可以看出，本文算法可以有效权衡置换损失与段差损失，以获取更优的结果。

5 结语

课题组针对一类带图案顺序强约束的一般纸板排样下料问题，提出了基于排样池交互的嵌套优化算法。将模型强约束关系转化为算法特殊结构，并利用其特征缩减低质量解空间，通过实例的数据对比，证明了课题组所提算法的高寻优能力和稳定性。另外，条带截断启发式规则也被证明能有效综合置换损失与段差损失，寻求全局优解。本研究算法对纸板制造业流程优化具有重要的参考价值。在未来的工作中，将会对其它如皮革加工等类似行业的排样下料问题开展进一步的研究。