基于隨機搜索算法的薄膜分切管理系統(tǒng)

盧偉康，鄒細勇，孟 燦，王國建，倪志祥

中國計量學院 光學與電子科技學院，杭州 310018

基于隨機搜索算法的薄膜分切管理系統(tǒng)

盧偉康，鄒細勇，孟 燦，王國建，倪志祥

中國計量學院 光學與電子科技學院，杭州 310018

1 引言

一維下料問題，是指原材料和所需材料維數都為一維時，在已知訂單要求和原材料數據時如何進行優(yōu)化切割下料，使得原材料盡量得到充分利用，成本盡量得到節(jié)約的線性規(guī)劃問題[1-2]。國內外學者對一維下料問題的研究已經有一定的歷史，諸如早期以Gilmore P C和Gomory R E為代表的線性規(guī)劃方法（LP）[1-6]，以及之后百家爭鳴的各種啟發(fā)式智能算法[7-10]，都廣泛地應用到解決一維下料問題中去，并取得了較大的成果。

實際生產中，諸如鋼材、紙卷、管材、薄膜等原材料的排樣切割都屬于一維下料問題的范疇。隨著工業(yè)化社會的發(fā)展，人們生產生活中對薄膜的需求量越來越大，薄膜生產行業(yè)已經進入了大規(guī)模生產營銷的階段。薄膜生產企業(yè)是典型的流程企業(yè)，具有訂單數量多、產品交貨期短等特點，生產過程常受到原料、設備和人力等因素的影響。不合理的薄膜下料與分切方法不僅會影響企業(yè)的生產效率，而且還會造成多項資源的浪費，增加企業(yè)的生產成本。為了降低成本，提高企業(yè)的下料生產效率，可以從以下兩個方面著手：一方面是設計出合理的下料算法，減少分切余料的浪費；二是通過建立合理的產銷存系統(tǒng)，優(yōu)化排單的過程管理，縮短市場需求與生產規(guī)劃之間的距離。

本文闡述了一種基于隨機搜索方法的順序啟發(fā)式算法[11]，并在此算法基礎上開發(fā)出了具有豐富功能的薄膜分切優(yōu)化綜合管理軟件。

2 計算模型及算法實現

2.1 數學模型分析

一維下料是個NP問題[12]，即非確定多項式問題，其非確定性可由以下的數學模型看出。以原材料消耗總卷數最少的數學模型為例，在薄膜生產行業(yè)中，設大卷薄膜的寬度為L，一筆訂單中共有m個規(guī)格的小卷薄膜，寬度分別為 l1、l2、…、lm，所對應的需求卷數分別為d1、d2、…、dm，設分切方案中共有 n種排樣方式，每一種排樣方式的重復使用次數分別為 x1，x2，…，xn，第i種排樣方式中每個小卷薄膜使用的數量分別為ai1，ai2，…，aim，其中i表示第i種分切方案。設Z為使用的大卷數，以原材料消耗的總卷數最少為目標函數[13]，即Z盡量得小，則一維下料問題可描述為：

鑒于NP問題的復雜性及非確定性，至今無法確立一個能得到問題最優(yōu)解析解的算法，因此已有的算法都旨在尋找能更接近最優(yōu)解的分切算法。上述數學模型僅僅考慮了大卷薄膜消耗的總卷數盡量少的目標，而在實際的薄膜生產中，還需要考慮分切方案中排樣方式更換導致的切割機器調整成本及分切剩余原料的庫存積壓問題。因此，實際生產中通常按優(yōu)先級從高到低對以下三個目標進行生產排樣的優(yōu)化。首要目標是使原材料消耗最少，即薄膜原材料消耗的總卷數最少；其次，還要追求最終排樣方式數少；最后，要求最后一種排樣方式剩余的余料寬度較大，因為較長的余料可以回收并再次利用。基于順序啟發(fā)式算法思想，本系統(tǒng)通過以下幾個策略來達到上述的目標。

（1）設立多個啟發(fā)式規(guī)則。啟發(fā)式算法往往通過設立一些參數和公式（啟發(fā)式規(guī)則）作為判斷條件來引導算法往設定的目標“前進”。通過啟發(fā)式規(guī)則能使計算結果往想要的目標方向發(fā)展，但通常得到的是較優(yōu)解。因此，本文設立了兩類不同的啟發(fā)式規(guī)則，一類是每生成一種排樣方式時僅考慮該排樣方式的最多可重復使用次數，另一類是每生成一種排樣方式時同時考慮該排樣方式的最多重復使用次數和該排樣方式產生的余料寬度。以兩類啟發(fā)式規(guī)則引導算法多次重復執(zhí)行，則可得到兩組排樣方案。再根據上述3個優(yōu)化目標按優(yōu)先級對其進行篩選。

