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

付常洋
机构：北京工商大学计算机与信息工程学院，食品安全大数据技术北京市重点实验室，北京，100048
作者简介：付常洋先生，在读硕士研究生；主要从事计算机视觉、图像处理的研究。
×
王瑜
机构：北京工商大学计算机与信息工程学院，食品安全大数据技术北京市重点实验室，北京，100048
角色：通讯作者
作者简介：王瑜，副教授；主要从事图像处理与模式识别的研究。
×
刘茜
机构：北京工商大学计算机与信息工程学院，食品安全大数据技术北京市重点实验室，北京，100048
×
邢素霞
机构：北京工商大学计算机与信息工程学院，食品安全大数据技术北京市重点实验室，北京，100048
×
肖洪兵
机构：北京工商大学计算机与信息工程学院，食品安全大数据技术北京市重点实验室，北京，100048
×

北京工商大学计算机与信息工程学院，食品安全大数据技术北京市重点实验室，北京，100048

中图分类号: TS734+.7

DOI:10.11980/j.issn.0254-508X.2019.03.010

Optimization Algorithm for Production Scheduling of Reel Slitting Based on Nonlinear Integer Programming

FU Changyang
Affiliation：Beijing Key Lab of Food Safety Big Data Technology, School of Computer and Information Engineering, Beijing Technology and Business University, Beijing, 100048* E-mail: wangyu@btbu.edu.cn
×
WANG Yu
Affiliation：Beijing Key Lab of Food Safety Big Data Technology, School of Computer and Information Engineering, Beijing Technology and Business University, Beijing, 100048* E-mail: wangyu@btbu.edu.cn
Role：Corresponding author
×
LIU Xi
Affiliation：Beijing Key Lab of Food Safety Big Data Technology, School of Computer and Information Engineering, Beijing Technology and Business University, Beijing, 100048* E-mail: wangyu@btbu.edu.cn
×
XING Suxia
Affiliation：Beijing Key Lab of Food Safety Big Data Technology, School of Computer and Information Engineering, Beijing Technology and Business University, Beijing, 100048* E-mail: wangyu@btbu.edu.cn
×
XIAO Hongbing
Affiliation：Beijing Key Lab of Food Safety Big Data Technology, School of Computer and Information Engineering, Beijing Technology and Business University, Beijing, 100048* E-mail: wangyu@btbu.edu.cn
×

Beijing Key Lab of Food Safety Big Data Technology, School of Computer and Information Engineering, Beijing Technology and Business University, Beijing, 100048* E-mail: wangyu@btbu.edu.cn

CLC: TS734+.7

DOI:10.11980/j.issn.0254-508X.2019.03.010

全文
图表
评论
参考文献
作者
出版信息

参考文献 1

KallrathJ, RebennackS, KallrathJ, 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

CorreiaM H, FerreiraJ S. Reel and sheet cutting at a paper mill[J]. Computers & Operations Research, 2004, 31(8): 1223.

查找原文

参考文献 3

KeskinocakP, WuF, GoodwinR, et al. Scheduling Solutions for the Paper Industry.[J]. Operations Research, 2002, 50(2): 249.

查找原文

参考文献 4

PoltroniereS C, PoldiK C, ToledoF 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

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

JinFujiang, WangHui, LiPing. Lexicographically Stratified Programming for Batch Cooking Process[J]. Transactions of China Pulp and Paper, 2002, 17(1): 86.

查找原文

参考文献 6

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

TUJianshun, YANGChunjie, LIPing, et al. A Genetic Algorithm Based on Variable Length Coding for Paper Roll Cutting Problem[J]. China Pulp & Paper, 2003, 22(7):24.

查找原文

参考文献 7

杨春节. 基于遗传算法的造纸企业优化排产方法研究[J]. 中国造纸,2005, 24(10): 32.

YANGChunjie. Research on Optical Scheduling in Papermaking Process Based on Genetic Algorithm[J]. China Pulp & Paper, 2005,24(10):32.

查找原文

参考文献 8

PoltroniereS C, AraujoS A, PoldiK C, et al. Optimization of an Integrated Lot Sizing and Cutting Stock Problem in the Paper Industry[J]. Tema, 2016, 17(3):305.

查找原文

参考文献 9

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

CaiYun, YangChunjie, LiPing. 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.

查找原文

参考文献 10

