一種求解單機(jī)總加權(quán)延遲調(diào)度問題的改進(jìn)蟻群算法

喬?hào)|平 裴 杰 文笑雨 肖艷秋 焦建強(qiáng)

1. 鄭州輕工業(yè)學(xué)院機(jī)電工程學(xué)院，鄭州，450002 2.河南省機(jī)械裝備智能制造重點(diǎn)實(shí)驗(yàn)室，鄭州，450002

0 引言

單機(jī)總加權(quán)延遲調(diào)度(single machine total weighted tardiness scheduling, SMTWTS)問題是考慮作業(yè)完工時(shí)間滿足預(yù)定交貨期，優(yōu)化目標(biāo)為最小化加權(quán)延遲成本的單機(jī)調(diào)度問題。LAWLER[1]證明了SMTWTS問題為NP-Hard問題。隨著求解規(guī)模的擴(kuò)大，該類問題求解復(fù)雜度及求解時(shí)間呈現(xiàn)指數(shù)級增長。針對該問題設(shè)計(jì)有效的調(diào)度算法，一直是生產(chǎn)調(diào)度領(lǐng)域的重要研究課題之一。目前，對該類問題已提出一系列有效的求解方法。依照優(yōu)化機(jī)制和優(yōu)化行為的不同，解決SMTWTS問題的算法可分為精確算法、基于優(yōu)先分配規(guī)則的構(gòu)造性啟發(fā)式方法和元啟發(fā)式算法[2]。BABU等[3]構(gòu)建的分支定界算法解決了50個(gè)作業(yè)規(guī)模的基準(zhǔn)問題；YIN等[4]結(jié)合候選作業(yè)特征提出一種新的構(gòu)造性啟發(fā)式規(guī)則(mixed dispatch rule, MDR)，以更有效地求解SMTWTS問題；YAHYAOUI等[5]、FU等[6]研究了求解SMTWTS問題的變鄰域搜索(variable neighborhood search，VNS)算法；SUPPIAH等[7]、UMI等[8]分別采用遺傳算法和禁忌搜索算法(TS)對SMTWTS問題作了進(jìn)一步探討；MADUREIRA等[9]、葉強(qiáng)等[10]針對OR-Library中的多個(gè)基準(zhǔn)問題，研究分析了蟻群算法對SMTWTS問題求解的有效性。

分支定界、動(dòng)態(tài)規(guī)劃等精確算法雖能在一定條件下產(chǎn)生最優(yōu)解決方案，但受限于計(jì)算復(fù)雜性，僅能有效解決較小規(guī)模的實(shí)例問題?；趦?yōu)先分配規(guī)則的構(gòu)造性啟發(fā)式方法為求解單機(jī)調(diào)度問題提供了一種快速排序方法，但算法求解質(zhì)量依賴于調(diào)度規(guī)則的選取。以模擬自然現(xiàn)象及規(guī)律而發(fā)展的元啟發(fā)式算法更易在合理時(shí)間內(nèi)以較大概率求得問題的滿意解，為復(fù)雜調(diào)度問題的研究提供了新的思路和手段，成為目前求解調(diào)度問題的主要方法。

蟻群優(yōu)化(ant colony optimization，ACO)算法[11]已在作業(yè)車間調(diào)度[12]、路徑規(guī)劃[13]等優(yōu)化領(lǐng)域中得到廣泛應(yīng)用。鑒于該算法的諸多優(yōu)良特性，本文針對SMTWTS問題特點(diǎn)，提出一種基于信息素差異更新的改進(jìn)蟻群優(yōu)化 (improved ant colony optimization，IACO)算法以更有效地求解SMTWTS問題。首先，該算法采用確定性選擇與隨機(jī)性選擇相結(jié)合的策略，結(jié)合MDD優(yōu)先規(guī)則改進(jìn)了啟發(fā)式信息的設(shè)定。其次，通過引入正負(fù)反饋機(jī)制，提出一種改進(jìn)的差異化信息素更新策略，并結(jié)合局部優(yōu)化策略實(shí)現(xiàn)了對調(diào)度序列的進(jìn)一步優(yōu)化。最后，OR-Library中多個(gè)不同規(guī)模基準(zhǔn)算例的仿真驗(yàn)證了算法具有較好的尋優(yōu)性能。