（2）使用隨機搜索算法獲得排樣方式。NP問題通常認為不可能在合理的時間范圍內找到全局最優(yōu)解。啟發(fā)式算法適合用于來求解NP問題的原因在于其通過設立規(guī)則能快速有效地找到近似最優(yōu)解。由于隨機搜索算法在搜索小卷薄膜時具有隨機性，使得啟發(fā)式算法每執(zhí)行完一次都能得到一種較優(yōu)的排樣方案，多次執(zhí)行該算法就能得到多種不同的排樣方案，再根據優(yōu)化目標對其篩選，最終能獲得其中最好的方案。

（3）優(yōu)化偽隨機性。隨機運算中，在設置srand函數的種子時，如果采用默認設置好的種子，由于計算機隨機運算是一種偽隨機的方法，會導致每次分切排樣的結果都相同，這相當于縮小了隨機搜索算法的搜索空間。又由于薄膜分切的排樣方案是通過重復搜索來不斷優(yōu)化的，而隨機數發(fā)生器rand()產生的隨機序列具有周期性，使算法反復迭代執(zhí)行多次后無法搜尋到更優(yōu)解。因此，本文在隨機數運算中采用改變偽隨機序列的策略，并以time變量作隨機數種子，具體如下：算法每執(zhí)行一定次數大循環(huán)后，重新設定時間種子為srand(time+rand())，即每執(zhí)行一定次數大循環(huán)后重新更換偽隨機序列，優(yōu)化搜索的隨機性。這種策略擴大了算法的搜索空間，有利于找到滿意的排樣方案。

2.2 算法描述

步驟1設立樣本參數Ns和評價公式選擇參數method，令method=0。

步驟2用一種隨機搜索算法獲得Ns種排樣方式。

步驟4對上述Ns個排樣方式按評價公式V1= 10n-yt進行評價，選取其中V1值最大的排樣方式并保留，被選定的個體為當前排樣方式。

步驟5從還未排樣的小卷薄膜集合中，扣除當前排樣方式中已經使用的小卷薄膜。則待排樣的小卷薄膜需求量更新為：dj=dj-n×atj，j=1，2，…，m，其中假設t為當前選中的排樣方式。

步驟6迭代步驟2～6直到待分切的小卷薄膜集合為空，這樣就生成了一種排樣方案。

步驟7重復1 000次步驟2～6，期間每執(zhí)行10次后重新設置隨機數種子為time+rand()，從產生的1 000個排樣方案里按三個優(yōu)化目標的優(yōu)先級順序優(yōu)選出最好的排樣方案。

步驟8令method=1，步驟4中評價公式取V2=10n，重復步驟2～7的過程。

步驟9把兩種評價公式下得到的各自最好的排樣方案再次按三個優(yōu)化目標的優(yōu)先級選出其中最好的排樣方案，作為最終排樣方案。

3 薄膜分切管理優(yōu)化系統(tǒng)概述

在下料算法的基礎上開發(fā)了薄膜優(yōu)化分切綜合管理系統(tǒng)，其主要包括以下三個功能模塊。

（1）訂單數據的查詢、導入和統(tǒng)計。連接存放訂單信息的SQL數據庫，實現了對數據庫中訂單信息的按訂單號或日期進行實時查詢。可以從一個或多個訂單中選取相同物理屬性（薄膜型號、厚度等）的薄膜訂單進行組合并導入到分切界面，同時支持臨時訂單導入，可以從EXECL中導入規(guī)定格式的訂單數據。對數據庫中的訂單進行統(tǒng)計，是根據設定的起始日期和結束日期計算并排列出期間訂單中需求量最大的幾種小卷的信息，生產分切薄膜時可以把最后一種排樣方式的余料分切成暢銷的幾種小卷薄膜。

（2）分切計算：從數據庫導入訂單數據后，可以對當前的待排樣數據進行添加、刪除、修改操作，執(zhí)行分切計算并經確認后更新數據庫，把訂單中已經確認過分切的小卷薄膜用“1”標記，表示已分切，默認標“0”，表示未分切。

