邵柏巖,葉伯生,王宏磊,梁 廣

(1.華中科技大學機械科學與工程學院,武漢 430074;2.北京化工大學數(shù)理學院,北京 100029;3.哈爾濱工業(yè)大學深圳校區(qū)機電工程與自動化學院,深圳 518055)

0 引言

矩形排樣是一類經(jīng)典的優(yōu)化問題,其目的是合理規(guī)劃矩形件在板材上的布局,以提高板材利用率、簡化切割過程、保障加工質量。矩形排樣常見于智能制造[1]、皮革剪裁[2]、家具加工[3]、玻璃切割[4]、鈑金加工[5]等方面,是制造業(yè)自動化的關鍵環(huán)節(jié),直接影響加工的成本與質量。求解該問題的方法主要分為3類:確定性算法、啟發(fā)式算法和智能優(yōu)化算法。最初,不少學者通過數(shù)學規(guī)劃嘗試給出該問題的精確解,這些方法對小批量排樣問題有不錯的效果。但在此之后,矩形排樣被數(shù)學家證明是NP-Hard 問題,加之生產力的迅猛發(fā)展,企業(yè)常有對大規(guī)模訂單加工的現(xiàn)實需求,兩者之間的矛盾,迫使學者們轉向尋找可以高效求解矩形排樣問題近似解的算法。先后出現(xiàn)了BLF、最低水平線[6]、剩余矩形匹配[7]等諸多啟發(fā)式算法,這些方法的主要思想是將矩形件按一定的規(guī)則和順序進行排樣。在面對大規(guī)模訂單時可以快速的給出排樣方案,但由于算法相對簡單,求解出的板材利用率有待提高。隨著智能優(yōu)化算法的興起,學者們利用改進后的鄰域搜索算法[8]、蟻群算法[9]、模擬退火算法[10]、遺傳算法[11-12]等對矩形排樣問題進行求解,實驗表明效果比原有算法有一定的提升。但大多數(shù)智能算法都要對樣本進行反復迭代,算法內存在大量待調參數(shù),使得智能算法在面對大規(guī)模訂單時不僅求解時間過長,而且求解結果太過依賴于初始參數(shù)的選取,常出現(xiàn)結果不穩(wěn)定或過早收斂現(xiàn)象。

當今注重個性化定制,待加工的訂單中矩形件形狀和所用材料均存在強互異性。但現(xiàn)有研究均是針對形狀強互異性,鮮有研究考慮到所用材料的強互異性。針對此類大規(guī)模兩重互異性問題,本文首先在現(xiàn)有研究基礎上提出了一種穩(wěn)定性好、高效快捷、板材利用率高的大規(guī)模排樣算法,即帶對偶項的降序有限首次適應算法來解決形狀強互異性的問題。再進一步對訂單組批問題加以研究,量化描述訂單所用材料的相似度,通過對每個訂單材料相似度以及工廠產能限制、生產效率等因素綜合考量,提出了考慮材料相似度的二階段貪心算法。通過該算法將總訂單依材料的相似程度組成若干批次,再對每個批次進行排樣加工來最大程度規(guī)避材料強互異性對板材利用率的影響。最后,利用多個測試數(shù)據(jù)集來驗證算法的有效性。

1 形狀強互異性的矩形件排樣算法

1.1 數(shù)學模型的建立

1.1.1 排樣過程命名約定

在矩形排樣的過程中,考慮到加工的便利性與可靠性,采用三階段齊頭切精確排樣[13],故加工中只會出現(xiàn)3種形式:對板材進行第1階段切割得到的條帶(stripe),對條帶進行第2階段切割得到的堆棧(stack),對堆棧進行第3階段切割得到最終的產品項(item)。切割后不能成為完整產品項的部分視為廢料(wasted)。為方便建立數(shù)學模型,對整個排樣過程中各部分的命名進行約定:

如圖1所示,對于一塊待切割板材,可以視作由若干個產品項及未利用的部分組成的集合,其中產品項i的長度為li,不妨讓產品根據(jù)其長度從高到低的順序進行排序:

