張國輝，胡一凡，孫靖賀

(鄭州航空工業(yè)管理學(xué)院 管理工程學(xué)院，河南 鄭州450015)

柔性作業(yè)車間調(diào)度問題(flexible job shop scheduling problem，F(xiàn)JSP)是一個(gè)組合優(yōu)化問題，也是智能調(diào)度中非常關(guān)鍵的組成部分。隨著客戶個(gè)性化的需求增加，多品種小批量的生產(chǎn)模式逐步成為現(xiàn)代制造型企業(yè)的主要生產(chǎn)模式，實(shí)際加工狀況更加復(fù)雜。不同工件在不同設(shè)備上加工時(shí)，存在調(diào)整時(shí)間和設(shè)備之間的移動時(shí)間，由于每個(gè)時(shí)間都會對最后的完工時(shí)間造成影響，因此很多學(xué)者對不同狀況下的柔性作業(yè)車間調(diào)度問題進(jìn)行了研究。Shen等[1]考慮了具有序列依賴機(jī)器的調(diào)整時(shí)間，以最大完工時(shí)間最小化為目標(biāo)，提出了具有特定鄰域函數(shù)和多樣化結(jié)構(gòu)的禁忌搜索算法。Rossi等[2]將調(diào)整時(shí)間考慮到FMS布局的作業(yè)車間環(huán)境中。楊立熙等[3]將工件的運(yùn)輸時(shí)間作為獨(dú)立因素考慮到FJSP模型中，采用小生境思想劃分種群，避免算法陷入局部最優(yōu)。趙寧等[4]采用運(yùn)輸時(shí)間矩陣對析取圖模型進(jìn)行改進(jìn)，建立了設(shè)備選擇的多階段決策方法。隨著計(jì)算機(jī)技術(shù)的發(fā)展，智能優(yōu)化算法廣泛應(yīng)用于求解該問題。朱偉[5]為了降低FJSP問題的復(fù)雜性，提出了一種靈活資源約束的集成優(yōu)化方法。Nouri等[6]通過基于混合元啟發(fā)式的聚類全息多智能體模型來解決FJSP問題，有效搜索解空間。針對FJSP搜索空間大的特點(diǎn)，Zhang等[7]將粒子群算法和禁忌搜索算法進(jìn)行結(jié)合。余璇等[8]將遺傳算法與禁忌搜索算法進(jìn)行結(jié)合，提高了算法的搜索能力。余建軍等[9]采用雙種群雙倍體自適應(yīng)免疫算法對多目標(biāo)柔性作業(yè)車間調(diào)度問題進(jìn)行求解。李明等[10]采用融入新的革命策略的帝國競爭算法對柔性作業(yè)車間調(diào)度問題進(jìn)行求解。林震等[11]對最小化最大完工時(shí)間，機(jī)器總負(fù)荷最小等4個(gè)目標(biāo)進(jìn)行求解，提出多交叉策略的進(jìn)化算子?，F(xiàn)有文獻(xiàn)的研究主要集中在加工時(shí)間或在此基礎(chǔ)上增加了運(yùn)輸時(shí)間的約束。而同時(shí)考慮加工時(shí)間、調(diào)整時(shí)間和運(yùn)輸時(shí)間的文獻(xiàn)還沒有。在實(shí)際生產(chǎn)過程中，調(diào)整時(shí)間和運(yùn)輸時(shí)間的約束確實(shí)存在，忽視這些約束會使研究偏離實(shí)際情況，降低研究的實(shí)際意義。

考慮加工時(shí)間、調(diào)整時(shí)間和運(yùn)輸時(shí)間約束的柔性作業(yè)車間調(diào)度結(jié)果會受到工件的前置工序、機(jī)器上的前置工序、加工/調(diào)整時(shí)間以及機(jī)器之間的運(yùn)輸時(shí)間等更多方面的影響。因此，研究多時(shí)間約束的FJSP問題十分重要。根據(jù)問題特性，本文通過3種初始化方式、自適應(yīng)變異算子和外部檔案庫保留機(jī)制改進(jìn)傳統(tǒng)的遺傳算法，來提高算法的求解能力，并使用基準(zhǔn)實(shí)例進(jìn)行測試，驗(yàn)證了改進(jìn)的遺傳算法的有效性。