1 SMTWTS問題描述

單機(jī)總加權(quán)延遲調(diào)度問題1‖ΣwjTj可描述如下：n個(gè)相互獨(dú)立的作業(yè)安排在1臺(tái)機(jī)器上完成，機(jī)器連續(xù)處理且同一時(shí)刻最多只能完成1個(gè)作業(yè)任務(wù)，各作業(yè)均可在0時(shí)刻到達(dá)并加工，作業(yè)間的加工順序不預(yù)先設(shè)定。第j(j=1，2，…，n)個(gè)作業(yè)有3項(xiàng)獨(dú)立參數(shù)：加工時(shí)間pj、權(quán)重即延遲懲罰系數(shù)wj及交貨期dj，各作業(yè)參數(shù)與其在加工序列中的位置無關(guān)。

(1)

求解中，對該調(diào)度模型作如下假設(shè)：①各作業(yè)無準(zhǔn)備時(shí)間，在0時(shí)刻，所有作業(yè)均可被處理；②作業(yè)的處理時(shí)間、交貨日期和權(quán)重在計(jì)劃開始時(shí)均為已知且確定；③不同作業(yè)具有相同的優(yōu)先級，其加工順序不預(yù)先設(shè)定；④工件在機(jī)器上僅加工一次，且機(jī)器一次只能處理一個(gè)作業(yè)；⑤機(jī)器進(jìn)行連續(xù)加工，不允許搶占和中斷；⑥當(dāng)前作業(yè)完成后，下一個(gè)計(jì)劃作業(yè)立即開始執(zhí)行。

2 求解SMTWTS問題的改進(jìn)蟻群算法

2.1 描述SMTWTS問題的變量定義

在IACO算法中，每個(gè)螞蟻通過對作業(yè)節(jié)點(diǎn)的逐步選取，最終構(gòu)建出完整的作業(yè)序列。解決方案的構(gòu)建過程受啟發(fā)式信息和信息素指導(dǎo)，初始信息素及啟發(fā)式信息分別結(jié)合最早交貨期(earliest due date, EDD)優(yōu)先規(guī)則和修正的MDD啟發(fā)式規(guī)則給出。每次迭代中，當(dāng)所有螞蟻都構(gòu)建出完整的解決方案后，采用改進(jìn)的差異化信息素更新規(guī)則對構(gòu)成該可行解的各節(jié)點(diǎn)間的信息素做更新處理，然后引入局部搜索以改進(jìn)每次迭代搜索到的最佳解決方案。IACO算法的相關(guān)變量定義如下：(i,j)表示在位置i處理作業(yè)j；α為信息素對螞蟻選擇路徑的影響力，α≥ 0；β表示啟發(fā)信息值的相對重要性，β≥ 0；ρ為信息素?fù)]發(fā)因子，ρ∈(0, 1)；NC為迭代計(jì)數(shù)器變量；NCmax為算法最大迭代次數(shù)；S*為當(dāng)前最優(yōu)調(diào)度序列；T*為當(dāng)前最優(yōu)調(diào)度序列的總加權(quán)延遲成本。

IACO算法的求解流程可描述如下：

Procedure單機(jī)調(diào)度問題的改進(jìn)蟻群算法

參數(shù)設(shè)置；

結(jié)合EDD優(yōu)先規(guī)則初始化各節(jié)點(diǎn)間信息素；

While不滿足終止條件 do

For 螞蟻k=1 tom

For 加工序列位置i=1 ton

按選取規(guī)則構(gòu)造可行解；

End for

End for