圖1 命名約定示意圖

l1≥l2≥…≥ln

(1)

規(guī)定了產品項的編號后,進一步定義堆棧、條帶和板材的編號。采用文獻[14]的方式,將堆棧中包含的長度最長的產品項所對應的編號定義為該堆棧的編號,即堆棧的編號是其所包含產品項中的最小編號。以此類推,條帶的編號是其所包含堆棧中的最小編號,而板材的編號是其所包含條帶中的最小編號。另外,規(guī)定板材按照水平、豎直、水平3個階段依次進行切割。

1.1.2 多約束混合整數(shù)規(guī)劃模型

對矩形排樣優(yōu)化問題,建立多約束混合整數(shù)規(guī)劃模型。首先引入0～1變量為:

(2)

式中:αj,i=1當且僅當產品項i包含在堆棧j中,βk,j=1當且僅當堆棧j包含在條帶k中,γh,k=1當且僅當條帶k包含在板材h中。

可以注意到,遵從上述命名約定的情況下,如果板材h存在,那么板材h一定包含編號為h的條帶、堆棧及產品項,且產品項h為板材h中編號最小的產品項。此時有:

γh,h=1,h∈{1,…,n}

(3)

由于板材利用率等于產品項總面積與所需板材總面積之比,最大化板材利用率等價于最小化板材使用數(shù)量,故矩形排樣優(yōu)化的整數(shù)規(guī)劃模型為:

(4)

subject to:

(5)

αj,i=0,?i>jorwi≠wjorli+lj>L

(6)

(7)

(8)

(9)

(10)

(11)

式(5)表示產品唯一性約束:每個產品項i有且僅有一個,因此每個產品項只能包含在一個堆棧中。式(6)表示堆棧同寬限長:根據(jù)三階段齊頭切精確排樣要求,同一堆棧中產品項的長度或寬度相同且均與堆棧的寬度相同,同時任意產品項長度之和必須小于等于板材長度。式(7)表示堆棧唯一性:如果堆棧j存在,則該堆棧只能被包含在一個條帶中。式(8)表示條帶唯一性:如果條帶k存在,則該條帶只能被包含在一個板材中。式(9)表示條帶長度約束:同一個條帶中任意堆棧的產品項長度之和小于等于該條帶長度。式(10)表示板材總寬度約束:同一個條帶中的堆棧寬度之和小于等于板材寬度。式(11)表示板材總長度約束:同一個板材中的條帶長度之和小于等于板材長度。

注意到,將產品項旋轉90°并不會改變產品的本質,但是上述模型只考慮了產品不旋轉的情形,下面改進模型來將旋轉的情形考慮進去。

產品項具有不同的屬性,包括編號、材料、長度、寬度和所屬訂單。產品旋轉90°意味著將項目的長度與寬度互換。于是,對產品項i,若產品項i*滿足其長度等于i的寬度,寬度等于i的長度,且其他屬性完全相同,則將產品項i*稱為產品項i的對偶項目。

將所有產品項的對偶項目作為虛擬項目引入規(guī)劃,此時項目數(shù)等于原項目的2倍,即n′=2n。令i+n為i的對偶項目。于是改進后的數(shù)學模型只需要在原有基礎上增添一個新的約束條件,稱其為對偶約束:

(12)

1.2 帶對偶項的降序有限首次適應算法

基于文獻[14]中提出的有限首次適應算法(finite first fit algorithm,FFF),將對偶項考慮進去,并引入同寬產品聚集概率對FFF算法進行改進,提出了帶對偶項的降序有限首次適應算法(descending finite first fit algorithm-dual,DFFF-dual)。

