基于非线性整数规划的卷纸分切排产方案优化算法研究

付常洋 王瑜 刘茜 邢素霞 肖洪兵

摘要：为了减少造纸厂卷纸分切时因排产方案不合理而产生的人力、能源、时间等资源的浪费，以降低企业生产成本，提出了一种基于非线性整数规划的卷纸分切排产方案优化算法。该算法思想包括：首先根据客户订单需求建立数学模型，其次对模型进行优化，有效地提高求解效率，最后用非线性整数规划的方法求解出最优排刀方案。实验结果表明，该算法可以有效地获得卷纸分切的最优排产方案，并可用于实际卷纸生产过程中。

关键词：卷纸分切;非线性整数规划;优化模型

中图分类号：TS734⁺.7    文献标识码：A     DOI：10.11980/j.issn.0254-508X.2019.03.010

Abstract： In this paper a optimization algorithm for production scheduling of reel slitting based on nonlinear integer programming was described in order to reduce the wastes of labor force， time and other resources caused by the unreasonable scheduling scheme， and then reduce the production cost of the enterprise. The idea of this optimization algorithm included： firstly， the mathematical model was built according to the customer's requirement. Then the model was optimized to improve the solution efficiency. Finally， the nonlinear integer programming method was used to solve the above model and to find the optimal production scheduling scheme. The experimental results showed that the optimal scheduling scheme was able to be obtained effectively using the proposed algorithm for reel slitting， and this method could be used in the actual production process.

Key words： reel slitting; nonlinear integer programming; model optimization

造紙厂卷纸分切业务订单具有品种繁杂、规模庞大等特点，传统的排产方案由工人凭借经验并反复验证所得，造成人力、能源、时间上的极大浪费，大大增加了企业的生产成本，不利于造纸行业的可持续发展^[1]。利用机器学习算法和计算机相关技术优化卷纸分切排产方案是节约纸厂生产成本、统筹生产的重要手段，其要求在一定规格和一定数量的大卷原纸上切割出符合订单要求规格和数量的小纸卷，且要求切剩纸边、分切机一次性切割刀数都在规定范围内，避免造成卷纸资源和人力资源的浪费^[2]。此外，由于卷纸分切机启动和停机时间较长、生产流程中调整刀片步骤繁琐以及设备清洗成本高等因素，使得减少排刀组合的切换次数成为优化卷纸分切排产方案的重点关注问题之一。

目前，国内外常用于解决卷纸分切优化问题的算法主要有两大类：第一类为启发式算法，如模拟退火算法、粒子群算法、遗传算法等^[3-7];第二类为精确算法，如分支界定法、割平面法等^[8]。但由于启发式算法无法得到问题的全局最优解，甚至有些情况下只能得到一个较差的可行解，无法满足纸厂的实际生产需求。精确算法是近年来提出的解决整数规划问题的有效方法，但在卷纸分切排产这种大规模问题背景下存在算法效率问题，其求解时间与问题规模呈指数关系，当订单中产品规格种类和数量增加时，模型中的变量会以指数关系急剧增加，使得一般的精确算法无法再合理时间内得到最优解。针对上述缺陷，本课题提出一种包含二次目标函数的基于非线性整数规划的卷纸分切排产方案优化算法，该算法以切换排刀方案步骤数最少为目标函数，以订单中卷纸规格和数量为约束条件建立数学优化模型，再对模型进行优化求解。该模型从非线性整数规划的角度出发，将复杂的排产过程以数学模型的形式展现出来，进行合理优化，并在有限时间内得出最优的排产方案，以提高造纸厂的卷纸分切效率和降低生产成本。

求其整数解即可得到满足订单要求的排产方案^[9]。但正常解方程存在以下两个问题，首先线性方程组的解可能不唯一，且解不一定全为整数，与实际情况相违背，实际切割方案中切割长卷纸重复次数必须为整数;另外，方程组的解即便全部为整数，也有可能不是最优解，不能达到尽可能减少完成订单的排刀步骤的目的。

