啟發(fā)式狼群算法求解不相關(guān)并行機(jī)調(diào)度問題

荀洪凱，陶翼飛，羅俊斌，何 李

（1.昆明理工大學(xué)機(jī)電工程學(xué)院，云南昆明 650504；2.昆明昆船邏根機(jī)場物流系統(tǒng)有限公司，云南昆明 650236）

0 引言

并行機(jī)調(diào)度［1］（Parallel Machine Scheduling，PMS）在生產(chǎn)制造領(lǐng)域應(yīng)用廣泛，如半導(dǎo)體加工、注塑成型加工、紡織加工、光刻加工、卷煙加工等，并行機(jī)調(diào)度問題也已經(jīng)被證明為一類經(jīng)典的NP-hard 問題。而在實(shí)際生產(chǎn)加工過程中，由于并行機(jī)加工能力不同，需要考慮工件加工分配問題，導(dǎo)致其復(fù)雜程度更高，求解難度更大，從而對不相關(guān)并行機(jī)調(diào)度（Unrelated Parallel Machine Scheduling，UPMS）問題的研究具有更重要的理論意義和應(yīng)用價(jià)值。

近年來，不相關(guān)并行機(jī)調(diào)度問題被廣泛研究，目前并行機(jī)調(diào)度問題大多采用啟發(fā)式算法或其它智能優(yōu)化算法進(jìn)行求解。通過改進(jìn)傳統(tǒng)智能優(yōu)化算法進(jìn)行求解仍然是重要的研究方向，例如對遺傳算法的改進(jìn)方面，Abreu 等［2］提出一種混合遺傳算法用于解決具有序列相關(guān)設(shè)置時(shí)間的不相關(guān)并行機(jī)調(diào)度問題；Xuan 等［3］將遺傳算法和模擬退火算法結(jié)合，開發(fā)了一種新的遺傳模擬退火算法，以解決具有不相關(guān)并行機(jī)的混合流水車間調(diào)度問題。近年來，不少新算法相繼被提出，蟻獅優(yōu)化算法［4］、混合差分進(jìn)化算法［5］、混合多目標(biāo)教—學(xué)優(yōu)化算法［6］、混合啟發(fā)式算法［7］等，都被應(yīng)用到求解并行機(jī)調(diào)度問題。同時(shí)，很多組合優(yōu)化算法也被提出，Zhang 等［8］提出一種結(jié)合列表調(diào)度、啟發(fā)式最短設(shè)置時(shí)間優(yōu)先規(guī)則和最早完成時(shí)間優(yōu)先規(guī)則的組合進(jìn)化算法以解決具有有限工人資源和學(xué)習(xí)效應(yīng)的不相關(guān)并行機(jī)調(diào)度問題。從當(dāng)前研究可以看出，通過算法融合，以及有針對性地提出一些新算法，可以有效彌補(bǔ)傳統(tǒng)算法所存在的不足，并且為求解不相關(guān)并行機(jī)調(diào)度問題擴(kuò)展了研究方向，本文提出一種算法融合的方式以優(yōu)化并行機(jī)調(diào)度問題。

目前，針對不相關(guān)并行機(jī)調(diào)度問題的研究已經(jīng)比較成熟，但在搜索效率方面并未得到實(shí)質(zhì)性提升，代招等［9］通過利用混沌映射和反向?qū)W習(xí)策略生成初始種群，改善初始種群的質(zhì)量，求解以最小化最大完工時(shí)間為目標(biāo)的柔性作業(yè)車間調(diào)度問題；顧文斌等［10］提出一種新的啟發(fā)式算法提升初始種群質(zhì)量，改善搜索效率。目前，不相關(guān)并行機(jī)調(diào)度問題中搜索效率提升方法相關(guān)研究較少。在算法選擇方面，吳虎勝等［11］提出一種狼群算法（Wolf Pack Algorithm，WPA），該算法利用不同的搜索機(jī)制對狼群進(jìn)行搜索，結(jié)構(gòu)簡單、尋優(yōu)效率高，主要應(yīng)用在多旅行商問題［12］、柔性作業(yè)車間調(diào)度問題［13］以及置換流水車間調(diào)度問題［14］中。目前，狼群算法已經(jīng)解決了多種調(diào)度問題，但在并行機(jī)調(diào)度問題中的研究并不完善。本文設(shè)計(jì)啟發(fā)式算法旨在提高其搜索效率，選用狼群算法目的是保留算法并行性等優(yōu)勢。