1問題描述與建模

1.1問題描述

柔性作業(yè)車間調(diào)度問題是經(jīng)典作業(yè)車間調(diào)度問題的擴(kuò)展[7]。其優(yōu)化問題描述如下。N個(gè)工件要在M臺機(jī)器上加工，每個(gè)工件包含的工序數(shù)不全相同且個(gè)數(shù)不小于1。每道工序只能同時(shí)被一臺機(jī)器加工，該機(jī)器是該工序可選機(jī)器集中的任意一臺機(jī)器。工件一道工序加工結(jié)束后進(jìn)入下一道工序，若同工件的相鄰工序的加工機(jī)器是同一臺，則無需考慮移動時(shí)間和調(diào)整時(shí)間。優(yōu)化目標(biāo)是最大完工時(shí)間最小化、總調(diào)整時(shí)間最小化和總移動時(shí)間最小化。

考慮多時(shí)間約束的FJSP問題的假設(shè)條件如下。

1)同一時(shí)刻在同一機(jī)器上只允許加工1個(gè)工件；

2)同一工件在同一時(shí)刻只能被一臺機(jī)器加工，且工件一旦開始加工就不能中斷；

3)每個(gè)工件工序的加工順序有先后之分，即每一道工序加工完成后會被送到下一道工序的機(jī)器上進(jìn)行加工；

4)工序加工時(shí)間會因所選擇的加工機(jī)器的不同而不同，加工時(shí)間是已知的；

5)同一個(gè)工件相鄰2道工序間在不同機(jī)器間移動時(shí)，移動時(shí)間因相鄰2道工序所選擇的加工機(jī)器的不同而不同，并且機(jī)器間的移動時(shí)間是給定的，若工件的連續(xù)2道工序在同一個(gè)機(jī)器上加工，則移動時(shí)間為0。

6)不同工序因選擇的加工機(jī)器不同而導(dǎo)致調(diào)整時(shí)間不同，并且機(jī)器的調(diào)整時(shí)間是給定的，若工件的前后2道工序在同一機(jī)器上連續(xù)加工，則調(diào)整時(shí)間為0。

1.2問題建模

工 件 集J={J1,J2,J3, ···,Jg, ···,Jn}；機(jī) 器 集M={M1,M2,M3, ···,Mi, ···,Mm}；OMil為在機(jī)器i上加工的第l道工序；OJjh為工件j的第h道工序(h=1,2,3, ···,kj)，工序OJj(h+1)為OJjh同工件的相鄰下一道工序，同理工序OJj(h-1)為OJjh同工件的相鄰上一道工序；TJijh為工件j的第h道工序在機(jī)器i上加工時(shí)所需要的時(shí)間；SJijh為工件j的第h道工序在機(jī)器i上的允許開始加工時(shí)間；SMil為機(jī)器i的加工第l道工序的允許開始加工時(shí)間；SJMijh為工件j的第h道工序在機(jī)器i上的實(shí)際開始加工時(shí)間；CJijh為工件j的第h道工序在機(jī)器i上的結(jié)束時(shí)間；CMil為機(jī)器i的加工第l道工序的結(jié)束時(shí)間；ATijh為工件j的第h道工序在機(jī)器i上的調(diào)整時(shí)間，MTiejh為工件j的因第h道工序在Mi和Me之間的移動時(shí)間；CJj為工件j的完工時(shí)間；Xijh=1表示工序OJjh在機(jī)器i上加工，Xijh=0表示工序OJjh不在機(jī)器i上加工；CT為所有工件完工時(shí)間中的最大完工時(shí)間；TAT為總調(diào)整時(shí)間；TMT為總移動時(shí)間。假設(shè)工件j的第h道工序?yàn)闄C(jī)器i加工的第l道工序。目標(biāo)函數(shù)如下。

最大完工時(shí)間最小化

總調(diào)整時(shí)間最小

總移動時(shí)間最小

式(4)為移動時(shí)間的約束；式(5)為調(diào)整時(shí)間約束；式(6)為工序開始加工時(shí)間，指工件移動到機(jī)器上的時(shí)間與機(jī)器調(diào)整完成時(shí)間中的較大者；式(7)為1個(gè)工件同一時(shí)刻只能被一臺機(jī)器加工；式(8)為一臺機(jī)器在同一時(shí)刻只能加工1個(gè)工件。