（3）分切報表打印：分切完成后生產的排樣方案除了在軟件界面顯示外，可以導出生成word報告并打印，報告中除包含了排樣方案外還包括了當前訂單的小卷薄膜的各物理屬性及當前訂單相關的各種信息，便于企業(yè)的全過程管理。生產車間根據批準的排樣方案進行大卷薄膜的生產。

4 算例分析

通過大量的數據計算實驗并同相關文獻進行對比，本文所述的薄膜分切綜合系統(tǒng)在計算結果及時間效率上都有一定的改進，下面以一些相關文獻中的數據為例，對本文系統(tǒng)進行說明和分析（各膜卷寬度單位為mm）。

算例1以一BOPP薄膜企業(yè)的一個實際訂單為例，原材料大卷薄膜寬度為8 280，8種小卷薄膜寬度分別為500、520、540、560、580、600、660和 720，需求量分別為144、144、144、144、144、99和99個，求下料方案。

文獻[14]中的CAD系統(tǒng)已經跟國內外很多文獻進行過算例對比，證實了該系統(tǒng)算法有效性，本文采用該文獻提供的系統(tǒng)對上述案例進行分切計算，其排樣方案如表1所示。

表1 算例1CAD系統(tǒng)排樣方案

CAD系統(tǒng)給出的排樣方案，包括5個排樣方式，使用原材料74根，最后一個排樣方式的余料為540，已經是一種較好的排樣方案。

本文薄膜分切綜合管理系統(tǒng)的排樣方案計算結果如表2所示，從表中可以看出，本文系統(tǒng)包括4個排樣方式，使用原材料74根，最后一個排樣方式的余料為400。在使用原材料相同的情況下，減少排樣方式數可以減少調整刀具的次數，節(jié)約人力物力，若考慮調整刀具所帶來的成本大于生成多余余料成本差的情況，本文提供了一種更好的選擇方案。此外在同一臺計算機上，CAD系統(tǒng)處理上述案例用時在16 s左右，而本文系統(tǒng)不到1 s。

表2 本文系統(tǒng)算例1排樣方案

算例2本算例來自文獻[14]，假設原材料寬度為4 000，五種坯料寬度分別為463、405、324、256和182，需求量分別為100、200、200、200和200個，求下料方案。

文獻[15]中采用一種順序啟發(fā)式算法求解，排樣方案包括排樣方式8個，使用原材料71根。文獻[7]的CAD系統(tǒng)給出其中一種以排樣方式少為目標的排樣方案，如表3所示，包括排樣方式3個，使用原材料71根，最后一個排樣方式的余料為740。本文系統(tǒng)的給出表4所示排樣方案，包括排樣方式3個，使用原材料71根，最后一個排樣方式的余料為2 180，超過文獻[7]的該數值。最后一個排樣方式余料越多，可以回收利用的價值越大。此外在同一臺計算機上，CAD系統(tǒng)處理上述案例用時在5 s左右，而本文系統(tǒng)不到1 s。

表3 CAD系統(tǒng)算例2排樣方案

表4 本文系統(tǒng)算例2排樣方案

5 結束語

本文把一維下料問題同實際生產需求相結合，提出了一維下料問題的三個分等級優(yōu)化目標，即首先考慮原材料的利用率，其次考慮排樣方案中排樣方式數，最后考慮最后一種排樣方式中余料寬度。采用了一種基于隨機搜索的多啟發(fā)式規(guī)則算法，通過設立多個啟發(fā)式規(guī)則和優(yōu)化偽隨機性來增大可行解的搜索空間，最終找到當前啟發(fā)式規(guī)則下的最優(yōu)排樣方案。

通過與其他研究文獻的算例對比，驗證了本文算法在計算結果及時間效率上的改進。此外，通過對比研究發(fā)現，大部分的一維下料算法在隨著坯料種數的增多，即m變大時，其算法的計算時間呈幾何上升，由于本文算法的隨機搜索次數不會隨著m的變大呈幾何上升，即使處理十余種種規(guī)格的坯料，仍然能在1 s內完成計算，大大減少了計算時間。本文的分切算法同生產管理相結合，除算法分切外還有很多管理、統(tǒng)計功能，使企業(yè)生產、管理相結合，具有較大的應用價值。

[1]Gilmore P C，Gomory R E.A linear programming approach to the cutting-stock problem[J].Operations Research，1961，9：849-859.

