李長云 林 多 何頻捷 谷鵬飛

（①湖南工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，湖南 株洲 412007；②湖南工業(yè)大學(xué)軌道交通學(xué)院，湖南 株洲 412007）

柔性作業(yè)車間調(diào)度問題[1](flexible job shop scheduling problem，F(xiàn)JSP)是一種研究生產(chǎn)資源的分配與工件工序的加工順序的問題，具有加工設(shè)備不確定和工藝路線柔性等特性。在實(shí)際的車間生產(chǎn)環(huán)境中，很多工件的工藝流程具有偏序關(guān)系，可能會(huì)包含工序具有共同前繼工序或者多個(gè)前繼工序的情況，以服裝生產(chǎn)車間為例[2]，在布料裁剪階段之后可以由不同機(jī)器并行完成服裝不同部位的縫制，最后再統(tǒng)一進(jìn)行拼接和后續(xù)操作。提高工序的并行性并考慮前繼工序的約束性，能夠?qū)崿F(xiàn)具有偏序工藝流程的柔性車間調(diào)度，提高工廠資源的利用效率。

國內(nèi)外學(xué)者對(duì)FJSP的研究主要集中在機(jī)器柔性和順序工藝流程的問題，對(duì)具有復(fù)雜偏序關(guān)系的FJSP研究較少。其中，謝志強(qiáng)等[3?4]針對(duì)串行工序的緊密度和并行工序的并行性提出考慮后續(xù)工序的擇時(shí)綜合調(diào)度算法。唐紅濤等[5]針對(duì)包含并行工序集的車間提出動(dòng)態(tài)觸發(fā)鄰域機(jī)制增強(qiáng)算法的局部搜索能力。劉曉平等[6]提出了工序和設(shè)備分段編碼從而實(shí)現(xiàn)適應(yīng)工件工序可并行的解碼算法，縮短了最大完工時(shí)間。徐本柱等[7]研究了工序的并行特性，有效地縮短了產(chǎn)品完工時(shí)間。以上算法大都對(duì)復(fù)雜的并行工序情況考慮不全面，沒有有效地解決串行工序的緊湊度和并行工序的并行性之間的關(guān)系，同時(shí)未考慮瓶頸工單和瓶頸機(jī)器中工件的偏序關(guān)系對(duì)最小化完工時(shí)間的影響。

本文針對(duì)偏序柔性作業(yè)車間調(diào)度問題(partial order flexible job-shop scheduling problem，POFJSP)提出了改進(jìn)的算術(shù)優(yōu)化算法(improved arithmetic optimization algorithm,IAOA)，設(shè)計(jì)了基于適應(yīng)度和工序完工差異度的二維聚類交叉和有效變異策略，并引入一種等級(jí)鄰域變異策略對(duì)瓶頸工單和瓶頸機(jī)器上的工序分等級(jí)進(jìn)行變異，有效地縮短了具有偏序關(guān)系工件的最大完工時(shí)間。最后通過仿真實(shí)驗(yàn)對(duì)比其他優(yōu)化算法驗(yàn)證本文所提算法的可行性和優(yōu)越性。

1 問題模型描述和約束建立

1.1 偏序柔性車間調(diào)度問題描述

FJSP中工件工序按照順序關(guān)系調(diào)度[8]，每個(gè)工序在加工機(jī)器集中選擇一個(gè)機(jī)器進(jìn)行生產(chǎn)。服裝車間中工件的生產(chǎn)需要經(jīng)過多個(gè)工序的加工，每個(gè)工序可由一個(gè)或多個(gè)機(jī)器進(jìn)行加工，每個(gè)工序存在一個(gè)或多個(gè)前繼工序。因此服裝車間的調(diào)度問題和FJSP比較類似，但是需要考慮工件加工具有復(fù)雜偏序工藝流程的特點(diǎn)。故將服裝車間的調(diào)度問題抽象為POFJSP，該問題是FJSP的衍生，針對(duì)工件的生產(chǎn)工藝流程通常不是順序型工藝流程，而是具有偏序關(guān)系的生產(chǎn)加工關(guān)系調(diào)度進(jìn)行研究。

