混合流水車間調(diào)度問題的果蠅優(yōu)化算法求解

杜利珍 王 震 柯善富 熊子雪 李新宇

1.武漢紡織大學(xué)機(jī)械工程及自動化學(xué)院，武漢，430073 2.華中科技大學(xué)機(jī)械科學(xué)與工程學(xué)院，武漢，430074

0 引言

混合流水車間調(diào)度問題(hybrid flow-shop scheduling problem, HFSP)[1]具有現(xiàn)實(shí)的制造業(yè)背景，涉及多設(shè)備、多階段、多工件的加工，屬于NP-hard問題。傳統(tǒng)HFSP可以分為相同并行機(jī)[2]、均勻并行機(jī)、不相關(guān)并行機(jī)調(diào)度問題[3]。

求解HFSP常用遍歷式算法和啟發(fā)式算法。遍歷式算法能夠得到該類問題的精確解，但受限于計(jì)算速度，該算法只用于小規(guī)模問題的求解[4]，而不適用于復(fù)雜大系統(tǒng)問題。近年來，啟發(fā)式算法的研究不斷取得突破，遺傳算法[5]、蟻群算法[6]、模擬退火算法等相繼被提出并用于求解HFSP，但運(yùn)算速度還是差強(qiáng)人意，因此人工魚群算法[7]、蜂群算法[8]、二元分布估計(jì)算法[9]等一些搜索速度更快、迭代過程更簡單且有效的算法被提出。啟發(fā)式算法能夠在短時(shí)間內(nèi)給出大規(guī)模問題的解，但這個(gè)解在通常情況下是滿意解而非精確解。

編碼與解碼是將模型問題融入算法的一個(gè)關(guān)鍵過程，編碼決定著輸入，解碼決定著輸出。PAN等[10]提出基于自適應(yīng)搜索策略的離散人工蜂群算法；王凌等[11]提出基于排列的編碼和解碼的方法，用人工蜂群算法很好地實(shí)現(xiàn)了不相關(guān)并行機(jī)HFSP的求解。

相較于上述算法，果蠅優(yōu)化算法[12]擁有更好的自適應(yīng)和自組織能力，具有迭代過程簡單、全局收斂性強(qiáng)、算法執(zhí)行時(shí)間短的特點(diǎn)。筆者在果蠅優(yōu)化算法的更新規(guī)則上加入權(quán)重系數(shù)，對權(quán)重的編碼方式進(jìn)行改進(jìn)，使得算法的隨機(jī)搜索能力更強(qiáng)，編碼和種群迭代過程更加簡單。

1 不相關(guān)并行機(jī)混合流水車間調(diào)度

1.1 問題描述

不相關(guān)并行機(jī)HFSP的假設(shè)如下：①n個(gè)工件在流水線上進(jìn)行S個(gè)階段的加工；②每個(gè)階段至少有1臺機(jī)器；③至少有一個(gè)階段存在并行機(jī)；④任意一個(gè)階段上的設(shè)備都能完成工件的一個(gè)工序；⑤工件需要在每個(gè)階段完成一道工序；⑥各機(jī)器的加工時(shí)間不完全相同，已知n個(gè)工件各道工序在各設(shè)備上的加工時(shí)間，要求確定n個(gè)工件的加工順序以及每一階段上設(shè)備的分配情況，使得某一調(diào)度指標(biāo)最小?；旌狭魉囬g調(diào)度模型如圖1所示。

圖1 混合流水車間調(diào)度模型Fig.1 Model of hybrid flow-shop scheduling

1.2 數(shù)學(xué)模型

對于不相關(guān)并行機(jī)HFSP有：工件的編號為i(i=1，2，…，n)；n個(gè)工件需要在S個(gè)階段上加工；ti,j,k為工件i在第j(j=1，2，…，S)個(gè)階段的第k臺設(shè)備的加工時(shí)間；mj為第j個(gè)階段的設(shè)備數(shù)量；si,j,k為第個(gè)i工件在第j個(gè)階段的第k臺設(shè)備的開始加工時(shí)間；Pi,j,k為第i個(gè)工件在第j個(gè)階段第k臺設(shè)備上的加工完成時(shí)間；xi,α為0-1變量，工件i被排在第α個(gè)位置等待加工時(shí)，xi,α=1；Ci為工件Ji的加工完成時(shí)間，所有工件加工完成所需的最大完成時(shí)間為各工件加工完成時(shí)間的最大值，即最大完工時(shí)間Cmax=max{C1，C2，…，Cn}；L為足夠大的數(shù)[13],具體的數(shù)字模型如下：