FFF算法,首先根據(jù)輸入產品項列表的長度和寬度進行降序排列。然后順序遍歷所有產品,將產品項裝入一個空的堆棧中并從產品項列表中刪除已裝入的產品項。然后通過一個概率閾值P(稱為同寬產品聚集概率)來決定是否繼續(xù)遍歷尋找寬度相同的產品項放入同一堆棧中。后續(xù)將通過對概率閾值參數(shù)P尋優(yōu)來進一步優(yōu)化算法。當一個堆棧裝滿了所需的產品項后,生成一個長度與該堆棧相同的新條帶來將其裝入。在該新條帶中生成一個新的空堆棧,按上述方式去遍歷并裝入新的產品項。以此類推,會得到被裝滿的條帶,多條同樣被裝滿的條帶就會組成一塊被裝滿的板材。如此循環(huán),最終會得到包含數(shù)據(jù)集中所有產品項的板材合集,每塊板材上有對應的產品排樣方案,所有板材及對應的排樣方案組成了輸入數(shù)據(jù)集的最終排樣方案。

DFFF-dual算法的實現(xiàn)流程大體與FFF相同。首先合并產品項列表和對應的對偶項列表,然后根據(jù)新列表降序排序。而在順序遍歷的過程中,刪去產品項時連同其對偶項一并刪去,其他排樣過程與FFF算法相同,就可以得到DFFF-dual算法,算法的偽代碼如表1所示。

表1 帶對偶項的降序有限首次適應算法(DFFF-dual)

在算法中,P稱為同寬聚集概率,表示相同寬度的產品出現(xiàn)在同一個堆棧的可能性。通過實驗對概率值進行尋優(yōu),發(fā)現(xiàn)概率越小求解出的利用率越高,當P=0時,板材利用率較高。

2 材料強互異性的訂單組批算法

2.1 多約束混合整數(shù)規(guī)劃模型的建立

訂單組批優(yōu)化是在排樣前,依據(jù)工廠產能等約束條件將總訂單合理的分成若干加工批次,以提高生產效益的過程。可見它是排樣加工的準備工作,要建立組批問題的數(shù)學模型,關鍵是在原有基礎上添加下列約束條件:

(1)板材h只能在一個批次中,故有約束條件:

(13)

式中:ηq,h取值范圍為{0,1},ηq,h=1當且僅當板材h包含在批次q中。

(2)相同訂單的項目只能在同一批次處理,記:

(14)

則ξq,i=1當且僅當項目i在批次q中。設oi表示產品i的所屬訂單,注意到:

項目i,j都在批次q中等價于ξq,i=1∧ξq,j=1,等價于ξq,iξq,j=1,經(jīng)推導該約束可寫作:

(15)

(3)同一塊板材上的產品項的材質必須相同,記:

(16)

則ψh,i=1當且僅當項目i在板材h上。設mi表示產品i的材料,于是該約束等價于:

(ψh,iψh,j=0∨mi=mj),i=1,…,n,j=1,…,n,h=1,…,n

(17)

(4)每批次加工的產品項個數(shù)要小于數(shù)量限制nm:

(18)

(5)每批次加工的產品項總面積要小于產能限制Sm:

(19)

于是,訂單組批問題的混合整數(shù)規(guī)劃模型為:

(20)

s.t. (5)(6)(7)(8)(9)(10)
(11)(12)(14)(16)(18)(19)

αj,i∈{0,1},j=1,…,n,i=j,…,n
βk,j∈{0,1},k=1,…,n,j=k,…,n
γh,k∈{0,1},h=1,…,n,k=h,…,n
ηq,h∈(0,1),q=1,…,n,h=q,…,n

2.2 二階段貪心算法

設計模型的求解算法,只需要對總產品項列表做劃分,其每個劃分出的子項目列表都滿足上述約束,再對每個子項目列表應用排樣算法,就可以得出組批及排樣結果。

為了保證交貨期,要求訂單相同的項目一定在同一批次中,于是可以采用二階段貪心算法在保證約束條件的前提下不斷地將某個訂單的項目放入子項目列表,直到放不下為止,其算法流程如表2所示。

表2 二階段貪心算法

同其他貪心算法類似,并在第3步之前,對訂單列表依項目數(shù)進行排序,先處理規(guī)模大的訂單,再處理小訂單,所得的結果會更優(yōu)良。

