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

盧偉康，鄒細(xì)勇，孟 燦，王國建，倪志祥

中國計(jì)量學(xué)院 光學(xué)與電子科技學(xué)院，杭州 310018

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

盧偉康，鄒細(xì)勇，孟 燦，王國建，倪志祥

中國計(jì)量學(xué)院 光學(xué)與電子科技學(xué)院，杭州 310018

1 引言

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

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

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

2 計(jì)算模型及算法實(shí)現(xiàn)

2.1 數(shù)學(xué)模型分析

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

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

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

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

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

2.2 算法描述

步驟1設(shè)立樣本參數(shù)Ns和評價(jià)公式選擇參數(shù)method，令method=0。

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

步驟4對上述Ns個(gè)排樣方式按評價(jià)公式V1= 10n-yt進(jìn)行評價(jià)，選取其中V1值最大的排樣方式并保留，被選定的個(gè)體為當(dāng)前排樣方式。

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

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

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

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

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

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

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

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

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

（3）分切報(bào)表打?。悍智型瓿珊笊a(chǎn)的排樣方案除了在軟件界面顯示外，可以導(dǎo)出生成word報(bào)告并打印，報(bào)告中除包含了排樣方案外還包括了當(dāng)前訂單的小卷薄膜的各物理屬性及當(dāng)前訂單相關(guān)的各種信息，便于企業(yè)的全過程管理。生產(chǎn)車間根據(jù)批準(zhǔn)的排樣方案進(jìn)行大卷薄膜的生產(chǎn)。

4 算例分析

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

[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]劉睿，嚴(yán)玄，許道云，等.一種有效的求解一維下料問題的啟發(fā)式算法[J].計(jì)算機(jī)應(yīng)用，2009，29（4）：1180-1182.

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

[15]王小東，李剛，歐宗瑛.一維下料優(yōu)化的一種新算法[J].大連理工大學(xué)學(xué)報(bào)，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

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

隨機(jī)搜索；一維下料；啟發(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.

國家自然科學(xué)基金（No.50905170，No.61007012）；浙江省重點(diǎn)科技創(chuàng)新團(tuán)隊(duì)項(xiàng)目（No.2010R50020）。

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

2013-01-07

2013-03-29

1002-8331（2014）23-0267-04

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