minCmax

(1)

(2)

(3)

(4)

Pi,j,k=si,j,k+ti,j,k

(5)

j=1,2,…,s

Pi,β,k≤si,β+1,k2

(6)

k=1,2,…,mββ=1,2,…,S-1k2=1,2,…,mβ+1

(7)

γ=1,2,…,n-1K=1,2,…,m1

(8)

l1≤l2l1,l2=1,2,…,n

上述公式的含義如下：式(1)為目標(biāo)函數(shù)；式(2)、式(3)保證優(yōu)先級與工件對應(yīng)關(guān)系的唯一性；式(4)保證工件在任意階段只能在1臺機(jī)器上加工；式(5)表示同一階段上工件加工的開始時(shí)間和完成時(shí)間的關(guān)系；式(6)表示工件加工的先后關(guān)系；式(7)表示第一階段排序靠前的工件先被加工；式(8)表示如果工件被分配在同一階段的同一設(shè)備，排序靠前的工件先加工。不處于同一位置的工件在相同階段的相同設(shè)備上加工時(shí)，足夠大的數(shù)L保證式(8)恒成立。

2 果蠅優(yōu)化算法

果蠅優(yōu)化算法利用果蠅覓食的原理不斷進(jìn)行種群的迭代，最終找到所求問題的最優(yōu)解。如圖2所示，果蠅優(yōu)化算法基本步驟如下[14]：

(1)參數(shù)初始化。對中心果蠅位置、種群規(guī)模、算法迭代次數(shù)進(jìn)行初始化。

(2)嗅覺搜索。在中心果蠅個(gè)體的周圍產(chǎn)生其他果蠅個(gè)體，計(jì)算種群每個(gè)果蠅個(gè)體的適應(yīng)度，用于評價(jià)每個(gè)果蠅個(gè)體。

(3)視覺搜索。選擇適應(yīng)度最大的果蠅作為下一次迭代的種群中心，利用種群更新公式進(jìn)行新一代種群更新。

圖2 改進(jìn)果蠅優(yōu)化算法流程圖Fig.2 Framework of the improved FOA

(4)判斷是否滿足迭代終止條件。若滿足則結(jié)束迭代，輸出最優(yōu)結(jié)果；否則轉(zhuǎn)至步驟(2)。

3 果蠅優(yōu)化算法的求解

3.1 編碼

本文采用基于權(quán)重的編碼方式，將離散系統(tǒng)的求解轉(zhuǎn)化成連續(xù)系統(tǒng)的求解。工件的加工順序根據(jù)權(quán)重的大小依次排列，每種排列表示一個(gè)可行解，例如權(quán)重(0.20，0.18，0.36，0.25，0.64，0.57)對應(yīng)的工件排列順序?yàn)?5，6，3，4，1，2)，該排序表示工件5先加工，其次是工件6，最后是工件2。這種編碼方式能夠便于種群的更新操作。

3.2 解碼

解碼采用基于排列的方式[15]，主要分為工件的排序和設(shè)備的選擇。工件排序的規(guī)則：第一階段，按照初始的工件排序依次進(jìn)行加工，后面階段的工件按照前一階段加工完成時(shí)間先后順序進(jìn)行加工；多個(gè)工件的加工完成時(shí)間相同時(shí)，隨機(jī)選擇其中一個(gè)工件進(jìn)行加工。設(shè)備的選擇規(guī)則：根據(jù)工件i在階段j上的加工順序，判斷每個(gè)工件在第k臺設(shè)備上的最早允許加工時(shí)間，即設(shè)備k釋放時(shí)間Pk與工件i在上一階段的完成時(shí)間Ri,j-1的較大者max(Pk,Ri,j-1)；然后對工件i根據(jù)公式max(Pk,Ri,j-1)+ti，j，k選擇值小的機(jī)器k作為工件i的加工設(shè)備。重復(fù)以上步驟直到所有工件完成S個(gè)階段的加工。