差異化信息素更新規(guī)則更新節(jié)點(diǎn)間信息素；

Application局部搜索策略；

If 搜索到當(dāng)前最優(yōu)解決方案π的改進(jìn)解π*

then

Setπ←π*andTπ←Tπ*

更新解決方案π相關(guān)節(jié)點(diǎn)間信息素；

End if

End while

Return最優(yōu)調(diào)度序列S*and該方案下的總加權(quán)延遲成本T；

End Procedure

2.2 編碼方式

基于問題特性的編碼方式能更好地提高算法的優(yōu)化性能。對于本文研究的1‖ΣwjTj問題，采用基于作業(yè)序列的構(gòu)建性編碼方式：初始時(shí)刻，m只螞蟻隨機(jī)選取作業(yè)j安排在加工序列的起始位置進(jìn)行處理；其次，按照2.4節(jié)中定義的多樣性選取規(guī)則逐步將尚未安排的作業(yè)添加到加工序列的后續(xù)位置，直至完成所有作業(yè)調(diào)度。編碼后得到一個(gè)完整的作業(yè)處理序列。表1給出了作業(yè)處理序列為J1-J7-J3-J2-J5-J6-J4，總加權(quán)延遲成本T=30的一個(gè)解決方案示例。

表1 基于作業(yè)序列的編碼

2.3 初始化

2.3.1初始化參數(shù)設(shè)置

令NC=0, 設(shè)置最大迭代次數(shù)NCmax，初始化當(dāng)前最優(yōu)調(diào)度序列π*為空集，當(dāng)前最優(yōu)調(diào)度序列的總加權(quán)延遲成本T*為無限大。

2.3.2初始化信息素

在所提出的改進(jìn)蟻群算法中，τij為任意時(shí)刻節(jié)點(diǎn)(i,j)間的信息素濃度。初始信息素濃度τij(0)的設(shè)定影響算法狀態(tài)轉(zhuǎn)移概率的計(jì)算，對螞蟻后續(xù)的搜索產(chǎn)生影響。若信息素釋放量遠(yuǎn)大于信息素初始值，則在正反饋機(jī)制的作用下，算法將很快集中搜索于螞蟻?zhàn)畛跎傻膸讞l路徑，導(dǎo)致搜索陷入較差的局部空間；反之，算法則需要較多次的初期迭代才能有效反映出不同節(jié)點(diǎn)的優(yōu)劣性，從而正確指導(dǎo)螞蟻開始有偏向性地進(jìn)行搜索。因此，為使算法具有較好的搜索性能，信息素初始值應(yīng)略大于每次迭代中螞蟻釋放的信息素期望值。

考慮到螞蟻的信息素釋放量多設(shè)定為1/Trnd(Trnd為螞蟻搜索到的任一調(diào)度序列的加權(quán)延遲目標(biāo)值)，算法在初始時(shí)，按τij(0)=n/TEDD分配節(jié)點(diǎn)(i,j)間的初始信息素，其中，TEDD為采用最早交貨時(shí)間序列規(guī)則生成的作業(yè)序列下系統(tǒng)的總加權(quán)延遲成本。

2.4 調(diào)度序列構(gòu)建

當(dāng)IACO算法用于求解SMTWTS問題時(shí)，每次迭代中，m只螞蟻獨(dú)立構(gòu)造一個(gè)可行調(diào)度方案。SMTWTS問題的一個(gè)可行解決方案為n個(gè)作業(yè)排列組成的處理序列。在可行調(diào)度方案的構(gòu)建過程中，每只螞蟻從一個(gè)空序列開始，通過選取規(guī)則逐步將一個(gè)未調(diào)度的作業(yè)j添加到已構(gòu)建的部分序列中，最終構(gòu)建出一個(gè)完整調(diào)度方案。將作業(yè)j添加到部分序列的決策是按照蟻群算法的狀態(tài)轉(zhuǎn)移規(guī)則進(jìn)行的，這個(gè)過程受節(jié)點(diǎn)間信息素τij及任意時(shí)刻節(jié)點(diǎn)(i,j)間的啟發(fā)信息值ηij的共同影響。