2.3 考慮相似度的二階段貪心算法

對上述二階段貪心算法求解的結果進行分析發(fā)現(xiàn),由于訂單中產品項除形狀外,每個訂單所用到的材料也具有強互異性。材料差異將導致一個加工批次常出現(xiàn)某種材料的板材上只有少數(shù)幾個產品,這會大幅降低板材利用率。為使利用率最大化,要讓材料相同的項目盡可能在同一批次中進行加工。這意味著,在“貪心”地選取訂單的時候,要注意待選訂單與已選訂單所用材料的相似程度。優(yōu)先選擇材料相似度高的訂單,最好是被包含在已有訂單的材料集合中,這樣可以讓材料相同的產品項盡可能的湊在一起,以此提高板材的利用率。

為定量衡量訂單所用材料的相似程度,對訂單的材料相似度進行定義。記m(o)表示訂單o中所有項目所用材料構成的集合。對訂單集A={o1,o2,…,oq},記m(A)=∪o∈Am(o)。于是可以定量描述兩個訂單集A、B的材料相似度:R(A,B)=|m(A)∩m(B)|/|m(A)∪m(B)|。

(21)

記t(o)為訂單o的所有項目構成的集合,對訂單集A,記t(A)=∪o∈At(o),于是組批問題中的約束(18)就變成了|t(Oi)|≤nm,i=1,…N。再記l(t)、w(t)分別表示項目t的長度和寬度,則約束(19)就變?yōu)?

(22)

于是,二階段算法中第一階段的數(shù)學模型為求訂單集O的一個劃分O1,O2,…,ON,使得:

(23)

subject to: (22) (24)

|t(Oi)|≤nm,i=1,…,N

(24)

在將訂單之間材料相似度納入考慮后,對上述二階段貪心算法加以改進提出考慮相似度的二階段貪心算法,其具體流程如表3所示。

表3 考慮材料相似度的二階段貪心算法

3 實驗與分析

現(xiàn)有矩形排樣測試數(shù)據(jù)集所含的產品項數(shù)量都較少,并且所用材料都是相同的,不符合大規(guī)模個性化訂單形狀、材料兩重強互異性的特點。所以,在進行實驗驗證時選用2022年中國研究生數(shù)學建模競賽提供的工廠生產過程中真實的訂單數(shù)據(jù)集作為實驗對象。其中A1～A4數(shù)據(jù)集均包含800個左右形狀存在強互異性的待加工矩形件;B1～B5每個數(shù)據(jù)集包含20 000～30 000個形狀、材料都存在強互異性的待加工矩形件,適合于算法的驗證。

3.1 矩形排樣實驗驗證

在此假定每塊板材的規(guī)格不變L×W=2440 mm×1220 mm,用DFFF-dual算法和文獻[14]中FFF算法分別對數(shù)據(jù)集A的4個子數(shù)據(jù)集進行求解,并將兩個算法求解的結果在表4中進行對比。

表4 FFF與DFFF-dual對A數(shù)據(jù)集求解結果對比

由于訂單規(guī)模龐大,在此從A1、A2中各隨機選取10個DFFF-dual算法求解的排樣效果圖進行范例展示,如圖2和圖3所示。

圖2 數(shù)據(jù)集A1的部分排樣效果圖

圖3 數(shù)據(jù)集A2的部分排樣效果圖

3.2 矩形排樣實驗結果分析

通過DFFF-dual算法求解出的排樣方案相比于FFF算法有2%的提升,并且板材的利用率可以高達95%左右,可以滿足實際加工生產的要求。不僅如此,算法對數(shù)據(jù)集求解的時長均在1 s以內,由此證明DFFF-dual是求解排樣問題快速高效的算法。通過觀察數(shù)據(jù)集求解結果表格,對比FFF和DFFF-dual的輸出結果和利用率可以得出結論:

