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

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

0 引言

在混凝土預(yù)制構(gòu)件生產(chǎn)的系統(tǒng)中，利潤(rùn)最大化是企業(yè)的首要目標(biāo)。決策者需要根據(jù)兩個(gè)重要的約束條件，即企業(yè)生產(chǎn)能力約束和交貨期約束，在兩個(gè)約束條件下會(huì)迫使企業(yè)來(lái)決定是否接受或拒絕哪些候選訂單以及如何對(duì)訂單進(jìn)行安排。這種問(wèn)題被稱(chēng)為訂單接受與調(diào)度問(wèn)題(order acceptance and scheduling, OAS)[1]。

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

目前在預(yù)制構(gòu)件的生產(chǎn)中還未對(duì)OAS問(wèn)題進(jìn)行過(guò)研究。因此，本文以最大化總凈收益為目標(biāo)，提出了一個(gè)預(yù)制流水車(chē)間的OAS模型。針對(duì)此模型本文設(shè)計(jì)了一種改進(jìn)的IG算法。在改進(jìn)的IG算法中，在重建過(guò)程之前加入了一種構(gòu)造啟發(fā)式的規(guī)則，并且結(jié)合閾值接受算法設(shè)計(jì)了一種自適應(yīng)接受準(zhǔn)則。最后將改進(jìn)的IG算法與禁忌搜索算法、遺傳算法以及經(jīng)典IG算法進(jìn)行了對(duì)比分析。結(jié)果表明改進(jìn)的IG算法能獲得更好的效果。

1 問(wèn)題描述

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

2 生產(chǎn)調(diào)度模型

(1)

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

(2)

(3)

(4)

(5)

(6)

(7)

xj∈{0, 1}?j

(8)

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

(9)

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

3 改進(jìn)迭代貪婪算法

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

3.1 編碼方式

3.2 基于構(gòu)造啟發(fā)式的破壞-重建策略

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

從經(jīng)典IG算法中可以看出，重建過(guò)程直接對(duì)剩余訂單序列進(jìn)行插入操作，并未充分利用剩余訂單集合中交貨期、處理時(shí)間以及最大凈收益等信息，很可能導(dǎo)致求解質(zhì)量下降。因此，為了在調(diào)度序列重建過(guò)程中有效改善目標(biāo)值，本文結(jié)合預(yù)制構(gòu)件訂單接受與調(diào)度問(wèn)題數(shù)據(jù)信息，提出了一種基于構(gòu)造啟發(fā)式規(guī)則的重建操作策略，如圖1所示，首先利用公式(10)在剩余訂單集合中對(duì)ξj進(jìn)行遞減排序，然后再?gòu)囊瞥唵渭现兄饌€(gè)抽出訂單，并插入到使得總凈利潤(rùn)最小的剩余訂單序列位置，直到移除訂單集合中沒(méi)有訂單。

圖1 基于構(gòu)造啟發(fā)式規(guī)則的破壞-重建策略圖

(10)

3.3 局部鄰域搜索

本文中的鄰域搜索方法采用是一種插入式的局部鄰域搜索方法。其基本思想是：每次從當(dāng)前解中隨機(jī)地選擇一個(gè)訂單，將訂單從左至右逐一試插，最終將訂單插入是目標(biāo)值增加最多的位置。如果通過(guò)鄰域搜索找到的新解優(yōu)于當(dāng)前解，則對(duì)當(dāng)前解進(jìn)行替換并繼續(xù)搜索，否則就結(jié)束搜索。

3.4 閾值接受準(zhǔn)則

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

在本文中，為了綜合考慮訂單規(guī)模和優(yōu)化效率，初始閾值設(shè)置為T(mén)0=n2，其中n表示訂單數(shù)；閾值衰減系數(shù)α是隨著迭代次數(shù)Iter不斷進(jìn)行變化的一個(gè)自適應(yīng)值，由式(11)確定。

(11)

3.5 終止條件

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

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

算法1：IGTA算法偽代碼

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

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

3: 設(shè)定初始解為當(dāng)前最好解 π*← π

4: while 不滿(mǎn)足結(jié)束條件 do

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

6: for i=1 to g do

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

8: end for

9: for i=1 to g do

10: 通過(guò)公式(10)中的構(gòu)造式規(guī)則對(duì)剩余訂單序列πa進(jìn)行遞減排序優(yōu)化得到πa’ ；

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

12: end for

13: while flag=1 do

14: flag=0

15: for i=1 to n do

16: 從π’中不重復(fù)地隨機(jī)移除一個(gè)訂單并將其插入π’所有剩余位置中的最優(yōu)位置，得到鄰域搜索解π’’；

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 實(shí)驗(yàn)結(jié)果及分析

