基于改進迭代貪婪算法的預制構件調度研究

陳竑翰，熊福力，曹勁松，李 志

(西安建筑科技大學 信息與控制工程學院，西安 710055)

0 引言

在混凝土預制構件生產的系統中，利潤最大化是企業的首要目標。決策者需要根據兩個重要的約束條件，即企業生產能力約束和交貨期約束，在兩個約束條件下會迫使企業來決定是否接受或拒絕哪些候選訂單以及如何對訂單進行安排。這種問題被稱為訂單接受與調度問題(order acceptance and scheduling, OAS)[1]。

有許多精確的方法被用來解決小規模的OAS問題，例如分枝定界算法[2]和動態規劃算法[3]。目前已經證實流水車間的OAS問題屬于NP-hard問題[4]，所以當問題規模過大時為了在合理的計算時間內獲得近似最優解，一些學者提出了有效的啟發式算法[5]和元啟發式算法[6-7]進行求解。鄭凡等[8]針對訂單接收的流水車間調度問題，提出了一種并行變鄰域搜索算法,采用雙串表示方法、新型的鄰域結構和并行搜索機制解決了該問題。Wang等人[9]考慮了模具制造、預制構件儲存和運輸的影響，以最小化延遲和早期懲罰的總成本，并通過GA解決了這一調度問題。Prata[10]考慮了鑄梁模具有效生產能力的約束條件，并采用整數線性規劃方法來最小化訂單生產損失。Ko等人[11]討論了相鄰工序之間帶緩沖區容量的預制調度問題，并通過GA進行求解。

目前在預制構件的生產中還未對OAS問題進行過研究。因此，本文以最大化總凈收益為目標，提出了一個預制流水車間的OAS模型。針對此模型本文設計了一種改進的IG算法。在改進的IG算法中，在重建過程之前加入了一種構造啟發式的規則，并且結合閾值接受算法設計了一種自適應接受準則。最后將改進的IG算法與禁忌搜索算法、遺傳算法以及經典IG算法進行了對比分析。結果表明改進的IG算法能獲得更好的效果。

1 問題描述

在生產過程中需滿足以下條件：1)相鄰工序之間工件的安裝時間和運輸時間可忽略不計;2)每道工序一次最多只能處理一個工件；3)每個工件一次最多只能在一道工序上處理；4)工件在工序上處理完成之前不能被其他工件搶占。

2 生產調度模型

(1)

訂單j的拖期時間Tj和完工時間Cj可由以下約束計算。

(2)

(3)

(4)

(5)

(6)

(7)

xj∈{0, 1}?j

(8)

yj,[k]∈{0, 1}?j,k

(9)

其中:式(2)和(3)表示每個訂單的拖期時間的約束，式中Ω是一個大數；式(4)確保將每個接受的訂單分配到一個位置，式中[k]表示訂單序列的位置指標；式(5)表示每個位置只能分配一個訂單；式(6)表示預制供應鏈環境下連續工序的完工時間,式中C[k]是指在第k個位置上訂單的完工時間,pj,s是指訂單j在工序s上的處理時間；式(7)表示預制供應鏈環境下并行工序的完工時間。式(8)和式(9)表示變量xj和yj,[k]均為二進制變量，若訂單j被接受，xj取1，否則為0；若訂單j分配到了訂單序列第k個位置，yj,[k]取1,否則為0。

3 改進迭代貪婪算法

迭代貪婪(iterative greedy，IG)算法最初是由Ruiz[12]提出的，是對貪婪搜索方法的一種擴展。經典IG算法主要由兩個主要階段構成，一個是可行解的破壞階段，另一個是可行解的重建階段。在破壞階段中，從完整的可行解中刪除一些元素。然后在重建階段通過應用一些貪婪規則重新構成一個完整的可行解。最后對完整的可行解進行選擇性接受。由于其在調度問題上良好的尋優能力，目前它已在許多領域得到了廣泛的應用。本文在結合預制構件訂單接受與調度問題的基礎上提出了一種結合構造式啟發規則的帶閾值接受的迭代貪婪算法(iterative greedy with threshold acceptance，IGTA)，以下各節詳細介紹了IGTA算法的主要過程。

3.1 編碼方式

3.2 基于構造啟發式的破壞-重建策略