(1)從板材原片利用率上看,DFFF-dual算法優(yōu)于FFF算法,并且樣本數(shù)量越大,樣本形狀越復雜多樣,DFFF-dual算法求解結果相較FFF算法提升會越大;

(2)從算法時間復雜度上看,FFF算法優(yōu)于DFFF-dual算法,DFFF-dual運行時間大致為FFF的2～3倍,這是由于引入對偶項目引起的。但兩個算法的求解時長都在毫秒級別,對求解效率的影響可以忽略。

3.3 訂單組批實驗驗證

以數(shù)據(jù)集B1～B5為對象進行實驗驗證,同樣約定每塊板材的規(guī)格不變。另外,假定單個批次產品項總數(shù)上限nm=1000,單個批次產品項的面積總和上限Sm=2502。分別使用TSG和TSG-S算法對數(shù)據(jù)集進行組批優(yōu)化,得到不同批次的訂單列表,之后均用DFFF-dual算法對每個單獨批次的產品數(shù)據(jù)列表進行排樣優(yōu)化,得到組批排樣方案。兩個算法組批并排樣的結果對比如表5所示。

表5 TSG與TSG-S對B數(shù)據(jù)集求解結果對比

由于數(shù)據(jù)集B求解得到的圖示數(shù)量龐大,故在此從B1、B3中各隨機選取10個用TSG-S算法組批、用DFFF-dual算法排樣的示意圖進行范例展示,如圖4和圖5所示。

圖4 數(shù)據(jù)集B1的部分排樣效果圖

圖5 數(shù)據(jù)集B3的部分排樣效果圖

3.4 訂單組批實驗結果分析

通過對比表4中兩種組批優(yōu)化算法的結果,可以發(fā)現(xiàn),在使用相同排樣優(yōu)化算法的情況下,TSG-S算法的效果要遠遠優(yōu)于TSG算法,每個數(shù)據(jù)集的利用率都能提高11%～12%,這說明了在組批優(yōu)化問題中,用本文提出的方法將訂單所用材料的相似度定量考慮進去后,能夠大幅度減少每個批次中所使用板材的數(shù)量,提高利用率。

對兩種組批優(yōu)化算法的相似度矩陣進行可視化,繪制如下相似度熱力圖,如圖6所示。

圖6 TSG及TSG-S的相似度矩陣熱力圖

顏色越深相似度矩陣中所對應的數(shù)值越大。可以看出,TSG算法比TSG-S算法顏色深,這表明后者對組批優(yōu)化問題數(shù)學模型的求解效果更加好,這與實際運行出的結果相一致,直觀顯現(xiàn)出TSG-S算法的優(yōu)勢。

4 結論

針對形狀強互異性問題,本文在現(xiàn)有FFF排樣優(yōu)化算法的基礎上,將旋轉的情況納入考慮,并引入同寬產品聚集概率對其進行改進,提出適用于三階段齊頭切精確排樣的DFFF-dual算法。DFFF-dual算法優(yōu)化效果相較性能優(yōu)良的FFF算法還要有顯著的提升。在對數(shù)據(jù)集A進行實驗驗證時,平均求解時長在100 ms以內,比現(xiàn)有的傳統(tǒng)算法、啟發(fā)式算法都快。并且,在保證速度的同時又不失性能,在測試的4個數(shù)據(jù)集上,板材利用率可達95%左右。

針對材料強互異性問題,提出定量描述訂單之間材料相似度的方法,將所用材料相近的訂單最大程度組合進同一加工批次,由此得到TSG-S算法。通過實驗驗證,使用TSG-S算法對數(shù)據(jù)集B進行組批優(yōu)化后,再對每個批次使用DFFF-dual算法進行排樣優(yōu)化,最終板材利用率最高可以達到80.10%,TSG-S算法相較于TSG算法的性能提升了11%～12%。

綜上所述,本文提出的DFFF-dual和TSG-S算法在解決大批量兩重互異性矩形件組批排樣優(yōu)化問題上效果顯著,對于實際生產活動具有指導意義。