考慮惡化效應(yīng)的多目標(biāo)非置換流水車間調(diào)度研究

錢偉康，唐紅濤

(武漢理工大學(xué) 機(jī)電工程學(xué)院,湖北 武漢,430070)

傳統(tǒng)的面向制造的生產(chǎn)調(diào)度研究中，通常假定工件的加工時間恒定。在實(shí)際生產(chǎn)中，由于惡化效應(yīng)的影響，工件的加工時間是不確定的。惡化效應(yīng)通常是由機(jī)器高負(fù)荷、作業(yè)延遲等眾多因素引起的，在制造生產(chǎn)中普遍存在[1]。例如，在機(jī)加工過程中，機(jī)床持續(xù)工作致使刀具磨損，從而使加工時間變長；在半導(dǎo)體產(chǎn)業(yè)，處理晶圓的過程中任何延遲都需要花費(fèi)額外的時間來完成[2]。因此，考慮惡化效應(yīng)的調(diào)度問題更貼合實(shí)際，相對于傳統(tǒng)調(diào)度問題也更加難以求解。

流水車間是一類典型的生產(chǎn)車間，廣泛應(yīng)用于電子、機(jī)械、化工等行業(yè)。因此，研究流水車間調(diào)度問題具有重要的工程應(yīng)用價值。黎陽等[3]以最小化最大完工時間為目標(biāo)，提出一種改進(jìn)的模擬退火算法求解大規(guī)模的置換流水車間調(diào)度問題。劉翱等[4]針對零空閑置換流水車間調(diào)度問題，提出一種帶有局部搜索的離散煙花算法。相比于上述流水車間的研究，非置換流水車間調(diào)度(non-permutation flowshop scheduling,NPFS)則允許不同機(jī)器上工件的加工順序改變，是一類松弛置換約束條件的調(diào)度問題。鄭永前等[5]以最小化最大完工時間為目標(biāo)，建立數(shù)學(xué)模型和析取圖模型，構(gòu)造一種列表啟發(fā)式算法。針對傳統(tǒng)調(diào)度算法不能有效利用歷史數(shù)據(jù)進(jìn)行學(xué)習(xí)，肖鵬飛等[6]提出一種基于時序差分法的深度強(qiáng)化學(xué)習(xí)算法求解。盡管諸多學(xué)者對非置換流水車間進(jìn)行了大量研究，然而考慮機(jī)器相關(guān)的惡化效應(yīng)的文獻(xiàn)缺乏。

智能優(yōu)化算法已被證明具有解決組合優(yōu)化問題的能力，且在生產(chǎn)調(diào)度中得到廣泛應(yīng)用。鯨魚優(yōu)化算法[7](whale optimization algorithm,WOA)是一種模擬鯨魚捕食行為的群體智能優(yōu)化算法。該算法原理簡單，參數(shù)設(shè)置少，尋優(yōu)能力強(qiáng)，現(xiàn)已成功應(yīng)用于各種工程領(lǐng)域[8-9]。針對車間調(diào)度問題，閆旭等[10]利用量子計算與優(yōu)化思想提出一種量子鯨魚優(yōu)化算法求解作業(yè)車間調(diào)度問題。欒飛等[11]對低碳車間調(diào)度問題提出一種改進(jìn)的鯨魚優(yōu)化算法，算法設(shè)計了非線性收斂因子和自適應(yīng)慣性權(quán)重系數(shù)來加強(qiáng)算法協(xié)調(diào)全局搜索和局部尋優(yōu)的能力。上述研究多是對單目標(biāo)進(jìn)行優(yōu)化求解，而實(shí)際的生產(chǎn)環(huán)境中常常需要考慮多個目標(biāo)[12-13]，因此改進(jìn)鯨魚優(yōu)化算法求解多目標(biāo)調(diào)度問題具有一定的研究意義。此外，上述研究多是采用“隨機(jī)鍵”的編碼方式，雖然能實(shí)現(xiàn)離散值和連續(xù)值之間的轉(zhuǎn)換，但不能充分利用編碼中的有效信息，也不夠簡單易行。針對WOA算法在迭代后期種群個體均向最優(yōu)個體聚集導(dǎo)致多樣性缺失的不足，相關(guān)文獻(xiàn)多是通過調(diào)整收斂因子以及權(quán)重來改進(jìn)迭代方式，但仍以最優(yōu)個體為導(dǎo)向進(jìn)行尋優(yōu)，不能完全克服迭代后期多樣性缺失的問題。

