基于非線性整數(shù)規(guī)劃的卷紙分切排產(chǎn)方案優(yōu)化算法研究

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

摘要：為了減少造紙廠卷紙分切時(shí)因排產(chǎn)方案不合理而產(chǎn)生的人力、能源、時(shí)間等資源的浪費(fèi)，以降低企業(yè)生產(chǎn)成本，提出了一種基于非線性整數(shù)規(guī)劃的卷紙分切排產(chǎn)方案優(yōu)化算法。該算法思想包括：首先根據(jù)客戶訂單需求建立數(shù)學(xué)模型，其次對(duì)模型進(jìn)行優(yōu)化，有效地提高求解效率，最后用非線性整數(shù)規(guī)劃的方法求解出最優(yōu)排刀方案。實(shí)驗(yàn)結(jié)果表明，該算法可以有效地獲得卷紙分切的最優(yōu)排產(chǎn)方案，并可用于實(shí)際卷紙生產(chǎn)過程中。

關(guān)鍵詞：卷紙分切;非線性整數(shù)規(guī)劃;優(yōu)化模型

中圖分類號(hào)：TS734⁺.7 ???文獻(xiàn)標(biāo)識(shí)碼：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

造紙廠卷紙分切業(yè)務(wù)訂單具有品種繁雜、規(guī)模龐大等特點(diǎn)，傳統(tǒng)的排產(chǎn)方案由工人憑借經(jīng)驗(yàn)并反復(fù)驗(yàn)證所得，造成人力、能源、時(shí)間上的極大浪費(fèi)，大大增加了企業(yè)的生產(chǎn)成本，不利于造紙行業(yè)的可持續(xù)發(fā)展^[1]。利用機(jī)器學(xué)習(xí)算法和計(jì)算機(jī)相關(guān)技術(shù)優(yōu)化卷紙分切排產(chǎn)方案是節(jié)約紙廠生產(chǎn)成本、統(tǒng)籌生產(chǎn)的重要手段，其要求在一定規(guī)格和一定數(shù)量的大卷原紙上切割出符合訂單要求規(guī)格和數(shù)量的小紙卷，且要求切剩紙邊、分切機(jī)一次性切割刀數(shù)都在規(guī)定范圍內(nèi)，避免造成卷紙資源和人力資源的浪費(fèi)^[2]。此外，由于卷紙分切機(jī)啟動(dòng)和停機(jī)時(shí)間較長、生產(chǎn)流程中調(diào)整刀片步驟繁瑣以及設(shè)備清洗成本高等因素，使得減少排刀組合的切換次數(shù)成為優(yōu)化卷紙分切排產(chǎn)方案的重點(diǎn)關(guān)注問題之一。

目前，國內(nèi)外常用于解決卷紙分切優(yōu)化問題的算法主要有兩大類：第一類為啟發(fā)式算法，如模擬退火算法、粒子群算法、遺傳算法等^[3-7];第二類為精確算法，如分支界定法、割平面法等^[8]。但由于啟發(fā)式算法無法得到問題的全局最優(yōu)解，甚至有些情況下只能得到一個(gè)較差的可行解，無法滿足紙廠的實(shí)際生產(chǎn)需求。精確算法是近年來提出的解決整數(shù)規(guī)劃問題的有效方法，但在卷紙分切排產(chǎn)這種大規(guī)模問題背景下存在算法效率問題，其求解時(shí)間與問題規(guī)模呈指數(shù)關(guān)系，當(dāng)訂單中產(chǎn)品規(guī)格種類和數(shù)量增加時(shí)，模型中的變量會(huì)以指數(shù)關(guān)系急劇增加，使得一般的精確算法無法再合理時(shí)間內(nèi)得到最優(yōu)解。針對(duì)上述缺陷，本課題提出一種包含二次目標(biāo)函數(shù)的基于非線性整數(shù)規(guī)劃的卷紙分切排產(chǎn)方案優(yōu)化算法，該算法以切換排刀方案步驟數(shù)最少為目標(biāo)函數(shù)，以訂單中卷紙規(guī)格和數(shù)量為約束條件建立數(shù)學(xué)優(yōu)化模型，再對(duì)模型進(jìn)行優(yōu)化求解。該模型從非線性整數(shù)規(guī)劃的角度出發(fā)，將復(fù)雜的排產(chǎn)過程以數(shù)學(xué)模型的形式展現(xiàn)出來，進(jìn)行合理優(yōu)化，并在有限時(shí)間內(nèi)得出最優(yōu)的排產(chǎn)方案，以提高造紙廠的卷紙分切效率和降低生產(chǎn)成本。