表1為一個(gè)柔性作業(yè)車間調(diào)度問題實(shí)例。若工件的前后相鄰工序在同一機(jī)器上連續(xù)加工，則調(diào)整時(shí)間為0，“-”表示對應(yīng)工序不能在對應(yīng)機(jī)器上加工。

表1工件在機(jī)器上的加工時(shí)間和調(diào)整時(shí)間Table 1 The processing time and set-up time

工件在不同機(jī)器之間的移動時(shí)間是非對稱式的，如表2所示。

表2工件在機(jī)器間的移動時(shí)間Table 2 The transport time

圖1為不帶調(diào)整時(shí)間和移動時(shí)間的調(diào)度甘特圖。其中，101在縱坐標(biāo)對應(yīng)值為4，表示第1個(gè)工件的第1道工序在機(jī)器4上加工，201在縱坐標(biāo)的對應(yīng)值為3，表示第2個(gè)工件的第1道工序在機(jī)器3上加工。圖2為帶調(diào)整時(shí)間和移動時(shí)間的調(diào)度甘特圖。其中，工件1的第1道工序(101)在機(jī)器4上加工，且加工前需要的調(diào)整時(shí)間為2。工件2的第3道工序在機(jī)器4上加工，且加工前機(jī)器的調(diào)整時(shí)間為1，工件2從機(jī)器3移到機(jī)器4的時(shí)間為2。

圖1不帶調(diào)整時(shí)間和移動時(shí)間的調(diào)度甘特圖Figure 1 Gantt chart without set-up time and transport time

圖2帶調(diào)整時(shí)間和移動時(shí)間的調(diào)度甘特圖Figure 2 Gantt chart with set-up time and transport time

從圖2中可以看出，帶調(diào)整時(shí)間和移動時(shí)間的調(diào)度甘特圖比不帶調(diào)整時(shí)間和移動時(shí)間的調(diào)度甘特圖最大完工時(shí)間多6。在實(shí)際的生產(chǎn)過程中，多出的6是有意義的。若不考慮調(diào)整時(shí)間和移動時(shí)間，得出的計(jì)劃的可行性會很低，若考慮了調(diào)整時(shí)間和移動時(shí)間，計(jì)劃方案對實(shí)際的生產(chǎn)具有更好的指導(dǎo)作用。

2改進(jìn)遺傳算法求解多時(shí)間約束的FJSP

2.1染色體編碼

有效的編碼在不產(chǎn)生非法解的情況下能表達(dá)出個(gè)體與可行解的關(guān)系。FJSP包含2個(gè)子問題：機(jī)器選擇和工序排序。因此，本文采用兩段式編碼方式，將2個(gè)子問題編碼到一條染色體上，用來表示FJSP的一個(gè)可行解[7]。

2.2染色體解碼

采用左移插入式解碼分別對機(jī)器選擇子問題和工序排序子問題進(jìn)行解碼。機(jī)器選擇部分解碼如下。從左到右依次讀取機(jī)器部分染色體，并轉(zhuǎn)換到機(jī)器順序矩陣J m，工件加工時(shí)間矩陣T1、機(jī)器調(diào)整時(shí)間矩陣T2和工件的移動時(shí)間矩陣T3。Jm(j,h)為第j個(gè)工件的第h道加工工序的機(jī)器號；T1(j,h)為第j個(gè)工件的第h道工序加工時(shí)間；T2(j,h)為第j個(gè)工件的第h道工序機(jī)器的調(diào)整時(shí)間；T3(j,h)為第j個(gè)工件的第h道工序工件移動到機(jī)器上的移動時(shí)間。Jm(j,h)、T1(j,h)、T2(j,h)、T3(j,h)是相互對應(yīng)關(guān)系。工序排序部分解碼如下。從左到右依次讀取工序染色體部分，并對此工序結(jié)合機(jī)器的調(diào)整時(shí)間和工件移動時(shí)間進(jìn)行排序得到調(diào)度結(jié)果。如果工序OJjh是工件j的第1道工序，且是機(jī)器i加工的第1道工序，直接從機(jī)器調(diào)整后的時(shí)間進(jìn)行加工；若工序OJjh不是工件j的第1道工序，但是機(jī)器i的第1道工序，則將OJj(h-1)加工結(jié)束的時(shí)間加工件移動到機(jī)器i上的時(shí)間與機(jī)器調(diào)整后的時(shí)間的較大者作為工序開始加工時(shí)間；當(dāng)工序OJjh不是工件j的第1道工序，且機(jī)器i上已經(jīng)有工件在加工，則需要考慮在機(jī)器i上加工的相鄰的2個(gè)工件之間的空隙時(shí)間段TSEik是否可以滿足下個(gè)工序的加工。假設(shè)空隙開始時(shí)間為TSik，空隙結(jié)束時(shí)間為TEik。當(dāng)工序OJjh在機(jī)器i上加工時(shí)，首先判斷產(chǎn)生空隙的前面工序是否與本工序?yàn)橥还ぜ倪B續(xù)的2個(gè)工序，若為連續(xù)的2個(gè)工序，則調(diào)整時(shí)間為0。