狀態(tài)轉(zhuǎn)移規(guī)則的設(shè)定對蟻群算法的優(yōu)化性能具有重要影響：若不同作業(yè)間的狀態(tài)選取概率差異過大，則易使算法過早陷入局部最優(yōu)狀態(tài)；反之，則導(dǎo)致算法難以有效利用迭代過程積累的搜索經(jīng)驗(yàn)，收斂性能較差。

(2)

計(jì)算各可選作業(yè)在該位置處的加工概率，然后結(jié)合輪盤賭規(guī)則選出待加工作業(yè)。

采用確定性選擇與隨機(jī)性選擇相結(jié)合的選擇策略。通過對q0的調(diào)整，可以調(diào)節(jié)算法對當(dāng)前較優(yōu)解區(qū)域及其他未知解空間的探索度，有利于提高解空間的多樣性，避免算法過早陷入局部最優(yōu)。

2.5 啟發(fā)式信息的設(shè)定

啟發(fā)式信息的設(shè)定反映了優(yōu)化問題的成本代價(jià)或成本代價(jià)的估計(jì)值。對ηij的有效設(shè)定直接影響到算法的求解效率及全局收斂性。在本文所述SMTWTS問題中，啟發(fā)式信息ηij表征作業(yè)j安排在位置(作業(yè)處理序號(hào))i(i=1,2,…,n])進(jìn)行加工的期望程度。針對該問題，文獻(xiàn)[10]采用基于MDD的優(yōu)先規(guī)則定義ηij：

(3)

式中，Cj-1為已安排作業(yè)的總加工時(shí)間。

若待選作業(yè)j在加工位置i能早于其交貨期dj完成加工，則具有較早交貨期的作業(yè)被選擇在位置i加工的概率就大。此外，對于遲于交貨期完成的候選作業(yè)，處理時(shí)間較短的作業(yè)擁有更高的加工優(yōu)先級。

式(4)對于啟發(fā)式信息的定義仍存在部分不足：由于大部分基準(zhǔn)實(shí)例問題的交貨期dj通常較大，尤其在求解大規(guī)模實(shí)例問題的調(diào)度決策后期，加工時(shí)間的累積將使max(Cj-1+pj,dj)的取值變得很大，因此，這些作業(yè)間的啟發(fā)式信息差異通常較小。這意味著啟發(fā)式信息可能無法完全正確反映出其對螞蟻決策的相對影響。

為了減弱上述影響，提出采用由下式定義的啟發(fā)式信息：

(4)

式中，wj為待選作業(yè)j的權(quán)重。

若Cj-1+pj≥dj，則具有較小加權(quán)處理時(shí)間pj/wj的作業(yè)具有較大的啟發(fā)式信息值。

2.6 信息素更新

在所有螞蟻完成一次完整遍歷后，對構(gòu)成該可行解的各節(jié)點(diǎn)間的殘留信息做更新處理。為使算法在對較優(yōu)節(jié)點(diǎn)信息充分利用的同時(shí)，也保持較好的全局搜索能力，避免過早陷入局部最優(yōu)，提出一種改進(jìn)的差異化信息素更新策略，對各節(jié)點(diǎn)間信息素進(jìn)行全局更新處理。

在所述差異化信息素更新規(guī)則中，根據(jù)螞蟻構(gòu)建的方案質(zhì)量，引入正負(fù)反饋機(jī)制對各節(jié)點(diǎn)間信息素進(jìn)行自適應(yīng)差異化更新，使當(dāng)前最優(yōu)節(jié)點(diǎn)的變化能迅速表現(xiàn)在節(jié)點(diǎn)間的信息素分布上。該過程受迭代最優(yōu)調(diào)度方案的總加權(quán)延遲成本Tib、迭代最差調(diào)度方案的總加權(quán)延遲成本Tworst及所有調(diào)度排序方案的平均延遲成本Tave的影響。改進(jìn)的信息素更新策略描述如下：

