一維下料問題的一種混合啟發式算法

管衛利，龔 擊，薛煥堂

1 引言

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

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

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

2 問題的數學模型

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

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

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

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

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

3 求解方法

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

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

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

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

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

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

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

第k種切割方式其使用數量為：

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

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

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

③記錄當前最優切割方式以及其對應的線材長度，按照當前零件的剩余需求量和線材的剩余供應量確定切割方式使用的次數。

④更新當前零件剩余需求量和線材剩余供應量。

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

4 實驗計算

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

4.1 單種線材下料的情形

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

表2 文獻[6]算法計算結果Tab.2 The Calculation Result of Literature[6]Algorithm

表3 文獻[5]算法計算結果Tab.3 The Calculation Result of Literature[5]Algorithm

表4 這里算法計算結果Tab.4 The Calculation Result of this Algorithm

例2：采用文獻[5]例題2數據，用長度為1000m的線材切割出5種零件，零件長度和需求量分別為（512m，5）、（321m，12）、（128m，8）、（247m，22）、（290m，6）。這里算法求得的下料方案，如表5所示。共耗費15根線材，材料利用率為97.40%，所用計算時間為0.409s。文獻[5、8]算法求得的下料方案分別參見文獻[5]的表3-6和表3-7，耗費線材分別為17根、16根，材料利用率分別為85.90%、91.30%。可見這里算法下料利用率高于文獻[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，可用根數分為 30，40，50，40，30；零件長度分別為 35m，52m，71m，97m，需求量分別為 100，80，50，100。文獻[10]VEA算法和文獻[5]順序啟發式算法求得的下料方案分別參見文獻[5]的表3-8和表3-12，兩種算法下料方案耗費的原材料長度均為21200m。這里算法求得的下料方案，如表6所示，耗費的線材長度為20960m，所用計算時間為0.631s。可見這里算法的節材效果優于文獻[5、10]算法。

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

5 結論

建立了線材一維下料問題的數學模型，構造了解決該問題的混合啟發式算法，該算法在生成切割方式時綜合考慮了切割方式的廢料長度，零件的平均尺寸，大零件的選取情況。克服了傳統順序啟發式算法的貪婪性，即先生成的切割方式材料利用率高，后生成的切割方式材料利用率低的弊端。通過與4種文獻算法進行比較，表明了這里混合啟發式算法在余料控制和提高下料方案的材料利用率方面均有效，并且算法計算時間較短，能夠滿足實際應用需要。