一維下料問題的一種混合啟發(fā)式算法

管衛(wèi)利，龔 擊，薛煥堂

1 引言

下料問題廣泛的出現(xiàn)在機(jī)械制造業(yè)的生產(chǎn)過程中，其實(shí)質(zhì)是對有限資源進(jìn)行合理安排使得資源利用率最高[1-2]。一維下料問題是指：將庫存線材原料切割成若干種所需零件，每種零件具有特定的長度和需求量，尋求一種下料方案使得線材利用率最高。管材，型材，棒材的切割下料均屬于一維下料問題。下料方案由多種切割方式按照一定數(shù)量組合而成，切割方式是指零件在單根線材上的排列方式。目前一維下料問題的解決方法可分為兩大類：以切割方式為導(dǎo)向的方法和以零件為導(dǎo)向的方法[3]。以切割方式為導(dǎo)向的方法首先組合零件形成多種不同的切割方式，然后確定每種切割方式所使用的數(shù)量。文獻(xiàn)[4]針對一維下料問題提出了一種基于遺傳算法的隨機(jī)搜索模型，通過在可行的切割方式集合中進(jìn)行迭代搜索來產(chǎn)生下料方案。文獻(xiàn)[5]提出了一種順序啟發(fā)式算法，首先求出所有可行的切割方式，然后按照一定的啟發(fā)式規(guī)則搜索所有可能的切割方式組合，選擇一組最優(yōu)切割方式形成下料方案。

以零件為導(dǎo)向的方法按順序生成下料方案中各切割方式，每個(gè)切割方式滿足部分零件需求量，直到所有零件需求量得到滿足后終止切割方式的生成。文獻(xiàn)[6]提出了一種基于多級序列思想的下料算法，將下料問題轉(zhuǎn)化為多級序列優(yōu)化問題，每級對應(yīng)單根線材切割方式的求解問題，用剩余零件需求量構(gòu)造每級最優(yōu)序列。文獻(xiàn)[7]提出了一種順序價(jià)值修正算法，該算法通過順序產(chǎn)生切割方式來構(gòu)造下料方案，每次產(chǎn)生切割方式后對剩余零件的價(jià)值進(jìn)行修正。文獻(xiàn)[8]提出了AB分類算法，該算法將貪心算法和隨機(jī)搜索技術(shù)相結(jié)合，每次取一根線材隨機(jī)的滿足部分剩余零件需求量，重復(fù)該過程直到所有零件需求得到滿足為止；對可行的切割方式的材料利用率設(shè)置一個(gè)閾值，高于閾值的切割方式歸為A類其余歸為B類，對B類切割方式所對應(yīng)的線材重新考察其切割方式直到無法產(chǎn)生A類切割方式或線材利用率達(dá)到理論上限為止。

這里提出一種以零件為導(dǎo)向的混合啟發(fā)式下料算法來求解一維下料問題。該算法通過廢料長度、零件平均長度、大零件數(shù)量指標(biāo)來評價(jià)各個(gè)切割方式的質(zhì)量；在選擇切割方式形成下料方案過程中，綜合考慮零件的剩余需求量、線材的庫存量以及切割方式對應(yīng)線材的長度。編程實(shí)現(xiàn)這種算法，將該算法與文獻(xiàn)中下料算法進(jìn)行測試比較，實(shí)驗(yàn)結(jié)果表明該算法相當(dāng)有效。

2 問題的數(shù)學(xué)模型

所用到的符號（變量）及其含義，如表1所示。

表1 符號及其含義Tab.1 Symbols and Their Meanings

一維下料問題：用m種線材切割出n種零件，其中第i（i=1，…，m）種線材的長度為Li，供應(yīng)量為bi，第j（j=1，…，n）種零件長度為lj，需求量為dj；約束條件為每種線材的使用量不超過其供應(yīng)量，每種零件的需求量得到滿足；優(yōu)化目標(biāo)為最大化化線材利用率。