(5)

式中，ρ為信息素?fù)]發(fā)系數(shù)；Tk為本次迭代中螞蟻k搜索到的排序方案下的總加權(quán)延遲成本；Δτijk為螞蟻k在本次循環(huán)中留在節(jié)點(diǎn)(i,j)間的信息素量；Δτij為本次循環(huán)中節(jié)點(diǎn)(i,j)間的信息素增量和。

(6)

式中，Q為預(yù)先設(shè)定的總信息量。

式(5)、式(6)根據(jù)螞蟻構(gòu)建的調(diào)度方案質(zhì)量動(dòng)態(tài)調(diào)整各節(jié)點(diǎn)間的信息素。對于目標(biāo)值小于迭代平均延遲成本的較優(yōu)調(diào)度排序方案，延遲成本越小，其所含節(jié)點(diǎn)間信息素增量越大，節(jié)點(diǎn)間就會(huì)獲得更多的信息素，在后續(xù)迭代中就可能會(huì)被更多的螞蟻所選擇；對于目標(biāo)值大于迭代平均延遲成本的較差調(diào)度排序方案，延遲成本越大，該方案所含節(jié)點(diǎn)間信息素減少的越多。相較于基本蟻群算法，該改進(jìn)通過對不同質(zhì)量調(diào)度排序方案進(jìn)行信息素差異化更新，增大較優(yōu)節(jié)點(diǎn)對螞蟻的吸引力，降低較差節(jié)點(diǎn)對螞蟻選擇的干擾，使得算法快速向全局最優(yōu)調(diào)度序列的方向搜索。

2.7 局部搜索策略的應(yīng)用

為進(jìn)一步改善調(diào)度方案質(zhì)量，對所有螞蟻每次迭代搜索后產(chǎn)生的迭代最優(yōu)方案引入局部搜索策略。局部搜索策略基于對候選解π的鄰域進(jìn)行迭代探測，通過局部調(diào)整當(dāng)前解決方案中的部分作業(yè)序列來提高調(diào)度方案質(zhì)量。在本文中，采用成對交換策略以進(jìn)一步實(shí)現(xiàn)解序列的優(yōu)化改進(jìn)。

成對交換策略中，候選解π的交換鄰域是在滿足i2-i1≤r(i2>i1；r為可調(diào)參數(shù)，r=1,2,…，n-1)的條件下，通過交換π中i1和i2位置的作業(yè)而得到的所有候選解π*的集合。成對交換是梯度下降的，它只接受可降低系統(tǒng)總加權(quán)延遲成本的可行調(diào)度方案。若在當(dāng)前候選解的鄰域內(nèi)找到更好的調(diào)度序列π*的加權(quán)延遲目標(biāo)值滿足Tπ*

考慮到有著臨近交貨期的作業(yè)必定在相近時(shí)刻先后安排加工才能保證整體最優(yōu)，因此，通過調(diào)整具有相近交貨期的部分作業(yè)序列可進(jìn)一步改善方案質(zhì)量。以r=4為例(任一作業(yè)與其緊鄰的4個(gè)作業(yè)依次交換)的成對交換策略執(zhí)行偽代碼可描述如下：

Procedure成對交換

對于任一迭代最優(yōu)作業(yè)序列π

Forr=1 to 4

Fori1=1 ton-r

Fori2=i1+r

Exchange [i1][i2]位置上的作業(yè)生成新的作業(yè)序列π*；

Ifπ*優(yōu)于當(dāng)前最優(yōu)解決方案πthen

π←π*，Tπ=Tπ*

更新解決方案π相關(guān)節(jié)點(diǎn)間信息素；

End if

End for

End for

End for

End Procedure

按照上述交換步驟，以表1為起始解決方案的一個(gè)成對交換局部優(yōu)化示例如圖1所示。