于战科, 倪明放, 汪泽焱,等. 整数线性规划的改进分支定界算法[J]. 计算机应用, 2011, 31(s2):36.

YuZhan-ke, NiMing-fang, WangZe-yan, et al. Revised branch-and-bound algorithm for integer linear programming[J]. Journal of Computer Applications, 2011, 31(s2):36.

查找原文

参考文献 11

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

GaoPei-wang, FengQuan-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.

查找原文

参考文献 12

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

NiRen-yuan, FengJian-hu. Linear Integer Programming Model and Method for Solving Car-carrier Loading Problems[J]. Numerical Mathematics A Journal of Chinese Universities, 2017(3):200.CPP

查找原文

摘要

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

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.

关键词

卷纸分切；非线性整数规划；优化模型

Keywords

reel slitting; nonlinear integer programming; model optimization

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

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

1 原理及模型
1
利用非线性整数规划解决卷纸切割排产优化问题是一个建模求解的过程。假设订单中要求卷纸包括n种规格l1、l2、…、ln，每种规格对应的数量为b1、b2、…、bn，且该批次待切割大卷原纸的规格为L和数量B。通过穷举法可以找出所有符合切剩纸边分切机一次性切割段数均满足规定的可行排刀组合。记求得可行排刀组合数量为m，每一种可行切割方案对应每种规格的小卷数量为ai,j(i=1,2,…,n;j=1,2,…,m)，每一种可行切割方案重复切割次数为xj。由此可得一个多元非齐次线性方程组（1）。
∑j=1ma1,jxj=b1∑j=1ma2,jxj=b2…∑j=1man,jxj=bn∑j=1mxj=Bxj∈X={x|0≤xj≤B,xj为整数}
(1)
求其整数解即可得到满足订单要求的排产方案^[9]。但正常解方程存在以下两个问题，首先线性方程组的解可能不唯一，且解不一定全为整数，与实际情况相违背，实际切割方案中切割长卷纸重复次数必须为整数；另外，方程组的解即便全部为整数，也有可能不是最优解，不能达到尽可能减少完成订单的排刀步骤的目的。
为了解决上述问题，在求解过程中，采用整数规划^[10,11,12]方法对上述线性方程组进行优化。以切换排刀组合步骤数最少为目标函数，以订单规格和数量为约束条件，建立非线性整数规划模型，再对模型进行求解。因为待切割原纸的数量B固定不变，即：
∑j=1mxj= B
(2)

所以可以选定非线性目标函数为式（3）。