該問題可以采用如下描述：每臺(tái)機(jī)器完成不同的工單工序所花費(fèi)的時(shí)間不同，每個(gè)工單加工產(chǎn)品的工藝流程不同，假設(shè)共有n個(gè)工單Job={J1,J2,J3,···,Jn}，每個(gè)工單Ji(1≤i≤n)包含pi個(gè)工序O={Oi1,Oi2,Oi3,···,Oip}，工單工序可以在m個(gè)機(jī)器M={M1,M2,M3,···,Mm}上進(jìn)行生產(chǎn)，若工單工序在某些機(jī)器Mk(1≤k≤m)上不能生產(chǎn)，則對(duì)應(yīng)的生產(chǎn)時(shí)間為空。一個(gè)工件的工序可能具有一個(gè)或多個(gè)前繼工序以及后繼工序，工序Oij具有前繼工序集Fij和后繼工序集Sij。工序的加工時(shí)間要介于前繼工序與后繼工序之間，并具有嚴(yán)格的加工次序約束。

工件工藝流程如圖1所示，工件J1的工藝流程中工序O12,O13,O14擁有共同的前繼工序O11，工序O11的后繼工序集S11={O12,O13,O14}可并行加工；工序O26有多個(gè)前繼工序O24,O25，其最早開始時(shí)間為前繼工序集F26={O24,O25}中結(jié)束時(shí)間ET24,ET25較晚的值。

圖1 工件工藝流程圖

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

針對(duì)偏序柔性車間調(diào)度問題，本文基于以下假設(shè)建立數(shù)學(xué)模型：

（1）零時(shí)刻可加工所有工件的第一個(gè)工序，且所有機(jī)器屬于待工狀態(tài)。

（2）一臺(tái)機(jī)器上不能同時(shí)加工多個(gè)工序。

（3）同一個(gè)工件的前繼工序全部加工完成后才能開始下一道工序。

（4）某工件一旦在某機(jī)器上開始加工，不可中斷當(dāng)前工序的運(yùn)作。

（5）工件加工互不影響，機(jī)器加工互不影響。

為了后續(xù)描述表達(dá)方便，現(xiàn)將各變量定義如表1所示。

表1 符號(hào)及其描述

本文研究的優(yōu)化目標(biāo)為最小化機(jī)器最大完工時(shí)間[9]，基于上述假設(shè)條件和數(shù)學(xué)符號(hào)描述模型約束

其中：式（1）表示工件Ji（1≤i≤n）的最大完工時(shí)間；式（2）表示優(yōu)化目標(biāo)為最小化機(jī)器最大完工時(shí)間，即適應(yīng)度；式（3）表示工件的每道工序只能在一臺(tái)機(jī)器上加工；式（4）表示工件工序含有一個(gè)或者多個(gè)前繼工序，規(guī)定工單開始工序的前繼工序?yàn)榭眨皇剑?）表示工件的結(jié)束工序不包含后繼工序（置為空集），其他工序的后繼工序集中包含一個(gè)或多個(gè)工序；式（6）表示需要完成當(dāng)前工單工序的全部前繼工序后才開始加工；式（7）表示Oij的最早結(jié)束時(shí)間為其前繼工序的完成時(shí)間的最大值與其所在加工機(jī)器上的加工時(shí)間之和；式（8）表示機(jī)器加工當(dāng)前工序完成之后才能開始下一個(gè)工序的加工。

2 基于等級(jí)鄰域策略的改進(jìn)算術(shù)優(yōu)化算法（IAOA+GNS）設(shè)計(jì)

算術(shù)優(yōu)化算法(arithmetic optimization algorithm,AOA)[10]是一種群智能算法，用于解決連續(xù)型運(yùn)籌優(yōu)化問題，具有調(diào)整參數(shù)少，收斂速度快等優(yōu)點(diǎn)，其思想適用于解決偏序柔性車間調(diào)度問題。在原始的AOA中，將其分為兩個(gè)主要階段：勘探和開發(fā)。在勘探階段算法先對(duì)搜索空間進(jìn)行廣泛覆蓋搜索，以避免陷入局部解，開發(fā)階段對(duì)勘探階段得到的解進(jìn)行鄰域搜索，算法步驟如下。