3.3 種群初始化

初始化種群規(guī)模psize，采用產(chǎn)生隨機(jī)數(shù)的方式來產(chǎn)生初始解Qz，根據(jù)Qz對工件的加工進(jìn)行排序。矩陣Qz的元素是0～1之間的隨機(jī)數(shù)，可保證初始解的隨機(jī)性。

3.4 嗅覺操作

通過產(chǎn)生隨機(jī)數(shù)的方式產(chǎn)生與初始解相同維度的隨機(jī)數(shù)矩陣Ly，則果蠅種群X(i)=Qz+Ly，對種群中的每一個(gè)果蠅個(gè)體X(i)以最大完成時(shí)間最小作為評價(jià)指標(biāo)進(jìn)行計(jì)算。單目標(biāo)適應(yīng)度函數(shù)為

F(x)=minCmax

(9)

果蠅優(yōu)化算法種群初始化及嗅覺操作偽代碼如下。

輸入：工件在各機(jī)器上的加工時(shí)間表

輸出：最優(yōu)的排序

Gj=[1,2,3,4,5,6];

∥工件排序

Sizepop=5；

∥初始化種群個(gè)數(shù)

K=6；

∥種群個(gè)體維度

Qz=rand(1，k)；

∥隨機(jī)初始種群中心權(quán)重

FOR i=1：sizepop；

X(i)=B1Qz+B2normrnd；

∥種群權(quán)重

END FOR

FOR i=1：sizepop

a=[Gj’,X(i,:)]；

∥工件順序按照權(quán)重重排

F(i)=f(a);

∥計(jì)算種群個(gè)體適應(yīng)度

Besta=arg min(F(i));

∥選擇適應(yīng)值最小的排序

END FOR

3.5 視覺操作

選取嗅覺操作中的最優(yōu)果蠅個(gè)體作為下一個(gè)種群的中心果蠅，其他果蠅向該果蠅移動，從而產(chǎn)生新的種群。種群的更新方式與嗅覺操作方式相同，改進(jìn)果蠅優(yōu)化算法更新規(guī)則為

X(i)=B1Qbest+B2Nr

(10)

式中，B1表示果蠅中心對果蠅種群的影響程度；B2表示種群領(lǐng)域隨機(jī)搜索能力對種群的影響程度；X(i)(i=1，2，…，psize)為果蠅個(gè)體權(quán)重矩陣，幾何上表示果蠅個(gè)體位置，下同；Qbest為中心果蠅權(quán)重矩陣；Nr為隨機(jī)權(quán)重矩陣。

與原始算法更新公式X(i)=Qbest+Nr相比，改進(jìn)后的更新公式增加了變量B1、B2，提高了算法的隨機(jī)搜索能力。

4 仿真測試和比較

標(biāo)桿實(shí)例1[16]12個(gè)工件的加工工序?yàn)檐?、刨、磨，現(xiàn)有3臺車床、2臺刨床、4臺磨床，每臺機(jī)床的加工能力不同，工件在設(shè)備M1～M9上的加工時(shí)間如表1所示。

表1 實(shí)例1加工時(shí)間表

標(biāo)桿實(shí)例2[17]某工廠需要加工6個(gè)工件，每個(gè)工件都需要經(jīng)過銑、車、磨三道工序?，F(xiàn)有3臺銑床、2臺車床、3臺磨床，設(shè)備用M1～M8表示。工件的加工時(shí)間如表2所示。

標(biāo)桿實(shí)例3[18]某鋼鐵生產(chǎn)包含煉鋼、精煉、連鋼、軋制四個(gè)步驟，完成這些工序需要3臺煉鋼爐、3臺精煉爐、2臺鑄機(jī)、2臺軋機(jī)，用M1～M10表示。工件在設(shè)備上的加工時(shí)間如表3所示。

表2 實(shí)例2加工時(shí)間表

表3 實(shí)例3加工時(shí)間表

4.1 參數(shù)討論