max∑j=1mxj2
(3)
即xj中非0的个数最少，即切换排刀方案步骤数最少，则非线性整数归化模型为式（4）。
max∑j=1mxj2
s.t.∑j=1ma1,jxj=b1∑j=1ma2,jxj=b2…∑j=1man,jxj=bn∑j=1mxj=Bxj∈X={x|0≤xj≤B,xj为整数}
(4)
2 模型优化
2
2.1 补充备用规格
2.1
工厂生产中，当实际订单代入上面的非线性整数规划模型时，常常会出现无解的情况，无法得出排产方案。此时需要补充一些备用规格，以便于充分利用待切割原纸，得出最优排产方案。此外，补充备用规格卷纸能有效减少切纸剩余料头，避免资源的浪费。
补充备用规格的情况是指当未补充备用尺寸时，上述模型无解，且订单中要求的卷纸总长度小于被切割长卷纸总长度，即
∑i=1nlibi<LB
(5)
在此情况下需要人为添加k个备用规格d1、d2、⋯,dk，如此可获得更多的可行排刀组合，以便于将全部待切割长卷纸切割完毕。备用规格可根据以下原则进行补充：当订单要求中的小规格卷纸较多时，多补充大规格卷纸；当订单要求中的大规格卷纸较多时，多补充小规格卷纸。
假设添加k个备用规格后，获得可行排刀组合的数量为m'，每一种可行切割方案中对应每种规格的小卷数量为a'i,j(i=1,2,…,n+k;j=1,2,…,m)，每一种可行切割方案重复切割次数为变量x'j。同样以切换排刀方案步骤数最少为目标函数，以订单中规格和数量为约束条件建立非线性整数规划模型，具体形式见式（6）。
max∑j=1m'(x')j2
s.t.∑j=1m'a'1,jx'j=b1∑j=1m'a'2,jx'j=b2…∑j=1m'a'n,jx'j=bn∑j=1m'x'j=Bx'j∈X={x|0≤x'j≤B,x'j为整数}
(6)
2.2 限定最大计算时间
2.2
在纸厂实际运作中，要求尽可能降低卷纸切割机的停歇时间，以便保持尽可能高的生产效率，而实际订单计算过程中存在计算时间过长可能，让卷纸切割机长时间的等待最优排产方案是不经济的。为维持较高的生产效率，在满足客户订单要求的情况下，可以人为限定一个最大计算时间，以便卷纸切割机不间断运作。
如果提出算法在限定时间内得到全局最优解，则输出最优排产方案；如果提出算法在限定时间内没有得到全局最优解，则找到在限定时间截止时得到的所有解中的最优解，输出最优排产方案；如果在限定时间内未求出可行解，则调整订备用规格，重新开始计算，直至获得最终方案。
3 建立图形化人机界面系统
3
为了让本课题提出的算法更好地应用于实际生产中，开发了一个图形化人机界面系统，系统执行流程包括以下步骤：第一步，确定客户订单中的卷纸规格与数量；第二步，确定待切割的全部原纸规格与数量；第三步，补充一些备用规格来充分利用原纸；第四步，限定系统最大运行时间；第五步，以切换排刀组合步骤数最少为目标建立非线性整数规划模型；第六步，在限定时间内用Gurobi 8.0.0求解器求解非线性整数规划问题；第七步，如果第六步在限定时间内得到全局最优解，则输出最优排产方案，如果第六步在限定时间内没有得到全局最优解，则找到在限定时间截止时得到的所有解中的最优解，输出最优排产方案，如果第六步未求出可行解，则返回第三步补充备用规格，继续接下来的步骤，直到得出最终方案。具体如图1所示。
图1 系统流程图
人机界面整体分为7个部分：规定尺寸输入区、规定卷数输入区、长卷纸规格输入区、备用尺寸输入区、最大计算时长输入区、排刀方案输出区以及备用尺寸及数量输出区。操作时首先根据订单需求将规定尺寸、规定卷数、长卷纸尺寸、长卷纸数量、长卷纸质量、备用尺寸、最大计算时长分别键入相应窗口，确认无误后点击“输入完成并计算”按钮，待系统提示计算完毕后，再点击“查询计算结果”按钮，便可在排刀方案输出区内查看最优卷纸分切排产方案，在备用尺寸及数量输出区内查看最优方案中备用尺寸的使用情况。具体如图2所示。
图2 人机界面

4 仿真实例

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

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

表1 客户订单需求

原纸宽度(L)/mm	6300
原纸单位质量(W)/t	5
原纸数量(B)/卷	75
小卷产品(Ci)	C1	C2	C3	C4	C5	C6	C7	C8	C9	C10	C11	C12	C13	C14	C15	C16	C17(备用)	C18(备用)	C19(备用)	C20(备用)
小卷宽度(li)/mm	605	665	725	785	787	800	850	885	900	1025	1200	1250	1300	1450	1574	1920	850	900	1400	1800
小卷数量(bi)/卷	24	151	13	15	81	10	50	48	5	21	6	4	4	26	10	9

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

图3 人机界面输入输出图

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

表2 最优排产方案

排产组合	总长/mm	卷数
1250,1250,1250,1250,1300	6300	1
605,605,605,885,1200,1200,1200	6300	1
605,605,665,785,787,885,1920	6252	9
605,725,785,785,885,1200,1300	6285	3
665,665,665,787,850,850,1800	6282	25
665,665,725,885,885,885,1574	6284	10
665,665,787,787,1025,1450,900	6279	21
665,787,800,800,885,900,1450	6287	5

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

5 结语
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.
  CPP

基本信息

DOI:10.11980/j.issn.0254-508X.2019.03.010

中图分类号: TS734+.7

文献标识码: A

引用信息

付常洋,王瑜,刘茜等.基于非线性整数规划的卷纸分切排产方案优化算法研究[J].中国造纸,2019,38(03):56-60.

FU Changyang,WANG Yu,LIU Xi,et al.Optimization Algorithm for Production Scheduling of Reel Slitting Based on Nonlinear Integer Programming[J].China Pulp & Paper,2019,38(03):56-60.

基金信息

国家自然基金面上项目(No. 61671028)；北京市自然科学基金面上项目(No.4162018)；国家重大科技研发子课题(No. ZLJC6 03-5-1)；北京工商大学校级两科培育基金项目(No. 19008001270)。