本節(jié)根據(jù)所研究問(wèn)題的特點(diǎn)設(shè)計(jì)了仿真實(shí)驗(yàn)，分析了本文所提出算法對(duì)不同問(wèn)題規(guī)模求解的效果，并通過(guò)與禁忌搜索算法(tabu search，TS)、遺傳算法(genetic algorithm，GA)以及經(jīng)典IG算法進(jìn)行比較，對(duì)算法的魯棒性和求解質(zhì)量給出分析結(jié)果。

4.1 測(cè)試實(shí)例

表1 生產(chǎn)數(shù)據(jù)

4.2 仿真結(jié)果與分析

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

具體來(lái)說(shuō)，針對(duì)每個(gè)測(cè)試的問(wèn)題實(shí)例，分別比較4種算法在不同實(shí)例上的求解效果，文中用最優(yōu)目標(biāo)均值(AVG)和最大值(MAX)來(lái)對(duì)算法的求解質(zhì)量進(jìn)行評(píng)估，以及使用標(biāo)準(zhǔn)差(STD)來(lái)評(píng)價(jià)算法的魯棒性。此外對(duì)于某個(gè)問(wèn)題規(guī)模下的測(cè)試實(shí)例l，考慮到算法會(huì)重復(fù)運(yùn)行M次，本文定義了一個(gè)平均相對(duì)百分偏差(average relative percentage deviation，ARPD)來(lái)對(duì)各個(gè)規(guī)模下不同算法的性能進(jìn)行評(píng)估，計(jì)算公式如(12)：

(12)

其中:TNRalg(l,m)表示對(duì)于給定算法alg在實(shí)例l下運(yùn)行第m次所獲得的目標(biāo)值，TNRbest(l)表示在實(shí)例l下所有實(shí)驗(yàn)得到的最優(yōu)目標(biāo)值，L表示同規(guī)模問(wèn)題下的測(cè)試實(shí)例之和。

在問(wèn)題規(guī)模n=20情況下的仿真實(shí)驗(yàn)結(jié)果如表2所示。

由表2所示的實(shí)驗(yàn)結(jié)果比較分析可知：本文所提出的IGTA算法表現(xiàn)較好，在最優(yōu)值的尋找方面均能找到不差于其余3種對(duì)比算法的解，在均值和標(biāo)準(zhǔn)差方面IGTA算法與經(jīng)典IG算法求解效果相近。

表2 n=20 時(shí) 4種算法的性能比較

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

為了更加直觀的展示4種算法在不同訂單規(guī)模下的求解效果對(duì)比，本文通過(guò)提出一種平均相對(duì)偏差的評(píng)價(jià)指標(biāo)可以更加清楚的看到在不同問(wèn)題規(guī)模下的4種算法的差異，4種對(duì)比算法的總體ARPD對(duì)比柱狀圖如圖2所示。

表3 n=40 時(shí) 4種算法的性能比較

表4 n=60 時(shí) 4種算法的性能比較

圖2 4種算法在不同規(guī)模下的ARPD對(duì)比圖

從圖2中可以看出當(dāng)訂單規(guī)模為20的時(shí)候所有算法的ARPD值均很小，隨著問(wèn)題規(guī)模的增大，IGTA算法的ARPD值呈現(xiàn)出遞增趨勢(shì)。且在哪種訂單規(guī)模下，統(tǒng)計(jì)上IGTA算法的ARPD值都是最小的，由此我們可以得出IGTA算法在小、中、大規(guī)模問(wèn)題下的求解質(zhì)量均優(yōu)于其余3種對(duì)比算法。

5 結(jié)束語(yǔ)

本文針對(duì)預(yù)制流水車(chē)間的訂單接受與調(diào)度問(wèn)題，構(gòu)建了線(xiàn)性整數(shù)規(guī)劃模型，并通過(guò)提出一種改進(jìn)的迭代貪婪算法來(lái)求解這一問(wèn)題，并通過(guò)計(jì)算仿真的方式與經(jīng)典IG，TS以及GA算法進(jìn)行對(duì)比。結(jié)果通過(guò)最優(yōu)目標(biāo)值、目標(biāo)均值、標(biāo)準(zhǔn)差以及平均相對(duì)百分偏差，4個(gè)性能評(píng)價(jià)指標(biāo)進(jìn)行對(duì)比分析，表明了本文提出的IGTA算法有良好的求解效果。下一步的研究可以對(duì)IGTA算法中的局部搜索作進(jìn)一步改良以開(kāi)發(fā)效率更高的預(yù)制流水車(chē)間的訂單接受與調(diào)度模型的元啟發(fā)式算法；同時(shí)，在未來(lái)的研究中可以將本文方法推廣到汽車(chē)制造，鋼生產(chǎn)等按訂單進(jìn)行生產(chǎn)的行業(yè)中。