綜上所述，本文在求解不相關(guān)并行機(jī)調(diào)度問題時(shí)以最小化最大完工時(shí)間為優(yōu)化目標(biāo)，首先，為提高搜索效率，提出一種啟發(fā)式算法，選擇合適的工件分配原則，將啟發(fā)式算法得到的種群與隨機(jī)生成的初始種群共同進(jìn)行優(yōu)化；其次，結(jié)合狼群算法的顯著特點(diǎn)以及在求解調(diào)度問題方面的優(yōu)勢，對狼群算法智能行為機(jī)制中鄰域搜索方式進(jìn)行設(shè)計(jì)，局部鄰域搜索與全局鄰域搜索相結(jié)合，使搜索效率達(dá)到最大化，最終通過不同規(guī)模不相關(guān)并行機(jī)調(diào)度問題算例進(jìn)行仿真優(yōu)化實(shí)驗(yàn)，證明所提出的啟發(fā)式狼群算法（Heuristic Wolf Pack Algorithm，HWPA）求解不相關(guān)并行機(jī)調(diào)度問題切實(shí)有效，與其它優(yōu)化算法相比該算法擁有更高的求解效率和精度。

1 問題描述

本文研究不相關(guān)并行機(jī)調(diào)度問題，該問題可以描述為：設(shè)N為待加工工件集合，M為并行機(jī)機(jī)器集合，每個工件只需在一臺機(jī)器上加工，同一臺機(jī)器在同一時(shí)間只能加工一個工件，并且每個工件在每臺機(jī)器上加工時(shí)間不同，每個工件之間沒有先后順序約束，即所有工件具有相同的優(yōu)先加工級，每個工件被加工的概率相同。假設(shè)工件j在機(jī)器i上的加工時(shí)間為t(i，j)，定義工件j在機(jī)器i上的廣義加工時(shí)間為x(i，j)t(i，j)，其中x(i，j)=1 時(shí)表示工件j在機(jī)器i上加工，否者x(i，j)=0。定義工件j在機(jī)器i上的加工初始時(shí)間為T(i，j)，工件j+1 在機(jī)器i上的加工初始時(shí)間為T(i，j+1)。總完工時(shí)間用C表示，最終求解目標(biāo)為最小化最大完工時(shí)間，即minCmax。并行機(jī)調(diào)度示意圖見圖1。

Fig.1 Parallel machine scheduling schematic圖1 并行機(jī)調(diào)度示意圖

目標(biāo)函數(shù)為：

約束條件為：

式（1）為模型中最小化最大完工時(shí)間，即目標(biāo)函數(shù)；式（2）確保每個工件只能由一臺并行機(jī)完成加工；式（3）定義了變量的取值范圍，式（4）規(guī)定工件在機(jī)器上加工未完成時(shí)不能更換工件；式（5）保證每臺機(jī)器上的工件按照一定的順序進(jìn)行加工。

2 啟發(fā)式狼群算法

為有效求解不相關(guān)并行機(jī)調(diào)度問題，本文提出一種啟發(fā)式狼群算法。該算法主要由兩部分組成：①針對不相關(guān)并行機(jī)調(diào)度的特點(diǎn)，對算法初始種群通過啟發(fā)式算法進(jìn)行調(diào)整；②在迭代過程中，不同類型的狼群設(shè)置不同的鄰域搜索方式。算法流程如圖2所示。