考慮實(shí)際生產(chǎn)中機(jī)器引起的惡化效應(yīng)，本文構(gòu)建一個多目標(biāo)非置換流水車間調(diào)度(multi-objective nonpermutation flow-shop scheduling,MONFSP) 模型，提出一種兩階段鯨魚優(yōu)化算法(TWOA)進(jìn)行求解。

1 問題描述及模型構(gòu)建

1.1 基于惡化效應(yīng)的調(diào)度問題

Gupta等[14]首次提出具有惡化效應(yīng)的生產(chǎn)調(diào)度問題。此后，諸多學(xué)者對生產(chǎn)調(diào)度領(lǐng)域中惡化效應(yīng)模型進(jìn)行了研究?，F(xiàn)有研究中，線性惡化效應(yīng)模型通常以一個根據(jù)工件的加工位置或開工時間的線性函數(shù)來描述實(shí)際加工時間[15]。然而，此類模型對某些實(shí)際問題并不適用，比如一些工件若不能在指定工期前加工才會發(fā)生惡化[16]。階梯惡化效應(yīng)模型以一個有上限的分段函數(shù)來描述實(shí)際的加工時間[17]，將實(shí)際加工時間分為基本加工時間和懲罰時間，其中基本加工時間是恒定的，懲罰時間是可變的。工件加工時不一定存在懲罰時間，只有滿足一定的條件才會產(chǎn)生懲罰時間。另外，懲罰時間只在某區(qū)間內(nèi)線性增加，達(dá)到臨界值后恒定不變。因此，本文將階梯惡化效應(yīng)模型應(yīng)用到流水車間調(diào)度中。圖1為階梯惡化效應(yīng)的一般模型。其中p為加工時間，t為開工時間。

圖1 階梯惡化效應(yīng)模型Figure 1 Step-deterioration effect model

1.2 問題描述

非置換流水車間調(diào)度問題可描述如下。n個工件在機(jī)器集M={M1,M2,···,Mm}上進(jìn)行加工，每個工件經(jīng)由機(jī)器M1,M2,···，Mm加工，不同機(jī)器上工件的加工順序不相同。任一時刻每臺機(jī)器只能加工一個工件，每個工件只能在一臺機(jī)器上加工。進(jìn)一步考慮惡化效應(yīng)的影響，機(jī)器的累積工作時長超過給定的閾值下限，性能降低導(dǎo)致工件的加工時間增加，若超過給定的閾值上限，工件的加工時間不再增加。

作為生產(chǎn)系統(tǒng)的重要環(huán)節(jié)，最常見的調(diào)度目標(biāo)是完工時間，而隨著日益嚴(yán)格的節(jié)能減排要求，能耗也需要進(jìn)一步統(tǒng)籌考慮。生產(chǎn)過程中，機(jī)器在工作狀態(tài)和空閑狀態(tài)單位時間能耗不一。因此，本文以最大完工時間和總能耗為優(yōu)化目標(biāo)。為了便于研究，相關(guān)假設(shè)如下。

1) 所有工件和機(jī)器在零時刻已準(zhǔn)備就緒；

2) 工件一經(jīng)加工便不可中斷；

3) 每臺機(jī)器前的等待隊列容量足夠大；

4) 忽略運(yùn)輸時間和準(zhǔn)備時間；