圖1 局部優(yōu)化示例Fig.1 Local optimization example

通過對迭代最優(yōu)方案引入局部優(yōu)化策略，將全局搜索與局部搜索有機(jī)結(jié)合，以較小的運(yùn)算代價(jià)有效改善了調(diào)度方案質(zhì)量，提高算法優(yōu)化性能。且上述交換策略只考慮了有限數(shù)量的交換鄰域，相比于文獻(xiàn)[14]的全局迭代交換，該方法更加簡單有效。

3 實(shí)驗(yàn)分析

為驗(yàn)證IACO算法對SMTWTS問題的求解性能，實(shí)驗(yàn)選用OR-Library[15]中問題規(guī)模n分別為40、50、100的各10個(gè)基準(zhǔn)問題進(jìn)行測試，并與蟻群算法及遺傳算法(GA)進(jìn)行求解比較。為使所選實(shí)例問題更具有一般性，30個(gè)實(shí)例問題均來自不同規(guī)模基準(zhǔn)問題集的前10項(xiàng)。

3種算法均采用Java語言編程，并在內(nèi)存為8 G，Intel Core i7-3770 CPU的PC上進(jìn)行測試。分別對每個(gè)實(shí)例問題進(jìn)行20次獨(dú)立實(shí)驗(yàn)，每次進(jìn)行2 000次迭代，ACO算法和GA算法的其他參數(shù)分別設(shè)置為文獻(xiàn)[16-17]中給出的建議值，IACO算法參數(shù)結(jié)合實(shí)驗(yàn)測試并設(shè)置如表2所示。

表2 IACO算法參數(shù)設(shè)置

表3統(tǒng)計(jì)了3種算法對不同基準(zhǔn)問題的實(shí)驗(yàn)結(jié)果。表3中，Tknow為已知最佳解決方案的總加權(quán)延遲目標(biāo)值，Tbest為算法搜索到的最佳結(jié)果，Tmean為算法20次求解的平均值，Hr為20次實(shí)驗(yàn)中搜索到已知最佳解決方案的命中率，偏差dev為算法搜索到的最優(yōu)解Tbest與已知最優(yōu)解Tknow的偏離程度：

(7)

表3 不同實(shí)例問題的求解結(jié)果

(續(xù)表)

基準(zhǔn)算例基本蟻群算法ACO遺傳算法GA改進(jìn)蟻群算法IACOn編號(hào)TknowTbestTmeanHr(%)dev(%)TbestTmeanHr(%)dev(%)TbestTmeanHr(%)dev(%)10015 9886 0406 24300.875 9886 286.5505 9886 054.440026 1706 2466 47201.236 2006 408.100.496 1706 288.530034 2674 3074 476.800.944 2804 482.800.304 2674 312.6510045 0115 0555 252.500.885 0115 235.5505 0115 151.5515055 2835 2885 515.800.095 2835 523.3505 2835 402.95550658 25861 54965 458.805.6559 13660 696.301.5158 30359 542.400.08750 97252 79955 207.803.5851 94353 263.201.9051 02055 152.900.09859 43460 99163 677.602.6260 58461 840.101.9359 55960 968.800.21940 97842 75144 437.604.3342 25343 23703.1141 04242 993.300.161053 20854 82156 833.803.0354 82155 890.803.0353 34254 842.300.25

表4給出了表3中部分實(shí)例問題求得的最優(yōu)解所對應(yīng)的具體加工序列。

表4 部分實(shí)例問題最優(yōu)解對應(yīng)的加工序列