具體步驟如下：①設(shè)定啟發(fā)式算法中每代個體數(shù)i、規(guī)模數(shù)及迭代次數(shù)i；②初始化種群，將隨機(jī)初始化的種群與啟發(fā)式算法尋優(yōu)得到的種群共同組成初始種群；③狼群分類，對初始化種群中的所有個體進(jìn)行譯碼、仿真并計(jì)算其適應(yīng)度值，按照計(jì)算出的適應(yīng)度值以及選定的規(guī)模數(shù)進(jìn)行相應(yīng)分類；④探狼游走，分類后的個體中探狼個體根據(jù)下文游走機(jī)制進(jìn)行相應(yīng)的鄰域搜索，并計(jì)算其適應(yīng)度，觀察最優(yōu)解是否得到更新；⑤頭狼召喚，分類后的猛狼個體根據(jù)召喚機(jī)制進(jìn)行相應(yīng)的鄰域搜索，計(jì)算搜索后的個體適應(yīng)度，判斷最優(yōu)解是否需要更新；⑥狼群圍攻，將最優(yōu)個體以外所有個體根據(jù)圍攻機(jī)制進(jìn)行全局鄰域搜索，計(jì)算出本次迭代中所有個體適應(yīng)度值并找到最優(yōu)解；⑦判斷最大迭代次數(shù)是否完成，若是，則算法結(jié)束，輸出最優(yōu)個體編碼即為最優(yōu)解，若否，則執(zhí)行步驟③。

Fig.2 Flow of HWPA圖2 啟發(fā)式狼群算法流程

2.1 初始種群生成

在狼群優(yōu)化算法中，如果僅用隨機(jī)方式生成初始種群，將增加種群迭代次數(shù)，因此本文在初始化種群時(shí)提出新的啟發(fā)式算法，流程如圖3所示。

Fig.3 Flow of heuristic algorithm圖3 啟發(fā)式算法流程

mint(i，j)表示工件i在機(jī)器j上的最短加工時(shí)間，用jmin表示加工時(shí)間最短的機(jī)器，用jmax表示加工時(shí)間最長的機(jī)器，Nj表示機(jī)器j上加工工件集合，Njmax表示加工時(shí)間最長的機(jī)器上所加工工件集合。tj表示工件i在兩臺機(jī)器上加工時(shí)間差值。

式（6）表示機(jī)器j的總加工時(shí)間，式（7）表示加工時(shí)間最長機(jī)器的加工時(shí)間，式（8）表示工件i在總加工時(shí)間最長的機(jī)器和總加工時(shí)間最短的機(jī)器上加工時(shí)間差值最小，其中i∈Njmax。

啟發(fā)式算法流程如圖3 所示，具體步驟如下：①分別選出加工工件時(shí)間最短的機(jī)器；②確定jmin和jmax，計(jì)算出t(jmax)即是此時(shí)總完工時(shí)間；③根據(jù)式（6）和式（7）找到Njmax，并根據(jù)式（8）找到可以替換加工機(jī)器的工件i并進(jìn)行替換；④重新計(jì)算總完工時(shí)間，判斷總完工時(shí)間是否減少，若總完工時(shí)間減少則進(jìn)行工件替換，并重復(fù)步驟②至④，若總完工時(shí)間增加則停止運(yùn)行算法。

給出一個示例進(jìn)行說明，先為每個工件選擇加工時(shí)間最短的機(jī)器，此時(shí)甘特圖如圖4所示。

Fig.4 10×4 Gantt chart before adjustment圖4 10×4調(diào)整前甘特圖

根據(jù)仿真后的結(jié)果，找到最早和最晚完工機(jī)器，考慮將M4 上的工件轉(zhuǎn)移到M2 機(jī)器上進(jìn)行加工，此時(shí)可以選擇的工件有J3、J7、J10。如圖5 所示，根據(jù)這3 個工件在M2和M4 上加工所用的時(shí)間差決定將增量最小的工件J3 分配到M2上加工。

Fig.5 Time increment before and after adjustment圖5 調(diào)整前后時(shí)間增量

最終調(diào)整后得到如圖6 所示甘特圖，此時(shí)總的完工時(shí)間減少，可以繼續(xù)進(jìn)行調(diào)整，直到總的完工時(shí)間不再減少為止。

Fig.6 10×4 adjusted Gantt chart圖6 10×4調(diào)整后甘特圖

2.2 編碼及譯碼