5) 不同工件之間相互獨(dú)立。

1.3 多目標(biāo)調(diào)度模型

在不失一般性的前提下，多目標(biāo)優(yōu)化問題可以表示為minf(x)=min[f1(x),f2(x),···,fk(x)]，x=(x1,x2,···,xn)∈Rn。fk(x)是第k個子目標(biāo)函數(shù)，x為解向量，Rn是 決策變量空間。存在解x,y∈Rn，若 ?i，有fi(x)≤fi(y)，且 ?i，使fi(x)＜fi(y)則 稱x支 配y，記為x?y。若解x不 被解空間Rn中任一解所支配，則稱x為非劣解。所有非劣解構(gòu)成的集合稱為Pareto解集，記為 PF。多目標(biāo)優(yōu)化的目標(biāo)為尋找一個均勻分布在Pareto前沿的 PF。

針對上述問題，以最大完工時間和總能耗為目標(biāo)，建立多目標(biāo)優(yōu)化模型。相關(guān)變量的說明如表1 所示。

表1 符號Table 1 Symbols

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

約束條件為

式(1)為總的優(yōu)化目標(biāo)；式(2)表示最大完工時間；式(3)為總能耗；式(4)表示工件的工序約束，即同一工件的各工序之間具有先后順序；式(5)表示機(jī)器在前一個工件的加工完成且下一個工件的上一道工序完成之后，才能進(jìn)行下一個工件的當(dāng)前工序的加工；式(6)表示惡化效應(yīng)下工件的實(shí)際加工時間；式(7)表示工件一旦開始加工則不能被中止。

2 兩階段鯨魚優(yōu)化算法求解調(diào)度模型

2.1 基本鯨魚優(yōu)化算法原理

鯨魚是一種具有智力的哺乳動物。有一類座頭鯨的群體，由于其缺乏可以咀嚼的牙齒，只能捕食成群的小型魚蝦，從而進(jìn)化出一種特殊的覓食行為。它們在收縮魚群包圍圈的同時螺旋上升吐出氣泡，形成一個圓形的氣幕網(wǎng)將分散的魚群聚集起來完成捕食。

根據(jù)座頭鯨的狩獵特點(diǎn)，Mirjalili等[7]于2016年提出一種新型智能優(yōu)化算法——鯨魚優(yōu)化算法。

WOA提供3種個體更新方式。

1) 鯨魚能夠通過回聲定位識別獵物位置并包圍獵物，更新公式如式 (8) 所示。式中，g bestk表示第k代領(lǐng)導(dǎo)鯨魚 (全局最優(yōu))的位置向量；xk和xk+1表示第k代和第k+1代個體X的位置向量。

2) 鯨魚沿著螺旋形路徑向領(lǐng)頭鯨魚游動，并吐出氣泡形成氣幕攻擊獵物，更新公式如式(9)所示。式中，dist為當(dāng)前個體與領(lǐng)導(dǎo)個體之間的歐氏距離；b為限定對數(shù)螺旋形狀的常數(shù)；l為-1到1之間的隨機(jī)數(shù)。

3) 隨機(jī)搜尋。鯨魚個體根據(jù)彼此位置進(jìn)行隨機(jī)搜索，更新公式如式(10)所示。式中，rand為隨機(jī)選擇的鯨魚個體的位置向量；A=2ar-a；C=2r，其中收斂因子a隨迭代次數(shù)從2到0線性下降，r為0～1范圍內(nèi)的隨機(jī)向量。當(dāng)|A|≥1時，算法執(zhí)行第3種更新方式；當(dāng) |A|＜1時，算法隨機(jī)選擇前2種更新方式的一種執(zhí)行。

2.2 兩階段鯨魚優(yōu)化算法