對該果蠅優(yōu)化算法的種群規(guī)模psize、中心果蠅重要程度參數(shù)B1、隨機(jī)搜索能力參數(shù)B2進(jìn)行測試。將評價(jià)次數(shù)3 000作為每種參數(shù)組合運(yùn)行的終止條件，對每一種參數(shù)組合獨(dú)立運(yùn)行20次，程序使用MATLAB編程，在4G內(nèi)存、3.20 GHz CPU上運(yùn)行，得到最大完成時(shí)間的平均值和標(biāo)準(zhǔn)差，如表4所示。

表4 實(shí)例1參數(shù)組合

統(tǒng)計(jì)實(shí)例1在不同參數(shù)組合條件下運(yùn)行時(shí)的均值和極值，如圖3所示。以標(biāo)桿案例1為例，對算法參數(shù)進(jìn)行分析可知，B1

圖3 實(shí)驗(yàn)結(jié)果圖Fig.3 Experiment results chart

對實(shí)例2在2 000次評價(jià)，實(shí)例3在6 000次評價(jià)的條件下設(shè)計(jì)同樣的實(shí)驗(yàn)，得到3種規(guī)模的最優(yōu)參數(shù)組合，如表5所示。

表5 實(shí)例1參數(shù)組合

4.2 實(shí)驗(yàn)結(jié)果對比

為了進(jìn)一步說明果蠅優(yōu)化算法(fruit fly optimization algorithm，F(xiàn)OA)的優(yōu)越性，將該算法與遺傳算法(GA)[16]和差分進(jìn)化(differential evolution，DE)算法[18]進(jìn)行對比。將評價(jià)次數(shù)10 000作為算法運(yùn)行終止條件，得到的結(jié)果如表6所示。文獻(xiàn)[16]給出了一種改進(jìn)的編碼方式，這種編碼方式能夠保證個(gè)體編碼的合法性。文獻(xiàn)[18]通過特殊的編碼方案，結(jié)合基于DE算法的進(jìn)化搜索和局部搜索，增強(qiáng)探索和開發(fā)能力。

表6 實(shí)例1結(jié)果比較

由表6可以看出，GA不夠穩(wěn)定，未能找到最優(yōu)解24，DE算法能8次找到最優(yōu)解24，而FOA能夠100%找到最優(yōu)解24，因此在相同的評價(jià)次數(shù)中，F(xiàn)OA的穩(wěn)定性更好，其最優(yōu)解甘特圖為圖4，圖中方框內(nèi)的數(shù)據(jù)為工件序號，收斂曲線如圖5所示。

圖4 最優(yōu)調(diào)度的甘特圖Fig.4 Gantt chart of the optimal solution

圖5 收斂曲線圖Fig.5 Convergence curve chart

實(shí)例2的實(shí)驗(yàn)結(jié)果對比如表7所示，將FOA與PBIL[17](population-based incremental learning)、EDA[17](estimation of distribution algorithm)進(jìn)行對比。將評價(jià)次數(shù)3 000作為算法運(yùn)行終止條件。在相同評價(jià)次數(shù)中，F(xiàn)OA能100%找到最優(yōu)解13.5，其他2個(gè)算法沒能找到最優(yōu)解，從而驗(yàn)證了算法的有效性和魯棒性。實(shí)例3的實(shí)驗(yàn)結(jié)果對比如表8所示，將評價(jià)次數(shù)18 000作為算法運(yùn)行終止條件，10次獨(dú)立運(yùn)行中，F(xiàn)OA能6次找到最優(yōu)解297，且結(jié)果優(yōu)于DE算法的結(jié)果[19]，再一次證明了算法了有效性。

表7 實(shí)例2結(jié)果比較

表8 實(shí)例3結(jié)果比較

5 結(jié)論

在原始果蠅優(yōu)化算法的基礎(chǔ)上，增加了中心果蠅影響程度參數(shù)B1和領(lǐng)域搜索能力參數(shù)B2，通過實(shí)驗(yàn)考察了2個(gè)參數(shù)對算法的影響。在相同的實(shí)驗(yàn)條件下，改進(jìn)果蠅優(yōu)化算法更容易找到最優(yōu)解，且不容易陷入局部最優(yōu)。與GA、EDA、DE算法進(jìn)行對比，改進(jìn)果蠅優(yōu)化算法表現(xiàn)出了極好的隨機(jī)搜索能力和魯棒性。