在經典IG算法中的破壞-重建階段中分為兩個主要過程，首先在破壞過程中，從當前解中隨機選擇g個訂單并將其移除，然后可以得到兩組序列，一組是由剩余的訂單組成的部分序列，另外一組是有移除的訂單組成的部分序列，其中，移除訂單數即破壞因子g通常在(2，3，...，8)中取值；其次在重建過程中，將移除訂單組成的部分序列從左至右逐一插入所有的位置，并進行比較，最終將訂單插入是目標值增加最多的位置，從而可以得到一個當前最優解。

從經典IG算法中可以看出，重建過程直接對剩余訂單序列進行插入操作，并未充分利用剩余訂單集合中交貨期、處理時間以及最大凈收益等信息，很可能導致求解質量下降。因此，為了在調度序列重建過程中有效改善目標值，本文結合預制構件訂單接受與調度問題數據信息，提出了一種基于構造啟發式規則的重建操作策略，如圖1所示，首先利用公式(10)在剩余訂單集合中對ξj進行遞減排序，然后再從移除訂單集合中逐個抽出訂單，并插入到使得總凈利潤最小的剩余訂單序列位置，直到移除訂單集合中沒有訂單。

圖1 基于構造啟發式規則的破壞-重建策略圖

(10)

3.3 局部鄰域搜索

本文中的鄰域搜索方法采用是一種插入式的局部鄰域搜索方法。其基本思想是：每次從當前解中隨機地選擇一個訂單，將訂單從左至右逐一試插，最終將訂單插入是目標值增加最多的位置。如果通過鄰域搜索找到的新解優于當前解，則對當前解進行替換并繼續搜索，否則就結束搜索。

3.4 閾值接受準則

經典IG算法中的接受準則是基于模擬退火算法中的按概率接受新解作為當前解。為了幫助IG算法能夠擁有更好擾動性能，并能更加容易跳出局部最優，本文通過結合一種閾值接受算法，提出了一種新的閾值接受準則。閾值接受算法是對模擬退火算法的改進，它是使用閾值對整個求解過程進行控制。閾值接受準則能夠使IG算法在一定范圍內接受稍差的解，從而使算法跳出局部最優值，與模擬退火算法中的接受準則相比，閾值接受準則能進行更小范圍內的搜索[13]。

在本文中，為了綜合考慮訂單規模和優化效率，初始閾值設置為T0=n2，其中n表示訂單數；閾值衰減系數α是隨著迭代次數Iter不斷進行變化的一個自適應值，由式(11)確定。

(11)

3.5 終止條件

本文中提出的IGTA算法為了綜合考慮問題的規模，且保證算法充分收斂情況下，設定終止條件為10*n2毫秒的程序運行時間。其中，n為待決策訂單的數量。

IGTA算法的偽代碼如算法1所示。

算法1：IGTA算法偽代碼

1:輸入初始可行解π ，初始目標值f (π)

2: 設置算法參數，其中包括：移除訂單數g以及初始化閾值T0；

3: 設定初始解為當前最好解 π*← π

4: while 不滿足結束條件 do

5: 令 π’← π，flag=1, Iter=1，利用式(11)計算α;

6: for i=1 to g do

7: 從π’中隨機選擇一個訂單移除，并將其置入移除訂單集，組成剩余訂單序列πa和移除訂單序列πr；

8: end for

9: for i=1 to g do

10: 通過公式(10)中的構造式規則對剩余訂單序列πa進行遞減排序優化得到πa’ ；

11: 從移除訂單序列πr中選擇一個訂單將其插入πa’中所有可能位置中能使目標增加最多的位置，得到最優插入序列π’；

12: end for

13: while flag=1 do

14: flag=0

15: for i=1 to n do

16: 從π’中不重復地隨機移除一個訂單并將其插入π’所有剩余位置中的最優位置，得到鄰域搜索解π’’；

17: if f(π’’ )>f(π’ ) then

18: π’ ←π’’, flag=1;

19: end if

20: end for

21: end while

22: if f(π’’ )>f(π) then

23: π ←π’’

24: if f(π)>f(π*) then

25: π*←π

26: end if

27: elseif (f(π )-f(π’’ ))<α×T0then

28: π←π’’

29: end if

30: end while

31: return π*

4 實驗結果及分析