鯨魚個體的位置更新是算法的關(guān)鍵。從第2.1節(jié)可以看出，WOA根據(jù)領(lǐng)導(dǎo)鯨魚進(jìn)行尋優(yōu)，并通過第3種更新方式擴(kuò)大搜索范圍。然而，這種隨機(jī)搜索的方式效率不高，此外，個體向領(lǐng)導(dǎo)鯨魚聚集易導(dǎo)致群體多樣性缺失從而陷入局部最優(yōu)。NPFS是一個離散問題，上述更新方式也不適用于整數(shù)編碼方式。對此，本文的兩階段鯨魚優(yōu)化算法設(shè)計如下。

2.2.1 編碼與種群初始化

種群中的每一個體都是一個解。采用基于工件序列的整數(shù)編碼方式。每個個體都是一個n維向量，每一個向量元素代表一個工件。例如，有6個工件進(jìn)行加工，某個個體為X=[6,3,5,1,2,4]，表明第1個加工的是工件編號為6的工件，而優(yōu)先級最低的4號工件最后加工。上述編碼方式不僅簡單易行，還便于計算個體所對應(yīng)調(diào)度解的目標(biāo)值。

初始種群的質(zhì)量和多樣性會影響算法的求解性能。為提高初始種群的質(zhì)量，本文采用文獻(xiàn)[18]中提出的NEH (Nawaz-Enscore-Ham)啟發(fā)式算法生成一半種群規(guī)模的初始解，具體步驟如下。

步驟1計算各工件從機(jī)器M1到 機(jī)器Mm的總加工時間Ti，按降序排成序列T；

步驟2選取序列T的前2個工件，將其加入加工序列；

步驟3從未加工工件序列中隨機(jī)選取一個工件，并依次插入到當(dāng)前序列的所有可能位置，每插入一個位置計算該位置形成的序列的完工時間，選擇完成時間最小的位置；

步驟4確定一個工件的插入位置，并從未加工工件序列中刪除；

步驟5重復(fù)步驟3～ 4，直至所有工件全部插入完成。

此外，為保證種群的多樣性，仍保留隨機(jī)初始化策略產(chǎn)生剩余50%的種群個體。

2.2.2 解碼與個體評價

解碼是將所有待加工工件分配到各機(jī)器上，形成一個完整的可行調(diào)度方案。本文采用先到先加工(first come first served,FCFS)規(guī)則進(jìn)行解碼。首先，按照編碼確定的工件加工順序在第1臺機(jī)器上進(jìn)行加工，對于第m(m＞1)臺機(jī)器，所有工件按照在前一臺機(jī)器上的完成時間非降序排列依次進(jìn)行加工。若多個工件的完成時間相同,則隨機(jī)確定這些工件的加工順序。

通過上述解碼得到調(diào)度方案后，計算個體的目標(biāo)函數(shù)值。對于多目標(biāo)優(yōu)化問題，不能直接比較目標(biāo)函數(shù)值來評價個體的優(yōu)劣。因此，本文采用文獻(xiàn)[19]中的非支配排序來評價個體的優(yōu)劣。

2.2.3 全局搜索

針對種群個體向領(lǐng)導(dǎo)鯨魚聚集而失去多樣性的問題，對鯨魚個體的行為重新設(shè)計。首先，引入一種引導(dǎo)個體，該個體是指優(yōu)于當(dāng)前個體且距離最近的鯨魚。領(lǐng)導(dǎo)鯨魚和引導(dǎo)個體攜帶的獵物信息均要優(yōu)于當(dāng)前個體。鯨魚個體在搜索時，根據(jù)貪婪準(zhǔn)則執(zhí)行兩階段搜索策略，個體先向引導(dǎo)個體移動，若獲得較差的解則向領(lǐng)導(dǎo)鯨魚移動進(jìn)行捕食。兩階段的具體設(shè)計如下。