設(shè)一維下料問題的解（下料方案）為A=［A1，…，AK］，共K種切割方式，每種切割方式AK=［ak1，…，akn］，其中akj表示第k種切割方式包含第j種零件的數(shù)量；第k種切割方式的使用數(shù)量為xk，對應(yīng)線材的編號為 g（k）∈［1，…，m］。綜上，一維下料問題的數(shù)學(xué)模型[9]如下：

上述模型，式（1）是目標(biāo)函數(shù)，實(shí)現(xiàn)線材利用率最大化；式（2）為零件需求量約束，即每種零件的需求量都得到精確滿足；式（3）為切割方式約束，即每種切割方式中的零件總長度不大于所對應(yīng)線材的長度；式（4）為線材使用量約束，即每種線材所使用的數(shù)量不超過其供應(yīng)量；式（5）為變量的取值范圍約束，即每種切割方式的使用次數(shù)只能取非負(fù)整數(shù)。

3 求解方法

文中混合啟發(fā)式算法的主要思想為用當(dāng)前毛坯的需求量和線材供應(yīng)量來構(gòu)造一系列可能的切割方式，按優(yōu)先級遞減原則選擇廢料最少、零件平均長度最大、大零件最多的切割方式切割線材滿足部分零件需求；重復(fù)上述過程直到所有零件需求量均得到滿足為止。

（1）輸入m種線材的數(shù)據(jù)（Li，bi），n種零件的數(shù)據(jù)（li，di）。

（2）將n種零件按照長度遞減排序，得到新的零件集合E=｛（l1，d1），…，（li，di），…，（ln，dn）｝，即對于任意i∈｛1，…，n｝，有l(wèi)i≥li+1。

（3）依據(jù)零件的需求量分別考察每種線材所對應(yīng)的可能切割方式，按照廢料最小原則確定最優(yōu)切割方式。

①對于每種切割方式，通過以下遞歸公式計(jì)算其包含每種零件的數(shù)量：

式中：“［·］”為向下取整數(shù)符號 k∈｛1，…，K｝，j∈｛1，…，n｝。

第k種切割方式其廢料長度為：

第k種切割方式其使用數(shù)量為：

第k種切割方式的零件平均長度為：

②通過下述優(yōu)先級原則在m種線材所對應(yīng)的所有可能的切割方式集合中選取當(dāng)前最優(yōu)切割方式k0，優(yōu)先級從（1～3）依次遞減。

（1）廢料長度 Wk最小，即 Wk0=min（Wk）。（2）零件平均長度 fk最大，即 fk0=max（fk）。（3）包含大零件的數(shù)量最多。

③記錄當(dāng)前最優(yōu)切割方式以及其對應(yīng)的線材長度，按照當(dāng)前零件的剩余需求量和線材的剩余供應(yīng)量確定切割方式使用的次數(shù)。

④更新當(dāng)前零件剩余需求量和線材剩余供應(yīng)量。

（4）判斷每種零件的剩余需求量是否全為0，若否，則轉(zhuǎn)（3），若是，則結(jié)束算法。

4 實(shí)驗(yàn)計(jì)算

為了檢驗(yàn)這里混合啟發(fā)式算法的性能，用C++語言實(shí)現(xiàn)該算法，在Microsoft Visual Studio 2010旗艦版開發(fā)平臺進(jìn)行實(shí)驗(yàn)，所用硬件環(huán)境為主頻3.3GHz，內(nèi)存2GB微型計(jì)算機(jī)。分別考慮單種線材下料情形和多種線材下料情形。采用文獻(xiàn)中已有例題，將這里算法計(jì)算結(jié)果分別與文獻(xiàn)[6]啟發(fā)式多級序列線性優(yōu)化算法、文獻(xiàn)[5]順序啟發(fā)式算法、文獻(xiàn)[8]AB分類算法、文獻(xiàn)[10]演化算法進(jìn)行比較。

4.1 單種線材下料的情形