解碼的偽代碼如下。輸入:染色體

輸出:活動調(diào)度結(jié)果

2.3適應(yīng)度值計(jì)算

采用歸一化求和的方式計(jì)算個(gè)體適應(yīng)度值，具體步驟如下。

1)對種群進(jìn)行解碼，得到所有個(gè)體的最大完工時(shí)間、總調(diào)整時(shí)間、總移動時(shí)間，并對這3個(gè)指標(biāo)分別作歸一化處理。

2)每個(gè)個(gè)體以這3個(gè)指標(biāo)的和作為評價(jià)值fi，fi越小則該個(gè)體越好。

3)將所有個(gè)體按評價(jià)值fi從小到大排序，評價(jià)值fi相同的個(gè)體名次一樣。名次ni越靠前的個(gè)體，其適應(yīng)度值Fi越高。根據(jù)最差個(gè)體的名次max (ni)將適應(yīng)度值上限a均等分。因此，個(gè)體適應(yīng)度值Fi=

2.4初始化

生成初始化解時(shí)不僅要保證解的多樣性，也要保證解的質(zhì)量。為了滿足這2個(gè)要求，本文按照以下3種方式生成初始種群。

1)隨機(jī)生成法。機(jī)器部分：每個(gè)工序隨機(jī)在可選機(jī)器集中選擇一個(gè)；工序部分：隨機(jī)產(chǎn)生工件的加工順序。

2)最小時(shí)間選擇法。機(jī)器部分：選擇當(dāng)前工序的可選機(jī)器中加工該工序時(shí)間最小的機(jī)器；工序部分：隨機(jī)產(chǎn)生工件的加工順序。

3)剩余加工時(shí)間最大優(yōu)先選擇法。機(jī)器部分：每個(gè)工序隨機(jī)在可選擇加工機(jī)器集中選擇一個(gè)；工序部分：選擇當(dāng)前工件剩余總加工時(shí)間最大的工件。

2.5交叉算子

為提高搜索的效率，在信息交換的過程中，應(yīng)較好的解與較好的解進(jìn)行交叉的概率大，較差的解與較好的解進(jìn)行交叉的概率大，較差的解與較差的解交叉的概率小。為此本文提出人工配對機(jī)制，具體步驟如下。

1)隨機(jī)從種群中選擇出N個(gè)個(gè)體。

2)根據(jù)個(gè)體的適應(yīng)度，采用輪盤賭的形式，從被選擇的N個(gè)個(gè)體中選擇出2個(gè)個(gè)體。

3)將挑選出的2個(gè)個(gè)體進(jìn)行交叉。機(jī)器部分采用多點(diǎn)式交叉方式，工序部分采用POX方式[12]。

2.6變異算子

為了使得較好的解在更大的空間內(nèi)搜索，采用自適應(yīng)權(quán)重的方式對不同的個(gè)體生成不同的變異率和鄰域搜索范圍。