階段1鯨魚向引導(dǎo)個體U移動，獲得新解X1。在尋找引導(dǎo)個體時從優(yōu)于當(dāng)前個體中選擇距離最近的。通過漢明距離計算個體間的距離。漢明距離是指兩個序列中位置相同值卻不同的個數(shù)。例如，個體P=[2,1,3,4]和Q=[2,3,1,4]，在位置2和3處值不同，那么它們之間的距離為2。鯨魚進(jìn)行移動時若采用原更新方式會破壞編碼規(guī)則，得到不可行解。對此，本文采取POX交叉算子，將交叉操作看作鯨魚個體的移動，如圖2所示。

圖2 POX交叉Figure 2 POX cross

以X=[2,7,9,8,1,5,4,6,3]，U=[6,7,2,8,4,3,5,9,1]為例。將工件集J={1,2,3,4,5,6,7,8,9}隨機(jī)分為子集JI={1,4,7,8}和JII={2,3,5,6,9}。將X中屬于JI的工件復(fù)制到X1中，保持位置不變；將U中屬于JII的工件依次填入X1的剩余位置。

階段2鯨魚向領(lǐng)導(dǎo)鯨魚L移動進(jìn)行圍捕得到新解X2。領(lǐng)導(dǎo)鯨魚是當(dāng)前全局最優(yōu)個體，而在多目標(biāo)問題中不能保證最優(yōu)解，且為避免個體向同一領(lǐng)導(dǎo)個體聚集而失去多樣性，本文從非劣個體中隨機(jī)選擇個體作為領(lǐng)導(dǎo)鯨魚。此外，領(lǐng)導(dǎo)鯨魚也是種群最靠近獵物的個體，可以將領(lǐng)導(dǎo)鯨魚的位置視為獵物所在的位置，個體向領(lǐng)導(dǎo)鯨魚移動即是對獵物進(jìn)行圍捕。個體圍捕行為設(shè)計如下。

隨機(jī)選取領(lǐng)導(dǎo)鯨魚L的位置編碼的一段序列D，記錄D中工件在當(dāng)前鯨魚編碼中的位置，對序列D中的工件隨機(jī)排序，將排序后的工件依次插入記錄的位置，如圖3所示。

圖3 圍捕行為Figure 3 Predatory behavior

以領(lǐng)導(dǎo)鯨魚L=[2,7,3,8,1,5,4,6]和 當(dāng)前鯨魚X=[6,7,2,8,1,3,4,5]為例。隨機(jī)選取領(lǐng)導(dǎo)鯨魚的編碼中位置3到位置6的序列D=[3,8,1,5]，將其與鯨魚X的編碼進(jìn)行比對，保留不同的工件 [6,7,2,4]，相同的工件則記為θ，將隨機(jī)排序后的序列依次插入。

2.2.4 局部搜索

為提高算法的局部搜索能力，本文引入禁忌搜索機(jī)制。禁忌搜索通過禁忌表封鎖搜索過的區(qū)域，以避免重復(fù)搜索，保證搜索的多樣性。故禁忌表的長度在很大程度上影響搜索效率和解的質(zhì)量。本文采用隨迭代周期動態(tài)變化的禁忌表長度，計算公式如式 (11)所示。其中，w為工序數(shù)，k為當(dāng)前迭代次數(shù)，λ =MaxIt/5，M axIt為最大迭代次數(shù)。

鄰域結(jié)構(gòu)對禁忌搜索的質(zhì)量和執(zhí)行效率也有較大的影響。本文采用3種有效的鄰域結(jié)構(gòu)，即基于NEH的插入鄰域、交換鄰域和逆向鄰域。3種鄰域的具體操作如下。

1) 基于NEH的插入鄰域。在個體序列中隨機(jī)選擇一個位置將其插入到序列的所有可能位置，計算插入后序列的完工時間，獲得所有完整序列中的非劣解。例如，某個體X=[5,1,2,3,4,6]，隨機(jī)選擇位置2，共有6個可能插入的位置，計算這6種插入后的完整序列的目標(biāo)，取其中的非劣解。