例1：采用文獻(xiàn)[5]例題1數(shù)據(jù)，用長度為3m的線材切割出5種零件，零件長度和需求量分別為（2.2m，5）、（1.8m，3）（1.2m，4）、（0.5m，6）、（0.3m，6），其中（2.2m，5）表示 2.2m 的零件需求量為 5個(gè)。求最優(yōu)下料方案（不考慮線材切口損失）[5]。表2給出了文獻(xiàn)[6]啟發(fā)式多級序列線性優(yōu)化算法求得的下料方案，表中第1行數(shù)據(jù)表示，切割方式1包含2號零件1個(gè)，5號零件4個(gè)，余料長度為0，按照該方式切割1根線材。表3給出了文獻(xiàn)[5]順序啟發(fā)式算法求得的下料方案。這里算法求得的下料方案如表4所示，所用計(jì)算時(shí)間為0.326s，三種算法的下料方案均耗費(fèi)8根線材，但這里算法前7根線材利用率達(dá)到100%，最后一根線材余料為2.4m，可供以后下料使用。文獻(xiàn)[5-6]算法下料方案產(chǎn)生的余料分別分散在4根線材和2根線材中，余料種類多且尺寸較短不便于今后下料使用。因此這里算法在余料控制方面優(yōu)于文獻(xiàn)[5-6]算法。

表2 文獻(xiàn)[6]算法計(jì)算結(jié)果Tab.2 The Calculation Result of Literature[6]Algorithm

表3 文獻(xiàn)[5]算法計(jì)算結(jié)果Tab.3 The Calculation Result of Literature[5]Algorithm

表4 這里算法計(jì)算結(jié)果Tab.4 The Calculation Result of this Algorithm

例2：采用文獻(xiàn)[5]例題2數(shù)據(jù)，用長度為1000m的線材切割出5種零件，零件長度和需求量分別為（512m，5）、（321m，12）、（128m，8）、（247m，22）、（290m，6）。這里算法求得的下料方案，如表5所示。共耗費(fèi)15根線材，材料利用率為97.40%，所用計(jì)算時(shí)間為0.409s。文獻(xiàn)[5、8]算法求得的下料方案分別參見文獻(xiàn)[5]的表3-6和表3-7，耗費(fèi)線材分別為17根、16根，材料利用率分別為85.90%、91.30%。可見這里算法下料利用率高于文獻(xiàn)[5、8]算法。

表5 這里算法求得的例題2的下料方案Tab.5 The Cutting Plan of Instances 2 Solved by this Algorithm

4.2 多種線材下料的情形

例題3：用5種線材原料切割出4種零件，線材長度分別為：320m，340m，360m，380m，400m，可用根數(shù)分為 30，40，50，40，30；零件長度分別為 35m，52m，71m，97m，需求量分別為 100，80，50，100。文獻(xiàn)[10]VEA算法和文獻(xiàn)[5]順序啟發(fā)式算法求得的下料方案分別參見文獻(xiàn)[5]的表3-8和表3-12，兩種算法下料方案耗費(fèi)的原材料長度均為21200m。這里算法求得的下料方案，如表6所示，耗費(fèi)的線材長度為20960m，所用計(jì)算時(shí)間為0.631s?？梢娺@里算法的節(jié)材效果優(yōu)于文獻(xiàn)[5、10]算法。

表6 這里算法求得的例題3的下料方案Tab.6 The Cutting Plan of Instances 3 Solved by this Algorithm

5 結(jié)論

建立了線材一維下料問題的數(shù)學(xué)模型，構(gòu)造了解決該問題的混合啟發(fā)式算法，該算法在生成切割方式時(shí)綜合考慮了切割方式的廢料長度，零件的平均尺寸，大零件的選取情況?？朔藗鹘y(tǒng)順序啟發(fā)式算法的貪婪性，即先生成的切割方式材料利用率高，后生成的切割方式材料利用率低的弊端。通過與4種文獻(xiàn)算法進(jìn)行比較，表明了這里混合啟發(fā)式算法在余料控制和提高下料方案的材料利用率方面均有效，并且算法計(jì)算時(shí)間較短，能夠滿足實(shí)際應(yīng)用需要。