为了解决上述问题，在求解过程中，采用整数规划^[10-12]方法对上述线性方程组进行优化。以切换排刀组合步骤数最少为目标函数，以订单规格和数量为约束条件，建立非线性整数规划模型，再对模型进行求解。因为待切割原纸的数量B固定不变，即：

2.2 限定最大计算时间

在纸厂实际运作中，要求尽可能降低卷纸切割机的停歇时间，以便保持尽可能高的生产效率，而实际订单计算过程中存在计算时间过长可能，让卷纸切割机长时间的等待最优排产方案是不经济的。为维持较高的生产效率，在满足客户订单要求的情况下，可以人为限定一个最大计算时间，以便卷纸切割机不间断运作。

如果提出算法在限定时间内得到全局最优解，则输出最优排产方案;如果提出算法在限定时间内没有得到全局最优解，则找到在限定时间截止时得到的所有解中的最优解，输出最优排产方案;如果在限定时间内未求出可行解，则调整订备用规格，重新开始计算，直至获得最终方案。

3 建立图形化人机界面系统

为了让本课题提出的算法更好地应用于实际生产中，开发了一个图形化人机界面系统，系统执行流程包括以下步骤：第一步，确定客户订单中的卷纸规格与数量;第二步，确定待切割的全部原纸规格与数量;第三步，补充一些备用规格来充分利用原纸;第四步，限定系统最大运行时间;第五步，以切换排刀组合步骤数最少为目标建立非线性整数规划模型;第六步，在限定时间内用Gurobi 8.0.0求解器求解非线性整数规划问题;第七步，如果第六步在限定时间内得到全局最优解，则输出最优排产方案，如果第六步在限定时间内没有得到全局最优解，则找到在限定时间截止时得到的所有解中的最优解，输出最优排产方案，如果第六步未求出可行解，则返回第三步补充备用规格，继续接下来的步骤，直到得出最终方案。具体如图1所示。

人机界面整体分为7个部分：规定尺寸输入区、规定卷数输入区、长卷纸规格输入区、备用尺寸输入区、最大计算时长输入区、排刀方案输出区以及备用尺寸及数量输出区。操作时首先根据订单需求将规定尺寸、规定卷数、长卷纸尺寸、长卷纸数量、长卷纸质量、备用尺寸、最大计算时长分别键入相应窗口，确认无误后点击“输入完成并计算”按钮，待系统提示计算完毕后，再点击“查询计算结果”按钮，便可在排刀方案输出区内查看最优卷纸分切排产方案，在备用尺寸及数量输出区内查看最优方案中备用尺寸的使用情况。具体如图2所示。

4 仿真实例

造纸企业实际排产主要依照客户订单要求进行，客户订单一般有品种、规格、质量和数量的要求。另外如果订单无解或不能恰好将待切割长卷纸分切完毕，就需要补充一部分备用尺寸。将客户订单要求的规格和数量输入到非线性整数规划模型，必要时补充备用尺寸、限定最大运行时间，就能获得最优排产方案。

为了验证本课题提出方法的可行性和有效性，根据一个规格多样、纸机产量大的俄卡纸厂的订单需求进行了实验。实例中客户订单具体要求如表1所示。

将订单输进人机界面后，根据实际需求选定最大时长为30 min，点击“输入完成并计算”按钮，待系统提示计算完毕后再点击“查询计算结果”按钮，便可在下方排刀方案输出区内查看最优卷纸分切排产方案，在备用尺寸及数量输出区内查看最优方案中备用尺寸的使用情况。具体如图3所示。

得出该订单的最优排产方案如表2所示。

该实例仅需切换排刀组合8次就可完成客户订单要求，极大降低了分切机切换成本。订单中的小卷纸总长相当于65卷大卷纸，但客户要求将75卷待切割大卷纸全部分切完毕，故使用备用规格900 mm的小卷纸21卷、1800 mm的小卷纸25卷，以达到客户订单要求。

5 结 语