2) 交換鄰域。在個體序列中隨機(jī)選擇兩個不同的位置，交換兩個位置上的元素。例如，某個體X=[5,1,2,3,4,6]，隨機(jī)選擇位置2和位置5進(jìn)行交換操作得到個體X=[5,4,2,3,1,6]。

3) 逆向鄰域。在個體序列中隨機(jī)選擇兩個不同的位置，將兩位置間的子序列逆向。例如，某個體X=[5,1,2,3,4,6]，隨機(jī)選擇位置2和位置5進(jìn)行逆向操作得到個體X=[5,4,3,2,1,6]。

局部搜索的具體步驟如下。

步驟1獲取個體解，禁忌表；

步驟2通過鄰域結(jié)構(gòu)生成鄰域解，計算其目標(biāo)值，刪除在禁忌表中存在的鄰域解；

步驟3若有鄰域解支配當(dāng)前解，則更新當(dāng)前解；

步驟4若存在鄰域解與當(dāng)前解不相互支配，則隨機(jī)選擇互不支配的鄰域解；

步驟5若沒有鄰域解支配當(dāng)前解，則保持當(dāng)前解；

步驟6更新禁忌表，若禁忌表已滿則刪除最先加入禁忌表的個體，結(jié)束。

算法整體流程如圖4所示。

圖4 TWOA算法流程圖Figure 4 TWOA flow chart

3 仿真實(shí)驗(yàn)

3.1 測試算例及性能指標(biāo)

參考文獻(xiàn)[1]中的設(shè)計并結(jié)合1.3節(jié)的調(diào)度模型，測試算例設(shè)計如下?？紤]工件數(shù)n={10,20,40,60,80}和機(jī)器數(shù)m={5,8,10}，共15個算例。各工件在各機(jī)器上的加工時間在[0.5 h,3 h]上服從離散均勻分布；各機(jī)器的惡化率在[0.05,0.10]上服從離散均勻分布，閾值下限在[8,21]上服從離散均勻分布，閾值上限在[55,70]上服從離散均勻分布；各機(jī)器處于工作狀態(tài)時，單位能耗在[2 kW,5 kW]上服從離散均勻分布，處于空閑狀態(tài)時單位能耗在[0.5 kW,1 kW]上服從離散均勻分布。

由于是多目標(biāo)算法之間的比較，本文引入3個衡量多目標(biāo)算法性能的指標(biāo)，分別為收斂性指標(biāo)GD[20]、多樣性指標(biāo)Δ[21]和綜合性指標(biāo)I GD[22]。

GD表示非劣解集PF的收斂程度，計算公式如式(12)所示。式中，P F*為 凈最優(yōu)Pareto解集；N為PF中的個體數(shù)；dist(xi,PF*)表 示PF中個體xi與 PF*個體之間的最小歐氏距離。G D值越小，算法收斂性越好。

Δ表示非劣解集PF的分布情況，計算公式如式(13)所示。式中，df和dl是PF*的極端解和PF的邊界解間的歐氏距離；di為PF中第i個體與最近個體之間的歐氏距離；d為di的 平均值。Δ值越小，算法得到的非支配解分布越均勻。

IGD代表算法的綜合性能，計算公式如式(14)所示。式中M為 PF*中 的個體數(shù)；dist(y,PF)表 示 PF*中個體y與PF個體之間的最小歐氏距離。I GD值越小，算法的綜合性能越高。

3.2 對比實(shí)驗(yàn)及結(jié)果分析