其中，Pm為個(gè)體的變異率；Pmax、Pmin分別為交叉率的最大值和最小值；F為個(gè)體的適應(yīng)度；Fmin為最差的個(gè)體的適應(yīng)度；Favg為種群的平均適應(yīng)度。當(dāng)個(gè)體的適應(yīng)度比較好時(shí)，增加個(gè)體的變異率，使個(gè)體的搜索空間更大，避免陷入局部最優(yōu)；當(dāng)個(gè)體的適應(yīng)度比較差時(shí)，減小個(gè)體的變異率，更多地保留個(gè)體與較好的解交叉形成的優(yōu)良基因。

由于染色體包括2部分，因此，分別采用不同的操作方式進(jìn)行變異。

1)機(jī)器選擇部分：采用輪盤賭的方式，以概率選擇加工機(jī)器，選擇加工時(shí)間大的機(jī)器概率小，選擇加工時(shí)間小的機(jī)器概率大。

2)工序排序部分：采用自適應(yīng)鄰域搜索的方式對工序部分進(jìn)行替換。

①按照適應(yīng)度的大小，把個(gè)體分成5個(gè)等級(1～5)。適應(yīng)度越大的個(gè)體等級越高，第5級的個(gè)體的鄰域搜索范圍為5，即5個(gè)變異點(diǎn)，第4級的個(gè)體的鄰域搜索范圍為4。依次類推。

②根據(jù)生成的鄰域搜索范圍在工序排序部分隨機(jī)選擇出變異點(diǎn)。

③生成鄰域解的所有排列組合，生成新的鄰域搜索解。

④評價(jià)所有的鄰域解，輸出適應(yīng)度值最高的鄰域解，將其加入到種群中。

2.7外部檔案庫

增加外部檔案庫可以避免優(yōu)良的個(gè)體在交叉變異選擇過程中丟失。根據(jù)最大完工時(shí)間、總調(diào)整時(shí)間、總移動時(shí)間判斷當(dāng)前種群中的解是否支配外部檔案庫中的某個(gè)個(gè)體，或是否與外部檔案庫中的個(gè)體為非支配關(guān)系，若是，則將其記錄在外部檔案庫中，同時(shí)刪除檔案庫中被支配的個(gè)體。

2.8選擇操作

選擇已被證明的相對于其他選擇算子有更好的或相當(dāng)收斂性和計(jì)算復(fù)雜性的錦標(biāo)賽選擇法。

2.9算法流程

改進(jìn)遺傳算法求解帶有移動時(shí)間和調(diào)整時(shí)間的柔性作業(yè)車間調(diào)度問題執(zhí)行步驟如下。

步驟1設(shè)置參數(shù)。確定種群規(guī)模P、迭代次數(shù)G、交叉率、最大變異率、最小變異率等；

步驟2按照隨機(jī)生成法、最小時(shí)間選擇法、剩余加工時(shí)間最大優(yōu)先選擇法3種方式生成初始解；

步驟3計(jì)算、評價(jià)種群中每個(gè)染色體的適應(yīng)度值即目標(biāo)值，比較其大小，若滿足輸出條件結(jié)束運(yùn)行，否則執(zhí)行步驟4；

步驟4采用錦標(biāo)賽的方式進(jìn)行選擇，選出待交叉?zhèn)€體；

步驟5采取人工配對的方式，對種群中滿足交叉要求的2個(gè)個(gè)體分別進(jìn)行機(jī)器和工序部分的交叉；

步驟6采用自適應(yīng)權(quán)重的方式對不同個(gè)體生成不同的變異率和鄰域搜索范圍，對種群中滿足變異要求的個(gè)體分別進(jìn)行機(jī)器和工序部分的變異；

步驟7對新生成的種群與外部檔案庫的個(gè)體進(jìn)行比較，選出非支配解并記錄在外部檔案庫中；

步驟8返回步驟3。

3實(shí)驗(yàn)結(jié)果

依據(jù)改進(jìn)的遺傳算法，采用Matlab 2017a編程。運(yùn)行環(huán)境為P4 CPU，主頻1.9 GHz，內(nèi)存4 G的個(gè)人計(jì)算機(jī)。每一個(gè)測試問題連續(xù)運(yùn)行10次。為了能夠讓改進(jìn)的算法執(zhí)行效率更高，得到的解更好，在可接受的時(shí)間范圍內(nèi)，對參數(shù)進(jìn)行選擇。根據(jù)問題規(guī)模的大小，設(shè)置不同的遺傳代數(shù)，其余主要參數(shù)如表3所示。