本课题针对造纸厂长卷纸分切排产问题进行细致分析，提出一种基于非线性整数规划的卷纸分切排产方案优化算法，该算法首先根据客户订单需求建立数学模型，其次对模型进行优化，有效地提高求解效率，最后用非线性整数规划的方法求解出最优排刀方案。该算法可应用于不同规格、数量的客户订单，综合考虑了模型求解的各种情况，可灵活调整计算时间和备用尺寸，更符合纸厂生产过程中的实际需求。通过該模型确定排产策略，能有效提高造纸厂卷纸分切效率，节省原材料和人力资源，有利于造纸行业的可持续发展。

参考文献

[1] Kallrath J， Rebennack S， Kallrath J， et al. Solving real-world cutting stock-problems in the paper industry： Mathematical approaches， experience and challenges[J]. European Journal of Operational Research， 2014， 238（1）： 374.

[2] Correia M H， Ferreira J S. Reel and sheet cutting at a paper mill[J]. Computers & Operations Research， 2004， 31（8）： 1223.

[3] Keskinocak P， Wu F， Goodwin R， et al. Scheduling Solutions for the Paper Industry.[J]. Operations Research， 2002， 50（2）： 249.

[4] Poltroniere S C， Poldi K C， Toledo F M B， et al. A coupling cutting stock-lot sizing problem in the paper industry[J]. Annals of Operations Research， 2008， 157（1）： 91.

[5] Jin Fujiang， Wang Hui， Li Ping. Lexicographically Stratified Programming for Batch Cooking Process[J]. Transactions of China Pulp and Paper， 2002， 17（1）： 86.

金福江， 王 慧，李 平. 间歇蒸煮过程的分层多目标优化[J]. 中国造纸学报， 2002， 17（1）：86.

[6] TU Jianshun， YANG Chunjie， LI Ping， et al. A Genetic Algorithm Based on Variable Length Coding for Paper Roll Cutting Problem[J]. China Pulp & Paper， 2003， 22（7）：24.

屠建顺， 杨春节， 李 平，等. 基于变长编码的遗传算法在纸卷切割中的应用[J]. 中国造纸， 2003， 22（7）：24.

[7] YANG Chunjie. Research on Optical Scheduling in Papermaking Process Based on Genetic Algorithm[J]. China Pulp & Paper， 2005，24（10）：32.

杨春节. 基于遗传算法的造纸企业优化排产方法研究[J]. 中国造纸，2005， 24（10）： 32.

[8] Poltroniere S C， Araujo S A， Poldi K C， et al. Optimization of an Integrated Lot Sizing and Cutting Stock Problem in the Paper Industry[J]. Tema， 2016， 17（3）：305.

[9] Cai Yun， Yang Chunjie， Li Ping. Study of Optimal Scheduling Synthesized Slitting and Inventory of Paper Rolls in Papermaking Process[J]. Transactions of China Pulp and Paper， 2003， 18（2）： 167.

蔡 韵， 杨春节， 李 平. 造纸生产纸卷分切与库存综合优化排产研究[J]. 中国造纸学报， 2003， 18（2）：167.

[10] Yu Zhan-ke， Ni Ming-fang， Wang Ze-yan， et al. Revised branch-and-bound algorithm for integer linear programming[J]. Journal of Computer Applications， 2011， 31（s2）：36.

于戰科， 倪明放， 汪泽焱，等. 整数线性规划的改进分支定界算法[J]. 计算机应用， 2011， 31（s2）：36.

[11] Gao Pei-wang， Feng Quan-xi. Combining a Cutting-Bound Method and the Integral Branch Principle for Solving Integer Linear Programming[J]. Mathematics in Practice and Theory， 2004， 34（4）： 109.

高培旺， 封全喜. 切割定界与整数分枝结合求解整数线性规划[J]. 数学的实践与认识， 2004， 34（4）：109.

[12] Ni Ren-yuan， Feng Jian-hu. Linear Integer Programming Model and Method for Solving Car-carrier Loading Problems[J]. Numerical Mathematics A Journal of Chinese Universities， 2017（3）：200.

倪任远， 封建湖. 轿运车配载问题的整数线性规划模型及解法[J]. 高等学校计算数学学报， 2017（3）： 200.

（责任编辑：董凤霞）