Step1：設(shè)定種群迭代次數(shù)T，種群大小popsize，隨機(jī)初始化生成一組候選解X(1)。首先解碼根據(jù)式（2）計(jì)算種群適應(yīng)度MS，并將當(dāng)代種群的最佳候選解視為目前獲得的最佳解Xbest(t)，然后通過式（9）計(jì)算MOA(t)進(jìn)行階段選擇。MOA(t)為選擇概率，Min為最小概率，Max為最大概率，本文設(shè)定Min=0.2，Max=1，隨著迭代次數(shù)的增加，選擇開發(fā)階段概率逐漸大于勘探階段。

Step2：勘探階段，在Xbest(t)附近使用搜索策略在多個(gè)解空間上進(jìn)行隨機(jī)搜索，從而擴(kuò)大種群多樣性。

Step3：開發(fā)階段，利用搜索策略在適應(yīng)度值較高的解鄰域進(jìn)行深入搜索，并在經(jīng)過多次迭代之后發(fā)現(xiàn)接近最優(yōu)的解。

AOA算法主要用于求解連續(xù)型問題，本文研究的POFJSP屬于離散型問題，因此提出一種基于偏序工序的改進(jìn)算術(shù)優(yōu)化算法（IAOA），其次在勘探階段設(shè)計(jì)了基于適應(yīng)度和工序完工差異度的二維聚類交叉和有效并行變異策略增加種群多樣性，在開發(fā)階段設(shè)計(jì)了一種等級(jí)鄰域搜索（grade neighborhood search，GNS）策略增強(qiáng)算法的局部搜索能力。最后結(jié)合兩者提出基于等級(jí)鄰域策略的改進(jìn)算術(shù)優(yōu)化算法（IAOA+GNS）求解POFJSP。

基于等級(jí)鄰域變異策略的改進(jìn)算術(shù)優(yōu)化算法流程如圖2所示。

圖2 IAOA+GNS算法流程圖

2.1 編碼解碼

POFJSP需要考慮到工件工序以及生產(chǎn)機(jī)器的安排，本文采取雙編碼形式Xi(t)=[Xg|Xm]對(duì)工序和機(jī)器進(jìn)行編碼，Xg為工序編碼部分，工件Ji出現(xiàn)的次數(shù)為其第j個(gè)工序，Xm為機(jī)器編碼部分，表示對(duì)應(yīng)工序Oij的可選機(jī)器集中的機(jī)器編號(hào)Mijk。編碼形式如圖3所示。

圖3 編碼示例圖

解碼是群智能算法能否解決車間調(diào)度問題的關(guān)鍵，考慮解碼的多約束性并通過工件前繼工序和機(jī)器可用時(shí)間段可以確定后繼工序的最優(yōu)加工時(shí)間，IAOA進(jìn)行解碼時(shí)具有以下步驟：

Step1：將候選解Xi(t)的工序編碼部分換算為工件工序Oij列表，找到對(duì)應(yīng)的安排機(jī)器Mijk。

Step2：將前繼工序?yàn)榭占墓ば虻淖钤缈砷_始時(shí)間TSTij初始化為0，其他的工序則按照式（6）計(jì)算其TSTij。

Step3：對(duì)Oij使用基于插入優(yōu)先的解碼策略：當(dāng)Oij安排的Mijk上已安排的工序數(shù)大于0時(shí)，轉(zhuǎn)到Step3.1，否則轉(zhuǎn)到Step3.3。

Step3.1：判斷Oij能否插入到Mijk上的第一個(gè)工序前，如果第一個(gè)工序的開始時(shí)間STM1k大于等于Oij的TSTij和其加工時(shí)間MTijk之和，則跳轉(zhuǎn)到Step4，否則判斷Mijk上已安排的工序數(shù)是否大于1，是則跳到Step3.2，否則跳到Step3.3。