[2]Gilmore P C，Gomory R E.A linear programming approach to the cutting-stock problem-part2[J].Operations Research，1963，1：863-888.

[3]Vnaee P H，Barnhat C，Johnson E L.Sovling binary cutting stock problems by column generation and branchand-bound[J].Comput ational Optimization and Applications，1994，3（2）：111-130.

[4]Chauny F，Loulou R，Sadones S，et al.A two-phase heuristic for the two-dimensional cutting-stock problem[J]. Journal of the Operational Research Society，1991，42（1）：264-271.

[5]Zak E J.Row and column generation technique for a multistage cutting stock pro blem[J].Computers&Operations Reasearch，2002，29（9）：1143-1156.

[6]Francois V.Exact algorithm for minimising the number of setups in the one-dimensional cutting stock problem[J]. Operations Research，2000，48（6）：915-926.

[7]Cui Yaodong，Yang Yuli.A heuristic for the one-dimensional cutting stock problem with usable leftover[J].European Journal of Operational Research，2010，204：245-250.

[8]Haessler R W.A heuristic solution to a non linear cutting stock problem[J].ManagementScience，1971，17：8793-8803. [9]Beasley J E.An exact two-dimensional non-guillotine cutting tree search procedure[J].Operations Research，1985，33（l）：49-64.

[10]Vharenkamp R.Random search in the one-dimensional cutting stock problem[J].European JournalofOperation Research，1996，95：191-200.

[11]Haessler R W.Controlling cutting pattern changes in one-dimensional trim problems[J].Operations Research，1975，23（3）：483-493.

[12]Cui Y，Zhao X，Yang Y，et al.A heuristic for the onedimensional cutting stock problem with pattern reduction[J].Proceedings of the Institution of Mechanical Engineers，Part B，Journal of Engineering Manufacture，2008，222（6）：677-685.

[13]劉睿，嚴玄，許道云，等.一種有效的求解一維下料問題的啟發(fā)式算法[J].計算機應用，2009，29（4）：1180-1182.

[14]劉睿，嚴玄，陳菲，等.考慮多目標優(yōu)化的一維排樣系統(tǒng)[J].計算機應用與軟件，2010，27（1）：23-25.

[15]王小東，李剛，歐宗瑛.一維下料優(yōu)化的一種新算法[J].大連理工大學學報，2004，44（3）：407-411.

LU Weikang,ZOU Xiyong,MENG Can,WANG Guojian,NI Zhixiang

College of Optical and Electronic Technology,China Jiliang University,Hangzhou 310018,China

A mathematical model of the one-dimensional cutting stock problem is established for film manufacturing,and a heuristic algorithm based on the random search algorithm is put forward to cut the raw film stock.The implementation steps of the cutting algorithm are given,which has been integrated with the functions of database query,data screening, data import and report generation into a management system.The contrast experiments with the same type systems show that the computation time is shorter and layout scheme has less model number,which demonstrates that the system is effective and efficient.

random search;one-dimensional cutting;heuristic algorithm

建立了薄膜分切的一維下料數學模型，提出采用一種基于隨機搜索的啟發(fā)式算法進行大卷薄膜的分切。給出了分切算法的實現步驟，將其與薄膜數據庫查詢、篩選、導入和報表等功能集成，形成了一體化的分切綜合管理系統(tǒng)。與其他多種一維下料系統(tǒng)進行算例對比，排樣方案及計算時間證實了該系統(tǒng)的有效性。

隨機搜索；一維下料；啟發(fā)式算法

A

TP391.7

10.3778/j.issn.1002-8331.1301-0042

LU Weikang,ZOU Xiyong,MENG Can,et al.Film cutting management system based on random search algorithm.Computer Engineering and Applications,2014,50（23）：267-270.

國家自然科學基金（No.50905170，No.61007012）；浙江省重點科技創(chuàng)新團隊項目（No.2010R50020）。

盧偉康（1988—），男，碩士研究生，研究領域：軟件開發(fā)；鄒細勇（1979—），男，副教授，研究領域：機器人導航、計算機控制、智能照明系統(tǒng)。E-mail：dean-1140@163.com

2013-01-07

2013-03-29

1002-8331（2014）23-0267-04

CNKI網絡優(yōu)先出版：2013-04-08,http://www.cnki.net/kcms/detail/11.2127.TP.20130408.1648.016.html