表3算法參數(shù)Table 3 The algorithm parameters

本文采用的測試問題來自Brandimarte[13]的測試數(shù)據(jù)。但是這些數(shù)據(jù)都只有加工時(shí)間，本文根據(jù)加工時(shí)間隨機(jī)生成調(diào)整時(shí)間與移動時(shí)間。

首先，測試MK01。MK01包含6臺機(jī)器，10個(gè)工件，共有55道工序。運(yùn)算結(jié)果如表4所示。

表4 MK01問題的非支配解集Table 4 The non-dominated solution set of MK01

圖3為該問題的非支配解集分布圖。從圖3可以看出，解在空間中均勻分布，種群的多樣性較好，具有一定的代表性。

圖3 MK01問題的非支配解集分布圖Figure 3 The distribution of non-dominated solution set of MK01

圖4為與解1對應(yīng)的甘特圖。圖4中有很多淺藍(lán)色的方塊，表示該解總移動時(shí)間較大。雖然解1為Mk01非支配解集中最大完工時(shí)間最小的解，但因其總移動時(shí)間較大，在實(shí)際生產(chǎn)計(jì)劃中并不適用。非支配解集中的解無法互相支配，即沒有優(yōu)劣之分。但在實(shí)際中，決策者可根據(jù)實(shí)際情況選擇其中的最合適的解為執(zhí)行方案。

本文提出的算法與其他算法的比較如表5所示。Number為找到的非支配解的個(gè)數(shù)；BMCT、BTST、BTMT分別為非支配解集中最大完成時(shí)間的最優(yōu)值、總調(diào)整時(shí)間的最優(yōu)值和總移動時(shí)間的最優(yōu)值。GA為未進(jìn)行改進(jìn)的遺傳算法策略。PSO+TS為Zhang等[7]提出的算法策略，IGA為本文采用的算法策略。

從表5可以看出，隨著數(shù)據(jù)復(fù)雜度的增加，3種算法得到的非支配解的數(shù)量均有所增加。本文算法在大多數(shù)情況下都優(yōu)于GA和PSO+TS。隨著數(shù)據(jù)規(guī)模和復(fù)雜性的增加，IGA可以找到更多的非支配解，并提供不同的解決方案。雖然在某些問題中發(fā)現(xiàn)的非支配解的數(shù)量比其他2種算法少，但其解的質(zhì)量要優(yōu)于其他算法。即IGA找到的解在一定程度上可以支配其他2種算法找到的解，驗(yàn)證了該算法對求解多時(shí)間約束的車間調(diào)度模型的有效性。

4結(jié)束語

為解決多時(shí)間約束下的柔性作業(yè)車間調(diào)度問題，本文中提出了一種考慮加工時(shí)間、調(diào)整時(shí)間和移動時(shí)間約束的柔性作業(yè)車間調(diào)度模型，對遺傳算法進(jìn)行改進(jìn)并用于求解模型。通過實(shí)驗(yàn)分析驗(yàn)證了該方法的可行性和有效性。得到結(jié)論如下。

1)種群初始化時(shí)，設(shè)計(jì)不同的策略生成初始解，可以保證解的覆蓋范圍，并且提高解的質(zhì)量，從而提升算法搜索效率。

2)個(gè)體進(jìn)行交叉操作時(shí)，為了避免優(yōu)良解的基因被破壞，將優(yōu)良信息傳遞到子代中，設(shè)計(jì)了人工配對方式。這使得較差解可以快速改進(jìn)，進(jìn)而使種群進(jìn)行更加有效的交叉。

3)個(gè)體進(jìn)行變異操作時(shí)，為了保證種群的多樣性，同時(shí)期望搜索的效率更高，提出了對不同的個(gè)體設(shè)計(jì)自適應(yīng)的變異率和變異范圍，以進(jìn)行不同的變異操作，提高解的質(zhì)量。

圖4 解1的甘特圖Figure 4 The Gantt chart of solution 1

表5 MK系列問題的算法結(jié)果對比Table 5 The comparison of algorithm results of MK series problems