Step3.2：循環(huán)安排在Mijk上，且時(shí)間在Oij的TSTij之后的所有工序OMvk，使用式（8）計(jì)算兩個(gè)工序之間的時(shí)間間隔IMvk，在Oij的TSTij和工序OMvk的結(jié)束時(shí)間ETMvk中選擇較大的值，判斷該值和Oij的加工時(shí)間MTijk之和是否小于下一個(gè)工序的開始時(shí)間STM(v+1)k，并且IMvk是否大于等于Oij的MTijk，是則表示可以插入該空閑時(shí)間段，轉(zhuǎn)到Step4。循環(huán)完畢，如發(fā)現(xiàn)沒有可插入的時(shí)間段，則跳轉(zhuǎn)到Step3.3。

Step3.3：Oij不能插入Mijk上的空閑時(shí)間段，在Oij的TSTij和Mijk上已安排的最后一道工序的結(jié)束時(shí)間ETMvk中選擇較大的值，該值即為Oij的真正開始時(shí)間STij。

Step4：利用式（1）和式（2）算出目標(biāo)函數(shù)值。

如圖4所示，有3個(gè)具有偏序關(guān)系的工件，將部分工序按照解碼步驟解碼到調(diào)度甘特圖，以工序O22為例，其TSTij=3，機(jī)器M1安排工序數(shù)大于2，轉(zhuǎn)到Step3.2檢查空位1發(fā)現(xiàn)IM12≥MT221但MT221+TST22≤STM21，檢查空位2發(fā)現(xiàn)IM22≥MT221且ETM21+MT221≤STM31，符合條件，可插入空位2。

圖4 解碼調(diào)度甘特圖

2.2 種群初始化

種群初始化的質(zhì)量好壞直接影響到算法求解速度和最終解的質(zhì)量，為了減少無效解的產(chǎn)生并增加種群多樣性，采用以下兩種方法進(jìn)行種群初始化（兩種方法生成的初始解在初始種群數(shù)量中各占50%）。

正向法：首先隨機(jī)打亂工序編碼，并為每道工序隨機(jī)分配機(jī)器，隨后通過前繼工序表查看所有工序，將具有共同前繼工序的工序編碼排在一起，最后檢查同一工單中具有共同前繼工序的工序的機(jī)器編碼，如果在同一臺(tái)機(jī)器上加工，則在可選機(jī)器集中重新選擇機(jī)器進(jìn)行分配。

逆向法：由正向法生成的工件編碼通過倒置得到逆向編碼，機(jī)器編碼仍采用正向法編碼規(guī)則隨機(jī)生成。

2.3 勘探階段

IAOA算法在傳統(tǒng)AOA算法上融合了GA算法的思想，將搜索策略替換成了交叉和變異，以此解決離散調(diào)度問題，因此在勘探階段中使用二維聚類交叉策略和有效并行變異策略擴(kuò)大種群多樣性。

2.3.1 二維聚類交叉策略

本文使用聚類交叉方法進(jìn)行操作，由于不同適應(yīng)度值的兩類個(gè)體基因存在相似可能性，因此對(duì)種群內(nèi)每個(gè)個(gè)體引入工序完工差異度（degree of variance of process completion,DVPCs），DVPCs可以計(jì)算出不同個(gè)體基因之間的差異度，結(jié)合適應(yīng)度值組成二維聚類再進(jìn)行交叉增大種群多樣性。工序完工差異度計(jì)算式（10）如下。

首先以當(dāng)前迭代種群最優(yōu)個(gè)體Xbest作為基準(zhǔn)，對(duì)種群中所有個(gè)體的適應(yīng)度MSs和DVPCs統(tǒng)一進(jìn)行最大最小歸一化，范圍為[0,1]，并以MSs和DVPCs作為指標(biāo)繪制散點(diǎn)圖。隨后使用k-means聚類算法對(duì)種群進(jìn)行二維聚類，其中參數(shù)k為聚類的數(shù)量，本文將k設(shè)為4，對(duì)應(yīng)不同MSs和DVPCs下的個(gè)體類，聚類算法結(jié)果如圖5所示。