本文采用單鏈編碼方式，首先用工件編號給出工件的加工順序，其次用大于工件編號的數(shù)字將排好的加工順序進(jìn)行分隔，進(jìn)而確定工件的加工機(jī)器。這種編碼方式能夠使編碼更簡潔，減少計(jì)算次數(shù)。

根據(jù)編碼方式，譯碼步驟為：①將分隔數(shù)字找出；②確定工件加工順序，同時(shí)將工件分配到相應(yīng)待加工機(jī)器。

例如：在7 個工件，3 臺并行機(jī)的加工過程中，編碼［5 7 3 8 4 2 9 6 1］中數(shù)字8 與數(shù)字9 代表分隔數(shù)字，工件加工順序?yàn)榫幋a先后順序。并行機(jī)1 加工工件5、7、3，并行機(jī)2加工工件4、2，并行機(jī)3加工工件6、1。

2.3 種群適應(yīng)度

本文研究的是以最小化最大完工時(shí)間為目標(biāo)的不相關(guān)并行機(jī)調(diào)度問題，用時(shí)越少，適應(yīng)度越高，因此種群的適應(yīng)度f用所有工件加工完成時(shí)間的倒數(shù)擴(kuò)大100 倍代替，即：

2.4 智能行為設(shè)置

根據(jù)狼群算法以及不相關(guān)并行機(jī)調(diào)度的特點(diǎn)，設(shè)計(jì)新的智能行為機(jī)制。

（1）選擇機(jī)制。在迭代過程中，迭代后的最優(yōu)個體優(yōu)于迭代前最優(yōu)個體，則進(jìn)行更新。

（2）游走機(jī)制。針對種群中部分次優(yōu)個體種群進(jìn)行鄰域搜索。將種群中除最優(yōu)個體以外的其他個體進(jìn)行適應(yīng)度排序，將部分適應(yīng)度較好的個體看作探狼，并在其鄰域內(nèi)進(jìn)行隨機(jī)搜索。為了提高種群多樣性，防止種群陷入局部最優(yōu)解，本文對次優(yōu)種群的步長沒有作具體規(guī)定，每段編碼中隨機(jī)找一段編碼，將這段編碼位置進(jìn)行隨機(jī)調(diào)換。如圖7 所示，位置編碼為［5 7 3 8 4 2 9 6 1］，執(zhí)行游走行為時(shí)，隨機(jī)選擇的片段為［7 3 8 4 2］，隨機(jī)排序后的片段為［2 8 3 4 7］，則隨機(jī)游走后的位置編碼為［5 2 8 3 4 7 9 6 1］，利用隨機(jī)游走方式增加了種群多樣性。

（3）召喚機(jī)制。首先，隨機(jī)選擇某一機(jī)器上所有工件并找出這段編碼，如圖8 所示，頭狼個體編碼為［5 7 3 8 4 2 9 6 1］，猛狼個體編碼為［4 1 3 8 6 7 5 9 2］，隨機(jī)選擇的并行機(jī)為2；其次，選擇剩余個體與最優(yōu)個體的編碼片段對應(yīng)位置進(jìn)行交叉，并且剩余位置編碼用部分映射交叉，對應(yīng)編碼位置在第4 位，將這段編碼與猛狼個體編碼相應(yīng)位置進(jìn)行部分映射交叉，交叉調(diào)整后的猛狼個體編碼為［5 1 3 8 4 2 9 6 7］，將新的編碼進(jìn)行譯碼計(jì)算出適應(yīng)度，若調(diào)整后的適應(yīng)度優(yōu)于原編碼適應(yīng)度，則將原編碼進(jìn)行替換。這種交叉方式能夠保留在某一臺并行機(jī)所選擇的加工工件，從而保留了較優(yōu)的排序片段。

Fig.7 Wandering schematic圖7 游走示意圖

Fig.8 Calling schematic圖8 召喚示意圖