求其整數(shù)解即可得到滿足訂單要求的排產(chǎn)方案^[9]。但正常解方程存在以下兩個(gè)問題，首先線性方程組的解可能不唯一，且解不一定全為整數(shù)，與實(shí)際情況相違背，實(shí)際切割方案中切割長卷紙重復(fù)次數(shù)必須為整數(shù);另外，方程組的解即便全部為整數(shù)，也有可能不是最優(yōu)解，不能達(dá)到盡可能減少完成訂單的排刀步驟的目的。

為了解決上述問題，在求解過程中，采用整數(shù)規(guī)劃^[10-12]方法對(duì)上述線性方程組進(jìn)行優(yōu)化。以切換排刀組合步驟數(shù)最少為目標(biāo)函數(shù)，以訂單規(guī)格和數(shù)量為約束條件，建立非線性整數(shù)規(guī)劃模型，再對(duì)模型進(jìn)行求解。因?yàn)榇懈钤埖臄?shù)量B固定不變，即：

2.2 限定最大計(jì)算時(shí)間

在紙廠實(shí)際運(yùn)作中，要求盡可能降低卷紙切割機(jī)的停歇時(shí)間，以便保持盡可能高的生產(chǎn)效率，而實(shí)際訂單計(jì)算過程中存在計(jì)算時(shí)間過長可能，讓卷紙切割機(jī)長時(shí)間的等待最優(yōu)排產(chǎn)方案是不經(jīng)濟(jì)的。為維持較高的生產(chǎn)效率，在滿足客戶訂單要求的情況下，可以人為限定一個(gè)最大計(jì)算時(shí)間，以便卷紙切割機(jī)不間斷運(yùn)作。

如果提出算法在限定時(shí)間內(nèi)得到全局最優(yōu)解，則輸出最優(yōu)排產(chǎn)方案;如果提出算法在限定時(shí)間內(nèi)沒有得到全局最優(yōu)解，則找到在限定時(shí)間截止時(shí)得到的所有解中的最優(yōu)解，輸出最優(yōu)排產(chǎn)方案;如果在限定時(shí)間內(nèi)未求出可行解，則調(diào)整訂備用規(guī)格，重新開始計(jì)算，直至獲得最終方案。

3 建立圖形化人機(jī)界面系統(tǒng)

為了讓本課題提出的算法更好地應(yīng)用于實(shí)際生產(chǎn)中，開發(fā)了一個(gè)圖形化人機(jī)界面系統(tǒng)，系統(tǒng)執(zhí)行流程包括以下步驟：第一步，確定客戶訂單中的卷紙規(guī)格與數(shù)量;第二步，確定待切割的全部原紙規(guī)格與數(shù)量;第三步，補(bǔ)充一些備用規(guī)格來充分利用原紙;第四步，限定系統(tǒng)最大運(yùn)行時(shí)間;第五步，以切換排刀組合步驟數(shù)最少為目標(biāo)建立非線性整數(shù)規(guī)劃模型;第六步，在限定時(shí)間內(nèi)用Gurobi 8.0.0求解器求解非線性整數(shù)規(guī)劃問題;第七步，如果第六步在限定時(shí)間內(nèi)得到全局最優(yōu)解，則輸出最優(yōu)排產(chǎn)方案，如果第六步在限定時(shí)間內(nèi)沒有得到全局最優(yōu)解，則找到在限定時(shí)間截止時(shí)得到的所有解中的最優(yōu)解，輸出最優(yōu)排產(chǎn)方案，如果第六步未求出可行解，則返回第三步補(bǔ)充備用規(guī)格，繼續(xù)接下來的步驟，直到得出最終方案。具體如圖1所示。

人機(jī)界面整體分為7個(gè)部分：規(guī)定尺寸輸入?yún)^(qū)、規(guī)定卷數(shù)輸入?yún)^(qū)、長卷紙規(guī)格輸入?yún)^(qū)、備用尺寸輸入?yún)^(qū)、最大計(jì)算時(shí)長輸入?yún)^(qū)、排刀方案輸出區(qū)以及備用尺寸及數(shù)量輸出區(qū)。操作時(shí)首先根據(jù)訂單需求將規(guī)定尺寸、規(guī)定卷數(shù)、長卷紙尺寸、長卷紙數(shù)量、長卷紙質(zhì)量、備用尺寸、最大計(jì)算時(shí)長分別鍵入相應(yīng)窗口，確認(rèn)無誤后點(diǎn)擊“輸入完成并計(jì)算”按鈕，待系統(tǒng)提示計(jì)算完畢后，再點(diǎn)擊“查詢計(jì)算結(jié)果”按鈕，便可在排刀方案輸出區(qū)內(nèi)查看最優(yōu)卷紙分切排產(chǎn)方案，在備用尺寸及數(shù)量輸出區(qū)內(nèi)查看最優(yōu)方案中備用尺寸的使用情況。具體如圖2所示。