圖5 適應(yīng)度和完工差異度聚類圖

隨后隨機(jī)選擇兩類中的個(gè)體作為父代，保留其中適應(yīng)度較小的父代中的優(yōu)秀基因，優(yōu)秀基因?yàn)閭€(gè)體基因中工單緊湊度（work order compactness，WOC）高的工單，WOC可通過比較工單理想完成時(shí)間和工單實(shí)際完成時(shí)間獲得，如式（11）所示。

優(yōu)秀基因的保留能夠加快迭代速度并優(yōu)化子代基因以獲取更優(yōu)解。最后使用POX交叉將父代P1的優(yōu)秀基因保留，其他基因刪除，并將另一父代P2中除了優(yōu)秀基因工單外的其他工單從左到右依次填補(bǔ)到P1的空基因位上得到交叉后的子代基因。

2.3.2 有效并行變異策略

針對(duì)變異過程中可能存在的無效變異問題，本文對(duì)機(jī)器變異和工序變異進(jìn)行了以下改進(jìn)。

機(jī)器變異：隨機(jī)選擇總數(shù)量中20%的工序，將其對(duì)應(yīng)機(jī)器換成可選機(jī)器集中加工時(shí)間更短的機(jī)器進(jìn)行加工。

工序變異：針對(duì)不同機(jī)器上的工序進(jìn)行位置交換可能對(duì)該機(jī)器的加工工序數(shù)量和順序不具有任何影響，從而導(dǎo)致無效變異的問題。本文對(duì)同一臺(tái)機(jī)器上加工的任意多個(gè)工序交換位置，可有效減少無效變異。

2.4 開發(fā)階段

影響適應(yīng)度函數(shù)的直觀原因在于以下兩點(diǎn)：一是瓶頸工單的WOC在所有工單的WOC中處于較低值，大部分工序在對(duì)應(yīng)機(jī)器上的加工時(shí)間比較長，且與前繼工序之間的時(shí)間間隔較大；二是瓶頸機(jī)器上的利用率遠(yuǎn)高于其他機(jī)器，瓶頸機(jī)器上加工的工序?qū)?duì)目標(biāo)函數(shù)值起到?jīng)Q定作用。

基于上述問題，開發(fā)階段在多個(gè)密集解空間上深入搜索最優(yōu)解，使用等級(jí)鄰域搜索策略（GNS）分別對(duì)瓶頸工單和瓶頸機(jī)器兩個(gè)方面進(jìn)行鄰域搜索。GNS策略如下：

（1）優(yōu)先級(jí)設(shè)定。首先為不同情況下的工序設(shè)定優(yōu)先等級(jí)，具有多個(gè)后繼工序的工序在機(jī)器上的完成時(shí)間能夠影響到所有后繼并行工序的完成進(jìn)度，是縮短工單的最大完工時(shí)間的重要因素，因此該類工序?yàn)樽罡邇?yōu)先級(jí)G1；多數(shù)工序只存在一個(gè)后繼工序，可以通過對(duì)該類工序使用優(yōu)化策略縮小目標(biāo)函數(shù)值，因此設(shè)為中等優(yōu)先級(jí)G2；最后一道工序?qū)φ麄€(gè)工單的完成時(shí)間影響不大，設(shè)為最低優(yōu)先級(jí)G3。

（2）變異策略設(shè)定。針對(duì)不同原因?qū)ば蜻M(jìn)行不同的變異策略，分為以下3種情況討論。

GNS1：如果當(dāng)前工序的開始時(shí)間和前繼工序的完成時(shí)間間隔大于當(dāng)前工序加工時(shí)間的一半，則將當(dāng)前工序與對(duì)應(yīng)機(jī)器上其前繼工序完成時(shí)間之后開始加工的其他工序隨機(jī)進(jìn)行位置互換；

GNS2：如果當(dāng)前工序與前繼工序的時(shí)間間隔較小，則將當(dāng)前工序換到可選機(jī)器集中加工時(shí)間更少的機(jī)器；

