基于非線性整數規劃的卷紙分切排產方案優化算法研究

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

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

關鍵詞：卷紙分切;非線性整數規劃;優化模型

中圖分類號：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.

（責任編輯：董鳳霞）