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

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

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

相較于上述算法，果蠅優(yōu)化算法[12]擁有更好的自適應(yīng)和自組織能力，具有迭代過程簡單、全局收斂性強(qiáng)、算法執(zhí)行時間短的特點(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個工件在流水線上進(jìn)行S個階段的加工；②每個階段至少有1臺機(jī)器；③至少有一個階段存在并行機(jī)；④任意一個階段上的設(shè)備都能完成工件的一個工序；⑤工件需要在每個階段完成一道工序；⑥各機(jī)器的加工時間不完全相同，已知n個工件各道工序在各設(shè)備上的加工時間，要求確定n個工件的加工順序以及每一階段上設(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個工件需要在S個階段上加工；ti,j,k為工件i在第j(j=1，2，…，S)個階段的第k臺設(shè)備的加工時間；mj為第j個階段的設(shè)備數(shù)量；si,j,k為第個i工件在第j個階段的第k臺設(shè)備的開始加工時間；Pi,j,k為第i個工件在第j個階段第k臺設(shè)備上的加工完成時間；xi,α為0-1變量，工件i被排在第α個位置等待加工時，xi,α=1；Ci為工件Ji的加工完成時間，所有工件加工完成所需的最大完成時間為各工件加工完成時間的最大值，即最大完工時間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)表示同一階段上工件加工的開始時間和完成時間的關(guān)系；式(6)表示工件加工的先后關(guān)系；式(7)表示第一階段排序靠前的工件先被加工；式(8)表示如果工件被分配在同一階段的同一設(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)嗅覺搜索。在中心果蠅個體的周圍產(chǎn)生其他果蠅個體，計算種群每個果蠅個體的適應(yīng)度，用于評價每個果蠅個體。

(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)重的大小依次排列，每種排列表示一個可行解，例如權(quán)重(0.20，0.18，0.36，0.25，0.64，0.57)對應(yīng)的工件排列順序為(5，6，3，4，1，2)，該排序表示工件5先加工，其次是工件6，最后是工件2。這種編碼方式能夠便于種群的更新操作。

3.2 解碼

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

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，對種群中的每一個果蠅個體X(i)以最大完成時間最小作為評價指標(biāo)進(jìn)行計算。單目標(biāo)適應(yīng)度函數(shù)為

F(x)=minCmax

(9)

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

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

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

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

∥工件排序

Sizepop=5；

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

K=6；

∥種群個體維度

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);

∥計算種群個體適應(yīng)度

Besta=arg min(F(i));

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

END FOR

3.5 視覺操作

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

X(i)=B1Qbest+B2Nr

(10)

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

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

4 仿真測試和比較

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

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

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

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

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

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

4.1 參數(shù)討論

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

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

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

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

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

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

4.2 實(shí)驗結(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)行對比。將評價次數(shù)10 000作為算法運(yùn)行終止條件，得到的結(jié)果如表6所示。文獻(xiàn)[16]給出了一種改進(jìn)的編碼方式，這種編碼方式能夠保證個體編碼的合法性。文獻(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，因此在相同的評價次數(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í)驗結(jié)果對比如表7所示，將FOA與PBIL[17](population-based incremental learning)、EDA[17](estimation of distribution algorithm)進(jìn)行對比。將評價次數(shù)3 000作為算法運(yùn)行終止條件。在相同評價次數(shù)中，F(xiàn)OA能100%找到最優(yōu)解13.5，其他2個算法沒能找到最優(yōu)解，從而驗證了算法的有效性和魯棒性。實(shí)例3的實(shí)驗結(jié)果對比如表8所示，將評價次數(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í)驗考察了2個參數(shù)對算法的影響。在相同的實(shí)驗條件下，改進(jìn)果蠅優(yōu)化算法更容易找到最優(yōu)解，且不容易陷入局部最優(yōu)。與GA、EDA、DE算法進(jìn)行對比，改進(jìn)果蠅優(yōu)化算法表現(xiàn)出了極好的隨機(jī)搜索能力和魯棒性。