本節根據所研究問題的特點設計了仿真實驗，分析了本文所提出算法對不同問題規模求解的效果，并通過與禁忌搜索算法(tabu search，TS)、遺傳算法(genetic algorithm，GA)以及經典IG算法進行比較，對算法的魯棒性和求解質量給出分析結果。

4.1 測試實例

表1 生產數據

4.2 仿真結果與分析

所有實驗均通過Matlab 2017b編程實現，并在計算機配置為Microsoft Windows 10，處理器為Intel Core i5-6300HQ CPU @ 2.3 GHz，8 GB RAM的個人電腦上運行。本文針對訂單n為20，40和60的3種小、中、大規模的問題測試實例在實驗中使用了禁忌搜索算法，遺傳算法以及經典IG算法和本文所提出的IGTA算法進行對比，它們將在每個問題實例下進行30次測試。總計運行3 240(27×30×4)次。在本文中GA算法中的種群數量，交叉率和變異率分別選取為Ps=100，Pc=0.8，Pm=0.02；TS算法中的禁忌長度和鄰域大小分別取(n(n-1)/2)1/2和2n，其中n表示待決策訂單的數量；經典IG算法中的參數分別取g=4，T=0.4；本文中的IGTA算法中的閾值和破壞因子分別取T0=n2，g=4。

具體來說，針對每個測試的問題實例，分別比較4種算法在不同實例上的求解效果，文中用最優目標均值(AVG)和最大值(MAX)來對算法的求解質量進行評估，以及使用標準差(STD)來評價算法的魯棒性。此外對于某個問題規模下的測試實例l，考慮到算法會重復運行M次，本文定義了一個平均相對百分偏差(average relative percentage deviation，ARPD)來對各個規模下不同算法的性能進行評估，計算公式如(12)：

(12)

其中:TNRalg(l,m)表示對于給定算法alg在實例l下運行第m次所獲得的目標值，TNRbest(l)表示在實例l下所有實驗得到的最優目標值，L表示同規模問題下的測試實例之和。

在問題規模n=20情況下的仿真實驗結果如表2所示。

由表2所示的實驗結果比較分析可知：本文所提出的IGTA算法表現較好，在最優值的尋找方面均能找到不差于其余3種對比算法的解，在均值和標準差方面IGTA算法與經典IG算法求解效果相近。

表2 n=20 時 4種算法的性能比較

在問題規模n=40和n=60情況下的仿真實驗結果如表3和表4所示。由表3和表4中所列出的數據可以明顯的看出隨著訂單規模的增加，改進的IG算法無論是在最優值的尋找還是整體均值的計算都能找到4種算法中最好的解。除此之外，從上表的STD對比中可以看出，本文提出的IGTA算法始終保持著比較穩定的狀態，由此說明IGTA算法相比于其余3種算法具有更好的魯棒性。

為了更加直觀的展示4種算法在不同訂單規模下的求解效果對比，本文通過提出一種平均相對偏差的評價指標可以更加清楚的看到在不同問題規模下的4種算法的差異，4種對比算法的總體ARPD對比柱狀圖如圖2所示。

表3 n=40 時 4種算法的性能比較

表4 n=60 時 4種算法的性能比較

圖2 4種算法在不同規模下的ARPD對比圖

從圖2中可以看出當訂單規模為20的時候所有算法的ARPD值均很小，隨著問題規模的增大，IGTA算法的ARPD值呈現出遞增趨勢。且在哪種訂單規模下，統計上IGTA算法的ARPD值都是最小的，由此我們可以得出IGTA算法在小、中、大規模問題下的求解質量均優于其余3種對比算法。

5 結束語

本文針對預制流水車間的訂單接受與調度問題，構建了線性整數規劃模型，并通過提出一種改進的迭代貪婪算法來求解這一問題，并通過計算仿真的方式與經典IG，TS以及GA算法進行對比。結果通過最優目標值、目標均值、標準差以及平均相對百分偏差，4個性能評價指標進行對比分析，表明了本文提出的IGTA算法有良好的求解效果。下一步的研究可以對IGTA算法中的局部搜索作進一步改良以開發效率更高的預制流水車間的訂單接受與調度模型的元啟發式算法；同時，在未來的研究中可以將本文方法推廣到汽車制造，鋼生產等按訂單進行生產的行業中。