由表3可知，對于SMTWT問題規(guī)模為n=40，50的多個(gè)基準(zhǔn)算例，IACO算法和GA均能在實(shí)驗(yàn)設(shè)定條件下獲得問題的最優(yōu)目標(biāo)值，ACO算法的求解結(jié)果稍差于IACO算法和GA，僅取得了少數(shù)最優(yōu)值。從其他統(tǒng)計(jì)參數(shù)來看，IACO算法的搜索成功率和平均求解結(jié)果等指標(biāo)多優(yōu)于GA且均明顯好于ACO算法，對每個(gè)基準(zhǔn)問題的平均求解結(jié)果與最優(yōu)解也極為接近，表明改進(jìn)算法對該類規(guī)模SMTWTS問題具有較好的求解性能及求解穩(wěn)定性。

對于表3中n=100規(guī)模的后4個(gè)基準(zhǔn)問題，3種算法均未能在算法停止時(shí)搜索到最優(yōu)解。由實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果可知，IACO算法的誤差率均在0.3%內(nèi)，明顯優(yōu)于其他2種算法，表明IACO算法在相同的迭代停止條件下具有更好的全局收斂性。

實(shí)驗(yàn)同時(shí)給出針對n=40，50，100三種不同規(guī)?；鶞?zhǔn)實(shí)例問題中編號(hào)為5的算法收斂曲線，如圖2所示。

圖2 實(shí)例問題5的算法收斂曲線圖Fig.2 Algorithm convergence curve for instance cases 5

圖2中，3種算法均以1000次迭代為停止條件。由圖2可知，GA的收斂過程“階段性”特征較為明顯，收斂較慢；ACO算法能快速收斂，但兩種算法對n=50，100規(guī)模的兩個(gè)實(shí)例問題均未能在指定停止條件下得到問題的最優(yōu)解。IACO算法能在更少迭代次數(shù)內(nèi)快速收斂到最優(yōu)解附近并趨于穩(wěn)定，圖2所示的3個(gè)實(shí)例均能在300次迭代內(nèi)獲得問題的最優(yōu)解，表明改進(jìn)算法具有較強(qiáng)的搜索能力。

綜合上述實(shí)驗(yàn)分析可知，對于多數(shù)基準(zhǔn)算例，IACO算法在求解質(zhì)量、收斂穩(wěn)定性等方面均顯著優(yōu)于GA及ACO算法，其原因如下：①多樣性節(jié)點(diǎn)選取規(guī)則和差異化信息素更新策略的應(yīng)用，使得算法在對較優(yōu)節(jié)點(diǎn)搜索經(jīng)驗(yàn)更好利用的同時(shí)，提高了解空間的多樣性和算法的搜索能力。②改進(jìn)的啟發(fā)式信息簡潔，準(zhǔn)確描述了作業(yè)在加工序列中不同位置的加工關(guān)系，信息素的正反饋更新機(jī)制強(qiáng)化了較優(yōu)調(diào)度節(jié)點(diǎn)被選取的概率，保證了算法快速向最優(yōu)調(diào)度序列的方向搜索。③局部搜索策略的引入，彌補(bǔ)了ACO算法局部搜索能力差的不足，在一定程度上降低了算法過早陷入局部最優(yōu)的概率。

4 結(jié)語

本文針對單機(jī)總加權(quán)延遲調(diào)度問題，提出一種基于信息素差異化更新的改進(jìn)蟻群調(diào)度算法。該算法采用確定性選擇與隨機(jī)性選擇相結(jié)合的選取規(guī)則，結(jié)合MDD調(diào)度規(guī)則改進(jìn)了啟發(fā)式信息函數(shù)，實(shí)現(xiàn)了SMTWTS問題的調(diào)度序列構(gòu)建；引入正負(fù)反饋機(jī)制對各節(jié)點(diǎn)間信息素進(jìn)行自適應(yīng)差異化更新，提高了解空間的多樣性，避免了算法的過早停滯。同時(shí)結(jié)合局部優(yōu)化策略實(shí)現(xiàn)了對可行調(diào)度方案的進(jìn)一步優(yōu)化。OR-Library中多個(gè)基準(zhǔn)實(shí)例的仿真實(shí)驗(yàn)表明，該改進(jìn)算法對SMTWTS問題具有良好的優(yōu)化性能。