（4）圍攻機(jī)制。將最優(yōu)個體編碼與次優(yōu)個體編碼進(jìn)行比較，相同位置的編碼將保留，如圖9 所示，最優(yōu)個體編碼為［5 7 3 8 4 2 9 6 1］，其他個體的編碼為［6 7 3 4 8 2 9 5 1］，比較后發(fā)現(xiàn)編碼7、3、2、9、1 是相同位置相同編碼，這些編碼不發(fā)生變化，其他位置編碼采用隨機(jī)方式重新進(jìn)行編碼。圍攻時(shí)的位置已經(jīng)接近本次迭代最優(yōu)位置，采用隨機(jī)方式進(jìn)行鄰域搜索，增加解的多樣性，有利于跳出局部最優(yōu)解。

Fig.9 Besieging schematic圖9 圍攻示意圖

3 實(shí)驗(yàn)設(shè)計(jì)仿真建模與分析

3.1 仿真建模

針對本文所提出算法，先用一個標(biāo)準(zhǔn)算例驗(yàn)證算法有效性，然后通過遺傳算法和混合果蠅算法對不同規(guī)模算例進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證其優(yōu)越性。利用Plant Simulation 軟件建模仿真分析、Simtalk2.0 語言進(jìn)行編程，建立優(yōu)化算法模型如圖10所示。

3.2 算法參數(shù)設(shè)置

Fig.10 Modeling of 5 parallel machine scheduling for 30 workpieces圖10 30工件5臺并行機(jī)建模

啟發(fā)式狼群算法主要參數(shù)有：工件數(shù)N，并行機(jī)機(jī)器數(shù)M，迭代次數(shù)D以及每迭代一次保留的個體數(shù)即種群規(guī)模G，各參數(shù)取值如表1 所示。根據(jù)算法主要參數(shù)找到L16（45）正交表設(shè)計(jì)正交實(shí)驗(yàn)如表2所示。

Table 1 HWPA parameters and values of each level表1 HWPA參數(shù)及各水平取值

Table 2 Orthogonal table and fitness value of HWAP parameters表2 HWPA參數(shù)正交表及適應(yīng)度值

通過正交實(shí)驗(yàn)結(jié)果如表3 所示，繪制相應(yīng)參數(shù)對算法影響水平趨勢圖，如圖11所示。

比較各參數(shù)對所求結(jié)果適應(yīng)度的影響。通過圖11 可以看出，工件數(shù)目越少，適應(yīng)度越好，并行機(jī)數(shù)目越多，適應(yīng)度越好，算法迭代次數(shù)在150 時(shí)最好，狼群規(guī)模在30 左右能達(dá)到最優(yōu)。根據(jù)正交實(shí)驗(yàn)結(jié)論設(shè)計(jì)實(shí)驗(yàn)參數(shù)D=150，G=30。

Table 3 Average fitness values of HWPA parameters表3 HWPA各參數(shù)平均適應(yīng)度值

Fig.11 Trend of influence level of each factor on algorithm圖11 各因素對算法影響水平趨勢

3.3 有效性驗(yàn)證

本文用一個已知實(shí)例［15］驗(yàn)證啟發(fā)式狼群算法有效性，仿真中的初始化參數(shù)為：D=150，G=30，探狼規(guī)模為種群規(guī)模的50%。利用軟件仿真建模，編寫算法程序，進(jìn)行50 次仿真，求取仿真平均值，得到最優(yōu)結(jié)果甘特圖如圖12所示。

仿真實(shí)驗(yàn)得出的最小化最大加工時(shí)間為7，與文獻(xiàn)中結(jié)果相同，證明本文提出的啟發(fā)式狼群算法有效。

Fig.12 Gantt chart of optimal solution of 8×4-problem圖12 8×4問題最優(yōu)解甘特圖

3.4 不同規(guī)模實(shí)驗(yàn)比較

為了多方位驗(yàn)證算法有效性，設(shè)計(jì)不同規(guī)模的實(shí)驗(yàn)與遺傳算法和混合果蠅優(yōu)化算法進(jìn)行比較。實(shí)驗(yàn)數(shù)據(jù)來自文獻(xiàn)［16］。通過查閱文獻(xiàn)［17-20］設(shè)置參數(shù)如下：N=｛30，50，80，100，120｝，M=｛5，10｝，每組規(guī)模進(jìn)行20 次實(shí)驗(yàn)，每個實(shí)例迭代次數(shù)150 次，每一代的種群規(guī)模數(shù)為30，遺傳算法交叉概率0.9，變異概率0.1，混合果蠅算法的種群規(guī)模和最大迭代次數(shù)與其他算法一致，果蠅搜索半徑為［-5，5］隨機(jī)數(shù)，啟發(fā)式狼群算法探狼數(shù)量為種群數(shù)量的50%。每組規(guī)模的實(shí)驗(yàn)結(jié)果如表4所示。