GNS3：如果當(dāng)前工序所處機(jī)器上沒有空閑時(shí)間段，則將當(dāng)前工序交換至可選機(jī)器集中機(jī)器負(fù)載更小的機(jī)器上。

若同時(shí)滿足多種情況，則隨機(jī)選擇一種情況進(jìn)行變異。

（3）瓶頸工單或瓶頸機(jī)器變異。對(duì)瓶頸工單或瓶頸機(jī)器中的所有工序進(jìn)行優(yōu)先級(jí)排序，隨后使用輪盤賭算法按照優(yōu)先級(jí)隨機(jī)挑選10%工序，并根據(jù)不同情況進(jìn)行變異。

以圖4所示的解碼調(diào)度甘特圖為例，假設(shè)在第t次迭代中對(duì)瓶頸工件J3進(jìn)行等級(jí)鄰域變異，其中O31的優(yōu)先級(jí)最高有多個(gè)后繼工序S31={O32,O33}，使用GNS3策略選擇可選機(jī)器集中負(fù)載更低的機(jī)器M1進(jìn)行加工，得到的調(diào)度甘特圖如圖6所示，有效地提前了工件J3的部分工序加工時(shí)間。

圖6 瓶頸工件使用等級(jí)鄰域策略結(jié)果圖

假設(shè)在第t+1次迭代中對(duì)瓶頸機(jī)器M1上的加工工序進(jìn)行等級(jí)鄰域變異，采用GNS1策略對(duì)工序O22與其前繼工序的完成時(shí)間之后開始加工的工序O13進(jìn)行位置交換，調(diào)度甘特圖如圖7所示，最大完工時(shí)間從原先的11有效地縮短到10。

圖7 瓶頸機(jī)器使用等級(jí)鄰域策略結(jié)果圖

3 仿真實(shí)驗(yàn)與案例分析

目前沒有標(biāo)準(zhǔn)算例驗(yàn)證本文的研究問題，因此本文基于Brandimarte P[11]所提出的10個(gè)案例Mk01～Mk10拓展了適用于偏序柔性車間調(diào)度問題的測試算例，表2為生成的擴(kuò)展算例的參數(shù)，新算例PMk01～PMk10在基準(zhǔn)算例的基礎(chǔ)上添加了每個(gè)工序的前繼工序集合，為了表達(dá)方便，假設(shè)每個(gè)算例中工件的工藝流程一樣。

表2 擴(kuò)展算例參數(shù)

3.1 參數(shù)對(duì)比實(shí)驗(yàn)

智能優(yōu)化算法的優(yōu)化結(jié)果受算法參數(shù)的影響很大，影響算法性能的參數(shù)有：種群規(guī)模popsize，最大迭代次數(shù)T，本文實(shí)驗(yàn)所用算法均采用相同參數(shù)值。以PMk09為測試算例，選擇規(guī)模為(32)的正交實(shí)驗(yàn)進(jìn)行測試，為避免結(jié)果的隨機(jī)性，以30次結(jié)果的平均值作為評(píng)價(jià)指標(biāo)，正交實(shí)驗(yàn)結(jié)果如表3所示。

表3 正交實(shí)驗(yàn)結(jié)果比較表

可以從表中看出當(dāng)種群規(guī)模popsize=90，最大迭代次數(shù)T=70時(shí)算法的性能最好，但是當(dāng)群規(guī)模popsize=90，最大迭代次數(shù)T=60時(shí)算法效果已經(jīng)接近最優(yōu)性能，且運(yùn)行時(shí)間少于達(dá)到最優(yōu)性能所花費(fèi)的時(shí)間，所以本文選擇群規(guī)模popsize=90，最大迭代次數(shù)T=60作為PMk09算例的最優(yōu)參數(shù)。

3.2 算法比較及結(jié)果