4 仿真實(shí)例

造紙企業(yè)實(shí)際排產(chǎn)主要依照客戶訂單要求進(jìn)行，客戶訂單一般有品種、規(guī)格、質(zhì)量和數(shù)量的要求。另外如果訂單無解或不能恰好將待切割長卷紙分切完畢，就需要補(bǔ)充一部分備用尺寸。將客戶訂單要求的規(guī)格和數(shù)量輸入到非線性整數(shù)規(guī)劃模型，必要時(shí)補(bǔ)充備用尺寸、限定最大運(yùn)行時(shí)間，就能獲得最優(yōu)排產(chǎn)方案。

為了驗(yàn)證本課題提出方法的可行性和有效性，根據(jù)一個(gè)規(guī)格多樣、紙機(jī)產(chǎn)量大的俄卡紙廠的訂單需求進(jìn)行了實(shí)驗(yàn)。實(shí)例中客戶訂單具體要求如表1所示。

將訂單輸進(jìn)人機(jī)界面后，根據(jù)實(shí)際需求選定最大時(shí)長為30 min，點(diǎn)擊“輸入完成并計(jì)算”按鈕，待系統(tǒng)提示計(jì)算完畢后再點(diǎn)擊“查詢計(jì)算結(jié)果”按鈕，便可在下方排刀方案輸出區(qū)內(nèi)查看最優(yōu)卷紙分切排產(chǎn)方案，在備用尺寸及數(shù)量輸出區(qū)內(nèi)查看最優(yōu)方案中備用尺寸的使用情況。具體如圖3所示。

得出該訂單的最優(yōu)排產(chǎn)方案如表2所示。

該實(shí)例僅需切換排刀組合8次就可完成客戶訂單要求，極大降低了分切機(jī)切換成本。訂單中的小卷紙總長相當(dāng)于65卷大卷紙，但客戶要求將75卷待切割大卷紙全部分切完畢，故使用備用規(guī)格900 mm的小卷紙21卷、1800 mm的小卷紙25卷，以達(dá)到客戶訂單要求。

5 結(jié) 語

本課題針對(duì)造紙廠長卷紙分切排產(chǎn)問題進(jìn)行細(xì)致分析，提出一種基于非線性整數(shù)規(guī)劃的卷紙分切排產(chǎn)方案優(yōu)化算法，該算法首先根據(jù)客戶訂單需求建立數(shù)學(xué)模型，其次對(duì)模型進(jìn)行優(yōu)化，有效地提高求解效率，最后用非線性整數(shù)規(guī)劃的方法求解出最優(yōu)排刀方案。該算法可應(yīng)用于不同規(guī)格、數(shù)量的客戶訂單，綜合考慮了模型求解的各種情況，可靈活調(diào)整計(jì)算時(shí)間和備用尺寸，更符合紙廠生產(chǎn)過程中的實(shí)際需求。通過該模型確定排產(chǎn)策略，能有效提高造紙廠卷紙分切效率，節(jié)省原材料和人力資源，有利于造紙行業(yè)的可持續(xù)發(fā)展。

參考文獻(xiàn)

[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.

金福江，?王?慧，李?平. 間歇蒸煮過程的分層多目標(biāo)優(yōu)化[J]. 中國造紙學(xué)報(bào)，?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.

屠建順，?楊春節(jié)，?李?平，等. 基于變長編碼的遺傳算法在紙卷切割中的應(yīng)用[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.

楊春節(jié). 基于遺傳算法的造紙企業(yè)優(yōu)化排產(chǎn)方法研究[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.

蔡?韻，?楊春節(jié)，?李?平. 造紙生產(chǎn)紙卷分切與庫存綜合優(yōu)化排產(chǎn)研究[J]. 中國造紙學(xué)報(bào)，?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.

于戰(zhàn)科，?倪明放，?汪澤焱，等. 整數(shù)線性規(guī)劃的改進(jìn)分支定界算法[J]. 計(jì)算機(jī)應(yīng)用，?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.

高培旺，?封全喜. 切割定界與整數(shù)分枝結(jié)合求解整數(shù)線性規(guī)劃[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，?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.

倪任遠(yuǎn)，?封建湖. 轎運(yùn)車配載問題的整數(shù)線性規(guī)劃模型及解法[J]. 高等學(xué)校計(jì)算數(shù)學(xué)學(xué)報(bào)，?2017（3）：?200.

（責(zé)任編輯：董鳳霞）