表4 中，IR1 表示目標(biāo)函數(shù)值較GA 改進(jìn)百分比，IR2 表示目標(biāo)函數(shù)值較FOA 改進(jìn)百分比。不同規(guī)模問題每一次迭代后的最小化最大完工時(shí)間點(diǎn)線圖如圖13所示。

Table 4 Test results of different scale problems表4 不同規(guī)模問題測試結(jié)果

3.5 實(shí)驗(yàn)結(jié)果分析

通過實(shí)驗(yàn)比較可以看出，啟發(fā)式狼群算法相比其他兩種算法能得到較優(yōu)結(jié)果，由于對初始種群進(jìn)行了改進(jìn)，啟發(fā)式算法為每個工件選擇了加工時(shí)間最短的機(jī)器，并通過改變最大完工時(shí)間機(jī)器上的工件分配，從而使該HWPA 在迭代初期就能表現(xiàn)出其優(yōu)勢。在GA 與FOA 搜索過程中，若增加迭代次數(shù)最終也能搜索到與HWPA 接近的結(jié)果，但搜索效率會降低。在150 次迭代搜索范圍內(nèi)，不同規(guī)模算例實(shí)驗(yàn)結(jié)果顯示，HWPA 的目標(biāo)值較GA 平均改進(jìn)了107.35%，較FOA 平均改進(jìn)了113.62%，精度提升較高，即使問題規(guī)模改變，啟發(fā)式狼群算法也能夠使計(jì)算結(jié)果達(dá)到相對最優(yōu)值，具有較好的魯棒性。通過對智能行為機(jī)制的改進(jìn)，使得每一次迭代后的最優(yōu)解中保留了較優(yōu)的工件分配片段。同時(shí)，采用隨機(jī)分配方式進(jìn)行調(diào)整，增加了跳出局部最優(yōu)解的可能，進(jìn)一步使最終尋優(yōu)結(jié)果達(dá)到較為滿意的程度。

從點(diǎn)線圖中可以看出，小規(guī)模不相關(guān)并行機(jī)調(diào)度中最小化最大完工時(shí)間相差不大，隨著工件數(shù)量與機(jī)器數(shù)目增多，3 種算法在150 次迭代后完工時(shí)間差值增大，在并行機(jī)數(shù)目保持不變的情況下，工件數(shù)目越多，啟發(fā)式狼群算法的優(yōu)勢也越明顯，說明啟發(fā)式狼群算法對解決以最小化最大完工時(shí)間為目標(biāo)的大規(guī)模不相關(guān)并行機(jī)調(diào)度有其優(yōu)勢。

4 結(jié)語

本文針對不相關(guān)并行機(jī)調(diào)度問題，提出一種啟發(fā)式狼群算法，通過啟發(fā)式算法改變部分初始種群的選擇方式，同時(shí)根據(jù)該問題特點(diǎn)，對狼群算法智能行為機(jī)制重新進(jìn)行設(shè)計(jì)。通過仿真優(yōu)化實(shí)驗(yàn)證明該算法有效，同時(shí)設(shè)置不同規(guī)模算例實(shí)驗(yàn)，在一定迭代次數(shù)內(nèi)，本文所提算法能有效優(yōu)化最大完工時(shí)間，且求解問題規(guī)模越大優(yōu)化效果也越明顯，為不相關(guān)并行機(jī)調(diào)度問題研究提供了一定參考價(jià)值。未來將繼續(xù)研究該算法在多目標(biāo)并行機(jī)調(diào)度問題中的應(yīng)用。

Fig.13 Optimal solutions of different scales圖13 不同規(guī)模最優(yōu)解