為了證明本文的IAOA+GNS算法應(yīng)用在偏序柔性車間調(diào)度上的有效性，將本文所采用的方法與文獻(xiàn)[12]和文獻(xiàn)[13]的算法求解效率進(jìn)行對(duì)比，對(duì)比算法的參數(shù)與本文算法的一致。同時(shí)為了驗(yàn)證本文等級(jí)鄰域策略的有效性，選擇與去掉GNS策略采用傳統(tǒng)變鄰域搜索的IAOA+VNS算法進(jìn)行對(duì)比，其中IAOA+VNS算法參數(shù)與IAOA+GNS一致。仿真軟件使用MATLAB 2016a，電腦硬件參數(shù)為：處理器 Intel(R) Core(TM) i5-4210U CPU @ 3.70 GHz，內(nèi)存8 GB。算法各運(yùn)行30次，并使用運(yùn)行結(jié)果中的最小完工時(shí)間Rbest、平均完工時(shí)間Ravr、完工時(shí)間標(biāo)準(zhǔn)差Rσ和算法平均運(yùn)行時(shí)間評(píng)測算法性能。

根據(jù)表4的仿真結(jié)果可以分析出本文的IAOA+GNS算法應(yīng)用在偏序柔性車間調(diào)度具有較好的效果，最小完工時(shí)間和平均完工時(shí)間均優(yōu)于其他優(yōu)化算法，且完工時(shí)間標(biāo)準(zhǔn)差少于其他算法，說明本文算法能夠得到更優(yōu)解，且更穩(wěn)定性。同時(shí)基于IAOA+GNS與IAOA+VNS算法的對(duì)比試驗(yàn)可以說明GNS策略的有效性。

表4 算法效果比較

根據(jù)表5的算法平均運(yùn)行時(shí)間來看，算例PMk05、PMk07、PMk09在本文的運(yùn)行時(shí)間比其他算法運(yùn)行時(shí)間更短，最小化最大完工時(shí)間也更短。在PMk08算例中大部分工序只能在同一臺(tái)機(jī)器上進(jìn)行加工，其適應(yīng)度函數(shù)取決于在此機(jī)器上加工的工序完成時(shí)間，因此無法體現(xiàn)本文算法的優(yōu)越性。在其他算例中本文算法比其他優(yōu)化算法的平均運(yùn)行時(shí)間更長，但是本文算法的運(yùn)行結(jié)果更優(yōu)，且運(yùn)行時(shí)間在可允許范圍之內(nèi)。同時(shí)，IAOA+VNS算法比IAOA+GNS算法運(yùn)行時(shí)間少很多，但是其算法穩(wěn)定性相較于較差，體現(xiàn)了本文改進(jìn)的IAOA+GNS算法在穩(wěn)定性上的優(yōu)勢。綜上所述，本文算法在解決偏序柔性車間調(diào)度問題上相較于現(xiàn)有其他幾個(gè)算法在性能和穩(wěn)定性上更優(yōu)越。

表5 算法平均運(yùn)行時(shí)間

以算例PMk09為例，圖8展示了本文算法對(duì)該算例的調(diào)度甘特圖，從圖中可以看出，其最大完成時(shí)間為307，8號(hào)機(jī)器為瓶頸機(jī)器，該機(jī)器上已無空閑時(shí)間可進(jìn)行調(diào)度，限制了適應(yīng)度函數(shù)的最小值。

圖8 算例PMK09調(diào)度甘特圖

4 結(jié)語

針對(duì)服裝加工行業(yè)中工件具有復(fù)雜工藝流程的情況，本文提出了IAOA+GNS算法求解該類偏序柔性車間調(diào)度問題。算法充分考慮了前繼工序的約束性，首先基于適應(yīng)度和工序完工差異度設(shè)計(jì)出聚類交叉和有效變異策略，避免無效變異的同時(shí)擴(kuò)大了種群探索范圍；然后利用瓶頸機(jī)器和瓶頸工件的關(guān)鍵性進(jìn)行等級(jí)鄰域變異以搜索更優(yōu)解。通過仿真實(shí)驗(yàn)對(duì)比其他算法，驗(yàn)證了IAOA+GNS算法的有效性和穩(wěn)定的求解性能。接下來將下一步的研究重點(diǎn)放到動(dòng)態(tài)調(diào)度偏序柔性車間調(diào)度上。