為了驗(yàn)證TWOA算法求解上述模型的可行性和有效性，選擇經(jīng)典的遺傳算法(genetic algorithms,GA)、變鄰域搜索算法(variable neighborhood search,VNS)以及文獻(xiàn)[11]提出的IWOA算法進(jìn)行對比實(shí)驗(yàn)研究。其中，GA作為經(jīng)典的智能算法，已成功地用于解決各種調(diào)度問題。VNS具有優(yōu)秀的局部搜索能力。IWOA則是WOA在車間調(diào)度領(lǐng)域的一種改進(jìn)算法。首先，采用正交實(shí)驗(yàn)設(shè)計法對TWOA算法的參數(shù)進(jìn)行優(yōu)化選取，經(jīng)多次組合實(shí)驗(yàn)確定如下參數(shù)。種群大小為80，最大迭代次數(shù)為100。3種對比算法采用隨機(jī)初始化方法，其余參數(shù)均采用來源文獻(xiàn)中的設(shè)置。此外，GA采用POX交叉算子，VNS采用2.2.4節(jié)所描述的3種鄰域結(jié)構(gòu)。

各算法均使用Matlab R2016a編程實(shí)現(xiàn)，并在Intel Core i5，2.60 GHz CPU，4 GB RAM和Windows 7 操作系統(tǒng)的環(huán)境中運(yùn)行。各算例均獨(dú)立運(yùn)行20次，且每次運(yùn)行的終止時間設(shè)為80 s。實(shí)驗(yàn)結(jié)果如表2、3所示?？梢钥闯觯谛∫?guī)模算例上，各算法取得的最優(yōu)值在同一水平，但TWOA的均值更小，這表明其穩(wěn)定性高于其他算法。而隨著規(guī)模的增大，TWOA獲得的解的質(zhì)量全面優(yōu)于另外3種算法。綜合來看，本文提出的算法優(yōu)于其他3種算法。

表2 實(shí)驗(yàn)結(jié)果—最小值Table 2 Experimental results-minimum

3種指標(biāo)的均值統(tǒng)計結(jié)果如圖5～ 7所示?？梢钥闯觯谛∫?guī)模問題上，VNS的性能更優(yōu)。而隨著問題規(guī)模的增大，TWOA的收斂性、多樣性和綜合性能都比其余3種算法好，進(jìn)一步驗(yàn)證了該算法對求解階梯惡化效應(yīng)的車間調(diào)度模型的可行性及有效性。這表明，本文的初始化策略能保證種群多樣性的同時提高個體質(zhì)量，而兩階段搜索策略能更好地避免多樣性缺失，有效的3種鄰域結(jié)構(gòu)幫助個體跳出局部最優(yōu)，且長度動態(tài)變化的禁忌表能提高局部搜索的效率。

圖5 GD對比折線圖Figure 5 The comparison in terms of GD

表3 實(shí)驗(yàn)結(jié)果—均值Table 3 Experimental results-means

4 結(jié)語

基于流水車間，考慮實(shí)際加工中機(jī)器長時間運(yùn)行引起的惡化效應(yīng)，本文構(gòu)建一個以最大完工時間和總能耗為目標(biāo)的階梯惡化效應(yīng)調(diào)度模型。為求解該模型，提出一種兩階段鯨魚優(yōu)化算法(TWOA)。算法采用NEH啟發(fā)式算法提高初始種群的質(zhì)量，在種群尋優(yōu)過程中，設(shè)計一種基于引導(dǎo)個體和領(lǐng)導(dǎo)個體的兩階段全局搜索策略。這種策略能更好地克服個體聚集致使多樣性缺失的缺點(diǎn)。同時，一種禁忌表長度動態(tài)變化的禁忌搜索機(jī)制的嵌入有利于減小算法陷入局部極值的概率。最后，通過對15種不同規(guī)模的測試算例進(jìn)行對比實(shí)驗(yàn)，結(jié)果表明，對于大規(guī)模算例，該算法對求解階梯惡化效應(yīng)調(diào)度模型的性能更優(yōu)。

圖6 Δ對比折線圖Figure 6 The comparison in terms of Δ

圖7 IGD對比折線圖Figure 7 The comparison in terms of IGD