求解多目標(biāo)混合流水車間調(diào)度的改進(jìn)NSGA-Ⅱ

宋存利

(1.大連交通大學(xué) 軟件學(xué)院,遼寧 大連 116052；2.人工智能四川省重點實驗室,四川 自貢 643000)

0 引言

制造業(yè)的發(fā)展在給人們生活帶來極大便利的同時也引發(fā)了新的問題，如環(huán)境污染、全球變暖、能源枯竭等。為實現(xiàn)人類社會的可持續(xù)發(fā)展，國際社會于2015年簽訂《巴黎協(xié)定》，根據(jù)該協(xié)定的內(nèi)在邏輯，在資本市場上，全球投資偏好未來將進(jìn)一步向綠色能源、低碳經(jīng)濟(jì)、環(huán)境治理等領(lǐng)域傾斜。同時，綠色制造已經(jīng)成為“中國制造2025”重大戰(zhàn)略方向之一，綠色調(diào)度則是企業(yè)在現(xiàn)有資源環(huán)境下實現(xiàn)綠色制造的重要一環(huán)。另一方面，競爭的加劇也要求企業(yè)不斷提高生產(chǎn)效率，搶占市場先機(jī)，因此追求最小化最大完工時間也是制造企業(yè)生產(chǎn)的另一重要目標(biāo)。鑒于此，針對以最小化能耗和最小化最大完工時間為目標(biāo)的生產(chǎn)調(diào)度問題展開研究具有重要意義。

針對面向節(jié)能的綠色生產(chǎn)調(diào)度問題，學(xué)者們提出許多優(yōu)化算法。針對柔性作業(yè)車間調(diào)度問題，WU等[1]為了同時最小化最大完工時間、最大能耗和開關(guān)機(jī)次數(shù)，考慮設(shè)備開關(guān)機(jī)能耗、設(shè)備不同轉(zhuǎn)速能耗提出解決該問題的基于非支配排序的遺傳算法；WANG等[2]提出節(jié)約能源的兩階段優(yōu)化方法，該方法考慮了工件加工工藝和能量消耗的不同；孟磊磊等[3]將工藝規(guī)劃和車間調(diào)度兩者有機(jī)集成，提出提高車間生產(chǎn)效率、降低能源消耗的混合整數(shù)規(guī)劃模型。針對混合流水車間的節(jié)能問題，任彩樂等[4]在考慮加工能耗、待機(jī)能耗和開關(guān)機(jī)能耗等的基礎(chǔ)上，提出一種混合整數(shù)線性規(guī)劃模型，并采用候鳥優(yōu)化算法求解問題。

針對以最小化最大加工時間為目標(biāo)的車間調(diào)度文獻(xiàn)較多，其中針對混合流水車間調(diào)度問題(Hybrid Flow Shop Scheduling Problem, HFSP)，宋存利[5]提出一種貪婪遺傳算法；崔琪等[6]提出一種改進(jìn)的混合變鄰域搜索遺傳算法；時維國等[7]提出一種改進(jìn)的灰狼算法；LOW[8]提出模擬退火算法；ESKANDARI等[9]和LI等[10]提出變鄰域算法；王圣堯等[11]提出分布估算算法；PAN等[12]提出離散人工蜂群算法；ZANDIEH等[13]針對帶有序相關(guān)設(shè)置時間的HFSP，提出一種免疫遺傳算法；JAVADIAN等[14]則在考慮工件加工時間需要滯后和序相關(guān)設(shè)置時間等因素的基礎(chǔ)上，提出解決該問題的免疫算法。

近年來，研究多目標(biāo)車間調(diào)度問題的文獻(xiàn)逐漸增多，如文獻(xiàn)[15-27]，其中以最小化完工時間和最小能耗為目標(biāo)的車間調(diào)度文獻(xiàn)有：WU等[21]對柔性作業(yè)車間問題進(jìn)行研究，提出改進(jìn)的帶精英策略的快速非支配排序遺傳算法(fast elitist Non-dominated Sorting Genetic Algorithm, NSGA-Ⅱ)；YANG等[22]對流水車間調(diào)度問題進(jìn)行研究，提出一種多目標(biāo)混合粒子群算法；LU等[23]對置換流水車間調(diào)度問題進(jìn)行研究，提出一種多目標(biāo)回溯算法。而針對加工時間可控的不相關(guān)并行機(jī)調(diào)度問題，DAI等[24]提出一種混合遺傳算法和模擬退火算法的多目標(biāo)優(yōu)化算法；TANG等[25]則對HFSP，在考慮工件動態(tài)達(dá)到的情況下，提出一種改進(jìn)的粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法(稱作NIW-PSO)；LI等[26]提出能源感知的多目標(biāo)優(yōu)化算法(Energy-Aware Multi-objective Optimization Algorithm, EA-MOA)，該算法采用設(shè)備優(yōu)先分配向量和工件加工順序向量兩個向量對問題進(jìn)行編碼，采用所提的多種解碼規(guī)則來解碼染色體，算法在混合多種交叉、變異操作的基礎(chǔ)上，同時對每個染色體輔以深度探索和深度開發(fā)，最大限度尋找問題的Pareto前沿解，并通過實驗證明了算法的有效性。

總之，考慮減少能量消耗的生產(chǎn)調(diào)度多目標(biāo)問題越來越多地被企業(yè)重視，而針對帶有不相關(guān)并行機(jī)的HFSP，以研究最小化總完工時間和最小能耗為目標(biāo)的文獻(xiàn)不是很多。因此，本文在考慮設(shè)備加工能耗、待機(jī)能耗和開關(guān)機(jī)能耗的基礎(chǔ)上，建立了帶有不相關(guān)并行機(jī)HFSP的數(shù)學(xué)模型，提出了解決該問題的改進(jìn)NSGA-Ⅱ，并驗證了算法的有效性。

1 問題描述與建模

帶有不相關(guān)并行機(jī)的HFSP可描述為：N個工件以相同順序流經(jīng)S個加工階段進(jìn)行加工，各加工階段有1到多臺不相關(guān)并行設(shè)備；同一階段的不同設(shè)備均可完成相應(yīng)工件的加工，只是加工同一工件的時間和能耗不同；同一加工階段，工件只有一道工序需要加工；已知工件在每臺設(shè)備上的加工時間、加工單位能耗，以及每臺設(shè)備的單位待機(jī)能耗和開關(guān)機(jī)能耗，確定工件在每個加工階段的加工設(shè)備、加工順序，以及設(shè)備在空閑時刻是關(guān)機(jī)還是待機(jī)等問題，從而使任務(wù)加工完成的總完工時間和能耗最小。為了方便描述問題，定義文中用到的數(shù)學(xué)符號：

N為加工工件總數(shù)；

S為加工階段總數(shù)或工序總數(shù)；

i為工件編號，且i=1,2,…,N；

j為加工階段編號，且j=1,2,…,S；

l為某臺設(shè)備上加工任務(wù)的編號，且0≤l≤N；

mj為每一階段的設(shè)備總數(shù)，且mj≥1；

k為某一階段的加工設(shè)備編號，k=1,2,…,mj；

Ti,j,k為工件i在第j個加工階段第k臺設(shè)備上的加工時間；

PEi,j,k為工件i在第j個加工階段第k臺設(shè)備上的加工單位能耗；

sbj,k為j階段第k臺設(shè)備的單位待機(jī)能耗；

swj,k為j階段第k臺設(shè)備的一次開關(guān)機(jī)能耗；

Xi,j,k表示工件i在階段j的加工是否分配給設(shè)備k，Xi,j,k=1為是，Xi,j,k=0為否；

Pi,j為工件i在階段j的加工結(jié)束時間；

Bj,k,l為j階段第k臺設(shè)備第l個工件的加工開始時間；

Cj,k,l為j階段第k臺設(shè)備第l個工件的加工結(jié)束時間；

Jnumberj,k為j階段第k臺設(shè)備上分配的工件個數(shù)；

Jobj,k,l為j階段第k臺設(shè)備上分配的第l個任務(wù)的工件號，l=1,2,…,Jnumberj,k；

Ftimej,k,l為j階段第k臺設(shè)備上第l個工件與其前驅(qū)工件之間的空閑時間，l=2,…,Jnumberj,k；

switchj,k,l表示j個階段設(shè)備k第l個工件之前的空閑階段是否關(guān)機(jī)重啟，switchj,k,l=1為是，switchj,k,l=0為否；

Cmax為所有工件的最大完成時間；

Energy為加工完所有工件的總能耗；

ProcessE為加工完所有工件的加工總能耗；

StandbyE為加工完所有工件的待機(jī)能耗；

SwitchE為加工完所有工件的開關(guān)機(jī)能耗；

π表示一個調(diào)度方案。

該問題的約束為：第一個加工工件到達(dá)設(shè)備時，設(shè)備均處于關(guān)機(jī)可用狀態(tài)；一個工件在加工過程中不允許其他工件搶占；工件必須嚴(yán)格按照工藝路線加工；同一時刻一個工件最多只能在一臺設(shè)備上加工；一臺設(shè)備同一時刻最多只能加工一個工件；工件可在同一階段的任意一臺設(shè)備上完成該階段工序的加工；不同加工階段間無緩沖限制。根據(jù)上述描述與假設(shè)，建立問題模型如下：

問題的目標(biāo)函數(shù)：

Cmax=min{Cmax(π*)|π*∈π}；

(1)

Energy=min{energy(π*)|π*∈π}。

(2)

對任意一個調(diào)度結(jié)果π，滿足約束：

(3)

Bj,k,l=

(4)

Cj,k,l=Bj,k,l+TJobj,k,l,j,k；

(5)

Pi,j=Cj,k,l=Bj,k,l+Ti,j,k,i=Jobj,k,l；

(6)

Cmax(π)=max{Pi,S|?i∈π中工件序號}；

(7)

Energy=ProcessE+StandbyE+SwitchE；

(8)

(9)

Ftimej,k,l·switchj,k,l；

(10)

(11)

switchj,k,l=

(12)

Ftimej,k,l=Bj,k,l-Cj,k,l-1,

l=2，…，Jnumberj,k；

(13)

Xi,j,k=

(14)

(15)

其中：式(1)為最小化最大完工時間；式(2)為求解最小化能量消耗；式(3)限定了工件i在加工階段j只能分配在該階段其中某一臺設(shè)備上；式(4)計算加工階段j第k臺設(shè)備上第l個工件的開始加工時間；式(5)計算加工階段j第k臺設(shè)備上第l個工件的加工結(jié)束時間；式(6)計算工件i在加工階段j的完工時間；式(7)為一個調(diào)度方案的最大完工時間；式(8)為一個調(diào)度方案的總能量消耗；式(9)為所有工件加工完成的總加工能耗；式(10)計算總待機(jī)能耗；式(11)計算設(shè)備的開關(guān)機(jī)能耗；式(12)為開關(guān)決策變量的決策依據(jù)；式(13)計算加工設(shè)備在加工任務(wù)間隙的空閑時間，式(14)為工件i在加工階段j的加工設(shè)備上的分配情況；式(15)說明j階段所有加工設(shè)備共同分擔(dān)該階段的加工任務(wù)。

2 改進(jìn)的NSGA-Ⅱ

2.1 問題編碼及種群初始化

求解HFSP的智能優(yōu)化算法，目前主要的編碼有：

(1)首階段工件加工順序碼 即n個工件的一個排列，工件在隊列的位置表明工件第一道工序的加工順序，后續(xù)階段則按照工件到達(dá)時間的非降序排列確定工件的加工順序，而工件加工設(shè)備一般用相應(yīng)的啟發(fā)式規(guī)則確定，文獻(xiàn)[4，5-7，9-13]均采用這種編碼方法。實驗證明，這種編碼方法針對單目標(biāo)問題，可在有效縮小解空間規(guī)模的同時最大限度地找到問題的近優(yōu)解，提高算法收斂速度，缺點是不能表達(dá)整個解空間，解碼時需要設(shè)計設(shè)備分配的啟發(fā)式規(guī)則。啟發(fā)式規(guī)則往往帶有一定偏好性，因此只設(shè)計單一的啟發(fā)式規(guī)則不適合求解多目標(biāo)問題，多目標(biāo)文獻(xiàn)一般通過提供多種設(shè)備分配的啟發(fā)式規(guī)則來解決該問題。

(2)矩陣編碼 該編碼方法采用S×N的工件加工順序矩陣和S×N的設(shè)備分配矩陣表達(dá)解，可表達(dá)全部解空間，解碼簡單。缺點是解空間龐大，影響算法搜索效率；同時可能存在一些不可行解，需要在解碼過程中進(jìn)行修正。文獻(xiàn)[25,27]采用這種編碼方法，文獻(xiàn)[26]則采用首階段工件加工順序碼和每階段設(shè)備分配優(yōu)先級向量相結(jié)合的方式，每次分配設(shè)備時，在同等條件下優(yōu)先分配優(yōu)先級高的加工設(shè)備。

以5個工件3個加工階段，前兩個加工階段配有2臺設(shè)備，第3個加工階段有3臺設(shè)備的HFSP為例。染色體{3,2,5,4,1|1,2,2,1,1|2,2,1,1,1|3,2,1,1,2}說明5個工件在第1加工階段的加工順序為3-2-5-4-1。在第1加工階段，工件3-4-1按照順序在設(shè)備1上加工，工件2-5按照順序在設(shè)備2上加工。假如第2加工階段工件的到達(dá)順序為2-3-4-5-1，則工件2-3將在設(shè)備2上按順序加工，工件4-5-1將在設(shè)備1上按順序加工。同理可以確定第3階段的加工順序和設(shè)備分配情況。

鑒于初始種群的優(yōu)劣對算法收斂速度和解的質(zhì)量有一定影響，本文算法初始種群的50%完全隨機(jī)產(chǎn)生；25%先隨機(jī)生成工件加工順序碼，再根據(jù)2.2節(jié)的解碼規(guī)則(2)生成設(shè)備碼；剩余25%先隨機(jī)生成工件加工順序碼，再根據(jù)2.2節(jié)的解碼規(guī)則(3)生成設(shè)備碼。

2.2 解碼方案

為了最大限度地確保算法找到Pareto前沿解，從而有效引導(dǎo)算法搜索空間，本文提出3種解碼方案，其中工件的加工順序均采用工件順序碼確定第1階段工件的加工順序，其他階段采用工件先到達(dá)先分配方案，將工件盡可能早地安排在相關(guān)設(shè)備加工。不同點在于加工設(shè)備的選擇方案不同，具體規(guī)則如下：

(1)基于染色體的設(shè)備分配方案(AllocateMachine according Chromosome, AMC) 該解碼方法完全按照染色體后S×N個向量確定對應(yīng)工件的加工設(shè)備，沒有偏向性，可以確保多目標(biāo)的求解。

(2)最早結(jié)束優(yōu)先分配方案(First end First allocation, FF)[5]該方案不考慮染色體中的設(shè)備分配碼，首階段按照工件順序碼確定加工順序，其他階段根據(jù)先到達(dá)先分配原則安排工件加工，加工設(shè)備的分配則優(yōu)先選擇能最早完成工件加工的設(shè)備，如果兩個設(shè)備能以相同時間完成加工，則優(yōu)先選擇加工能耗較小的設(shè)備，該解碼方案優(yōu)先從完工時間的角度進(jìn)行解碼，對最小化最大完工時間這一目標(biāo)具有一定導(dǎo)向性。

(3)基于最小加工能耗的分配方案(AllocateMachine based minimal Energy consumption，AME) 與FF類似，該解碼方案只是分配加工設(shè)備時優(yōu)先選擇加工能耗最小的設(shè)備。當(dāng)同時有兩臺以上設(shè)備以相同的加工能耗完成工件的加工任務(wù)時，優(yōu)先選擇最早完工的加工設(shè)備，該方案對最小能耗這一目標(biāo)具有一定導(dǎo)向性。

為不影響后代的操作，在采用AME和FF解碼的過程中需同時在染色體中記錄設(shè)備分配方案，以保證染色體的完整性，這種解碼相當(dāng)于對原有染色體進(jìn)行了導(dǎo)向性修改。

2.3 解碼結(jié)果的移動策略

2.2節(jié)的解碼策略確定了每階段工件的加工設(shè)備、加工順序及工件的開完工時間，解碼時未考慮設(shè)備的待機(jī)能耗和開關(guān)機(jī)能耗。對于一個調(diào)度方案，設(shè)備空閑時間的狀態(tài)是待機(jī)還是關(guān)機(jī)重啟可根據(jù)式(12)進(jìn)行決策?？紤]工件加工過程中，除了關(guān)鍵路徑上的工件開完工時間沒有浮動時間外，非關(guān)鍵路徑上的工件加工總有一定的浮動時間，因此從節(jié)約能量的角度提出一種移動策略，該策略在不改變加工任務(wù)總完工時間的情況下，將工件在其浮動時間內(nèi)移動來減少設(shè)備關(guān)機(jī)重啟次數(shù)、延長關(guān)機(jī)重啟間隔或減少待機(jī)時長，以達(dá)到減少能耗的目的。該策略分兩階段進(jìn)行：

(1)右移策略 該策略從最后一個階段依次向前遞推到第2階段，將每臺設(shè)備上的工件右移。方法是對一具體設(shè)備，從該設(shè)備上倒數(shù)第2個加工工件開始依次盡最大努力右移，具體移動距離則根據(jù)式(16)計算。假設(shè)當(dāng)前要移動j階段設(shè)備k上的第l個加工工件，該工件的右移時間距離設(shè)為dj,k,l，則

dj,k,l=

(16)

通過右移操作，每臺設(shè)備的加工任務(wù)除最后一個加工任務(wù)外，其他任務(wù)盡量最晚開工，從而在一定程度縮短設(shè)備待機(jī)時長或減少關(guān)機(jī)重啟次數(shù)或延長某次開關(guān)間隔，達(dá)到節(jié)約能耗的目的。

(2)左移策略 右移將每個工件在設(shè)備上的加工盡量推后，左移的目的則是在保證每臺設(shè)備首工件開工時間和末工件完工時間不變的情況下，盡量利用加工設(shè)備上中間非關(guān)鍵工件的浮動時間來進(jìn)一步減少能耗。具體是從第2加工階段依次到倒數(shù)第2階段，對加工任務(wù)數(shù)大于2的設(shè)備上的中間工件塊有條件左移，達(dá)到延長設(shè)備關(guān)機(jī)重啟間隔、縮短待機(jī)或完全擠掉待機(jī)時間的效果。左移策略以塊為單位，假設(shè)當(dāng)前要移動j階段設(shè)備k上的某塊，該塊的最后一個工件為該設(shè)備上的第l個工件，該塊長度為block。設(shè)塊的開始加工時間與其前驅(qū)工件的完工時間間隔為A1，塊可左移的最大時間間隔為A2，塊的加工結(jié)束時間與其后繼工件的開始加工時間間隔為BD，設(shè)備開關(guān)的最小時間間隔為LT，則有：

(17)

(18)

(19)

LT=swj,k/sbj,k。

(20)

當(dāng)A2=0時，該塊不能左移；當(dāng)A2>0時，根據(jù)以下規(guī)則判斷是否左移當(dāng)前塊：

(1)當(dāng)A1

(2)當(dāng)A1>LT且BD

(3)當(dāng)A1>LT且BD>LT時，塊前和塊后的設(shè)備空閑時間均為關(guān)機(jī)重啟，將塊左移A2個時間單位，達(dá)到延長塊后關(guān)機(jī)重啟時間，縮短塊前空閑時間，甚至擠掉空閑時間的效果來節(jié)能。

圖1所示為一個左移決策案例，在第2加工階段，以工件4和工件11組成塊為例。該塊的塊長block=2，變量BD等于工件18的開工時間減去工件11的完工時間，即BD=2；變量A1等于工件4的開工時間減去工件7的完工時間，即A1=18。根據(jù)式(18)，變量A2則是A1、塊內(nèi)工件4的開始加工時間減去其在第1階段完工時間的值12，以及塊內(nèi)工件11的開始加工時間減去其在第1階段完工時間的值1，這3個數(shù)值的最小值，因此A2=1。變量LT根據(jù)具體案例確定為LT=8，根據(jù)規(guī)則(2)判斷，該塊不左移。

2.4 交叉算子

因為染色體編碼由首階段工件加工順序碼和全部階段的設(shè)備分配碼兩部分組成，所以兩部分的交叉操作規(guī)則不同。具體方法為：隨機(jī)生成兩個1～(S+1)×N之間的隨機(jī)整數(shù)h1和h2，若h1，h2≤N，則交叉操作僅發(fā)生在工件順序碼上，這部分交叉操作任選文獻(xiàn)[5]的3種交叉算子之一進(jìn)行，而設(shè)備碼部分則原樣遺傳給子代染色體；若h1，h2>N，則交叉操作僅發(fā)生在設(shè)備碼部分，直接交換兩個父代設(shè)備碼中兩隨機(jī)數(shù)之間的基因?qū)?，子代其余位置基因原樣拷貝父代對?yīng)位置的基因即可；若h1N，則工件碼部分和設(shè)備碼部分同時發(fā)生交叉操作，規(guī)則是工件碼部分采用工件碼的交叉規(guī)則，設(shè)備碼采用設(shè)備碼的交叉規(guī)則，具體交叉操作偽代碼如下：

void crossOperator(染色體p1,染色體p2)

{令h1=int(rand()×(s+1)×n)+1;

令h2=int(rand()×(s+1)×n)+1;

將較小的整數(shù)放入h1，較大的整數(shù)放入h2;

if(h1>N)

執(zhí)行染色體p1和p2對應(yīng)設(shè)備碼的交叉操作規(guī)則，產(chǎn)生兩個子代染色體Child1和Child2;

elseif(h2<=N)

執(zhí)行染色體p1和p2工件碼的交叉操作規(guī)則，產(chǎn)生兩個子代染色體Child1和Child2;

else

{將兩父代染色體p1和p2工件碼從h1到N位置進(jìn)行交叉操作，

產(chǎn)生子代Child1和Child2的工件加工順序碼；

將兩父代染色體p1和p2的設(shè)備碼從N+1到h2位置進(jìn)行交叉操作，

產(chǎn)生兩子代Child1和Child2的設(shè)備分配碼；

}

輸出兩子代染色體；

}

2.5 貪婪變異算子

本文中貪婪變異的目的是增加解的多樣性和增強(qiáng)算法的鄰域搜索能力。具體的染色體變異操作也有兩種策略，對工件順序碼的變異方法任選文獻(xiàn)[5]的3種變異算子之一進(jìn)行。針對設(shè)備分配碼的變異操作，設(shè)計了兩種不同的變異方法。一種是對每一個設(shè)備基因碼采用變異概率30%進(jìn)行變異操作；另一種是隨機(jī)生成兩個隨機(jī)數(shù)，將這兩個隨機(jī)數(shù)之間的設(shè)備碼進(jìn)行變異，具體是隨機(jī)選擇該階段一臺不同的加工設(shè)備號替換原有加工設(shè)備。

貪戀變異操作的思想是對選擇發(fā)生變異的染色體，最多循環(huán)50次令其發(fā)生變異，若某次變異中生成的染色體適應(yīng)值對其原有染色體的適應(yīng)值形成了支配關(guān)系，則用變異后的染色體替換原有染色體，結(jié)束循環(huán)。若變異后染色體和原染色體互不支配，則將變異后的染色體與種群中其他染色體對比，觀察有無染色體對其形成支配關(guān)系，有則直接放棄，繼續(xù)變異操作；否則將其放入孩子染色體集合中，等待選擇操作，結(jié)束變異。偽代碼如下：

void greedymutate(染色體p)

{ int i=0;

定義染色體變量pnew;

while(i<=50)

{ p發(fā)生變異操作產(chǎn)生新染色體pnew;

解碼新染色體pnew;

if(pnew支配p)

{ p=pnew;

break; }

elseif(pnew和p互不支配)

{if(pnew支配種群中某個染色體嗎？)

{替代被它支配的染色體；

break;}

elseif(種群中染色體支配pnew嗎？)

{放棄pnew;}

else{放入孩子群體中，等待選擇；break;}

}

i=i+1;

}

}

2.6 改進(jìn)選擇算子

為了保證不丟失優(yōu)良個體，同時避免早熟收斂，保持種群的多樣性，本文提出一種改進(jìn)的精英保留選擇算子，步驟如下：

步驟1初始化下代種群NextPop為空集，將父代種群fatherPop和遺傳操作產(chǎn)生的子代種群childPop合并為一個集合R0。

步驟2計算集合R0中每個染色體的非支配排序等級，非支配等級為0的染色體進(jìn)入集合R1，非支配等級為1的染色體進(jìn)入R2集合，以此類推，直到R0中的每個染色體都進(jìn)入一個相應(yīng)等級的集合中。

步驟3對步驟2得到的集合Ri(i≥1)按順序執(zhí)行如下操作，直至得到下一代指定規(guī)模的種群：

(1)計算當(dāng)前集合中每個染色體的擁擠度距離，按照該距離由大到小對染色體進(jìn)行排序。

(2)對于擁擠度為0的染色體，說明在該集合中至少有3個適應(yīng)值與其相同的染色體，以90%的概率從集合中刪除這樣的染色體，該過程稱為除冗余。

(3)計算該集合中剩余染色體的個數(shù)，若將其全部并入集合NextPop時不超出種群規(guī)模，則將該集合中的所有染色體直接并入NextPop，對下一個等級的染色體集合重復(fù)步驟3；若將某個非支配排序等級的集合并入NextPop時超出種群規(guī)模，則根據(jù)該集合中每個染色體的擁擠度距離，采用輪盤賭策略選擇進(jìn)入集合NextPop的染色體，直到NextPop達(dá)到種群規(guī)模，結(jié)束步驟3。

步驟4如果執(zhí)行步驟3時集合NextPop中的染色體沒有達(dá)到種群規(guī)模，則隨機(jī)生成新的染色體進(jìn)入NextPop集合，直至達(dá)到相應(yīng)的種群規(guī)模。

具體偽代碼如下：

void choiceNext()

{ 令NextPop=?；Pnumber=0;

令R=fatherPop+childPop;

非支配排序R，將其劃分進(jìn)不同支配等級的集合S[0]，S[1],…中,令Pnumber為集合個數(shù);

令rank=0;

While(rank<=Pnumber)

{計算集合S[rank]中染色體的擁擠度;

根據(jù)擁擠度由大到小排序S[rank]中的染色體;

令number為S[rank]集合中染色體的個數(shù);

while(S[rank][number]的擁擠度為0？)//循環(huán)刪除冗余染色體

{

if(rand()<0.9)

{刪除染色體S[rank][number];}

number=number-1; //下一染色體位置

}

N1= S[rank]//為剩余染色體個數(shù)

If(Pnumber+N1<=Psize)//染色體進(jìn)入下一代種群

{ NextPop= NextPop+ S[rank];//兩個集合并運(yùn)算

Pnumber=Pnumber+N1;

rank=rank+1;

}

else

{以輪盤賭選擇策略選擇放入S[rank]中的Psize-Pnumber個染色體進(jìn)入NextPop ;

break;}

}

While(Pnumber

{ Prand=init();//隨機(jī)算法產(chǎn)生一個染色體；

Prand放入NextPop;

}

}

3 實驗分析

本文算法采用VC++6.0編寫，計算機(jī)配置為：操作系統(tǒng)采用WIN 10，內(nèi)存為16 GB，主頻為1.99 GHz。本文案例均采用j*c*a*命名，其中*表示一個整型數(shù)字，例如案例j15c5a1表示15個加工工件在加工階段為5的車間加工，a1為該類案例的第一個案例。所有加工數(shù)據(jù)隨機(jī)產(chǎn)生，其中工件的加工時間在[10～30]之間，每階段加工設(shè)備在[1～3]之間，設(shè)備加工單位能耗數(shù)據(jù)在[5～10]之間，設(shè)備單位待機(jī)能耗在[1～5]之間，單次開關(guān)機(jī)能耗在[20～30]之間。案例規(guī)模有15工件、20工件和30工件，其中案例j20c5a1～j20c5a5既有加工階段只有1臺加工設(shè)備的情況，又有加工階段有2～3臺設(shè)備的情況。其他案例每階段設(shè)備數(shù)至少在2臺以上。

本文改進(jìn)算法命名為NSGAⅡ_3，為了驗證其有效性，設(shè)計了3種比較算法：①基本NSGAⅡ_1算法(傳統(tǒng)NSGAⅡ)，該算法采用AMC的解碼方案，選擇操作采用傳統(tǒng)的精英保留策略；②NSGAⅡ_2，該算法解碼采用3種解碼方案的混合解碼方法，并采用貪婪變異操作，其他設(shè)計同NSGAⅡ_1；③NSGAⅡ_3，該算法在NSGAⅡ_2基礎(chǔ)上，選擇操作采用2.6節(jié)提出的改進(jìn)的選擇算子。

3.1 移動策略的有效性驗證

為了驗證本文所提移動策略的有效性，以案例j20c5a2為例，該案例的設(shè)備配置特點為1-2-3-1-2。圖2所示為該案例的3種調(diào)度結(jié)果，其中橫坐標(biāo)為完工時間，縱坐標(biāo)為加工設(shè)備。其某個調(diào)度結(jié)果甘特圖如圖2a所示。為了使不同加工階段調(diào)度結(jié)果看起來更加明顯，相鄰階段采用不同灰度間隔。圖2a為解碼結(jié)果，其完工時間為293，能量消耗為9 542。圖2b為對圖2a的調(diào)度結(jié)果執(zhí)行右移之后的結(jié)果，如兩圖虛線框框出部分所示。從圖2b可見，后兩個階段加工設(shè)備上的中間空閑時間被完全擠壓掉，第3和第2加工階段的部分設(shè)備待機(jī)時間減少或完全被擠壓掉，部分設(shè)備的開關(guān)時間被擠壓掉或縮短為待機(jī)狀態(tài)。圖2b調(diào)度能耗減少為9 294，相比圖2a共降低了248個能耗，而完工時間不變。圖2c是針對圖2b的調(diào)度結(jié)果左移之后的結(jié)果，如圖2b圖和圖2c深色虛線框出部分所示。顯然，圖2c調(diào)度的總完工時間不變，但加工能耗為9 278，相比圖2b節(jié)約16個能耗。通過本文先右移再左移的移動策略，案例j20c5a2的調(diào)度結(jié)果共降低264個能耗，證明了本文調(diào)度調(diào)整方案的有效性，因此所提算法均采用該策略對調(diào)度方案進(jìn)行調(diào)整。

表1統(tǒng)計了本文20個案例的Pareto前沿解在右移后能量消耗相對原始調(diào)度的平均能耗節(jié)約率(用RR表示)，以及左移后相對右移結(jié)果能耗的平均節(jié)約率(用LR表示)。由表1可見，相對原始調(diào)度，右移策略能夠100%節(jié)約能耗。本文20個案例右移后再左移，其中有7個案例在左移后能耗不變化，剩余13個案例在左移后能節(jié)約一定能耗，進(jìn)一步證明了移動策略的有效性。

表1 移動策略實現(xiàn)的能源節(jié)約率

3.2 3種解碼算法混合比例校驗

在NSGAⅡ_2中，采用3種解碼方案的混合策略，為了驗證不同解碼方案對算法的影響，以及解碼策略在該算法中的設(shè)置比例，給出3種解碼策略的6種不同設(shè)置比例，具體如表2所示。其中編號1，2，3為3種解碼算法的混合，編號4，5，6只采用其中一種解碼算法，編號4采用AMC解碼，編號5采用FF解碼，編號6采用AME解碼。從案例j15c5a1～j15c5a5，j20c5a1～j20c5a5，j20c5a6～j20c5a10的每組案例中隨機(jī)選其中兩組，經(jīng)過正交實驗確定算法種群規(guī)模、迭代次數(shù)、交叉概率和變異概率分別為40，2 000，0.75，1。每個算例運(yùn)行1次，利用相關(guān)案例的Pareto前沿解分布圖展示結(jié)果，具體如圖3所示，其中橫坐標(biāo)makespan表示最大完工時間。

表2 各種解碼算法的分配比例

觀察圖3中6個案例的Pareto前沿解分布圖，編號4對應(yīng)的AMC解碼實驗結(jié)果，其前5個案例Pareto前沿解的分布性較好，但收斂性差，只有圖3f的收斂性稍好一些；編號5采用FF解碼，其導(dǎo)向性是最小化最大完工時間，6個案例中，圖3a、圖3b、圖3e和圖3f的實驗結(jié)果較靠近Pareto前沿解，但主要集中在完工時間較小、能耗較大的區(qū)間，證明單獨(dú)采用FF解碼不太合適求解多目標(biāo)，解的分布性較差；編號6采用AME解碼，該解碼以最小能耗為準(zhǔn)則選擇設(shè)備分配，6個案例中，圖3a、圖3b、圖3e和圖3f的Pareto前沿解集中在能量消耗較少但完工時間較大的區(qū)間，同樣說明單獨(dú)的導(dǎo)向性明顯的AME解碼算法同樣不適合多目標(biāo)問題。編號1，2，3均采用3種解碼算法混合策略，只是比例不同。編號1解碼策略中具有導(dǎo)向性的解碼規(guī)則FF和AME占比較高，均達(dá)到25%，從Pareto前沿解的分布看，解的分布大多集中在兩端，分布不均。具體原因是由于受導(dǎo)向性解碼規(guī)則FF和AME指引過于強(qiáng)烈，從而使算法結(jié)果集中在兩頭，中間沒有或很少，具體如圖3a、圖3b、圖3e和圖3f所示；從采用編號2的解碼策略的實驗結(jié)果看，6個案例的Pareto前沿解的收斂性和分布性均比編號1的實驗結(jié)果好；從采用編號3的解碼策略的實驗結(jié)果看，圖3的6個實驗案例中，除了圖3e的分布性相對差一些外，其他5案例的實驗結(jié)果無論解的分布性還是收斂性，均好于采用解碼策略1～6的實驗結(jié)果。因此，本文的混合解碼比例將采用編號3的設(shè)置。

3.3 混合解碼算法及選擇算子有效性驗證

為了驗證本文混合解碼策略的有效性，將NSGAⅡ_1和NSGAⅡ_2進(jìn)行實驗對比；為了驗證改進(jìn)的選擇策略的有效性，將NSGAⅡ_3和NSGAⅡ_2進(jìn)行驗證對比；最后對比NSGAⅡ_3和NSGAⅡ_1的實驗結(jié)果，以證明本文算法的有效性。3種算法種群規(guī)模、交叉變異概率的設(shè)置同3.2節(jié)，NSGAⅡ_2和NSGAⅡ_3的解碼算法比例設(shè)置采用3.2節(jié)的實驗結(jié)論(0.9，0.05，0.05)，采用中等規(guī)模的j20c5a5～j20c5a10案例進(jìn)行實驗。圖4所示為6個案例相應(yīng)算法的Pareto前沿解的分布。表3所示為圖4中3種算法針對每個案例的Pareto前沿解中兩個端點的結(jié)果，即一組是最小完工時間和能耗，一組是最小能耗和完工時間。其中：cmin為實驗的最小完工時間，e為對應(yīng)的能耗，emin為實驗結(jié)果的最小能耗，c為其對應(yīng)的完工時間，加粗的數(shù)據(jù)為前沿解在不同方面的最好解。

首先，對比NSGAⅡ_1與NSGAⅡ_2的實驗結(jié)果，驗證混合解碼策略對多目標(biāo)問題的有效性。從圖4中6個案例的Pareto前沿解的分布看，在案例j20c5a7上，NSGAⅡ_1的Pareto前沿解的分布性和收斂性優(yōu)于NSGAⅡ_2；對于案例j20c5a5，j20c5a8，j20c5a9，NSGAⅡ_2的Pareto前沿解的分布性和收斂性優(yōu)于NSGAⅡ_1；在案例j20c5a6和j20c5a10上，兩種算法的前沿解形成了交叉。該實驗說明，采用混合解碼算法的NSGAⅡ_2與單獨(dú)采用AMC解碼的NSGAⅡ_1相比，具有一定優(yōu)勢，表3的統(tǒng)計結(jié)果也支持了該結(jié)論。

表3 6個案例的實驗結(jié)果

其次，比較NSGAⅡ_3和NSGAⅡ_2，驗證2.6節(jié)所提改進(jìn)選擇算子的有效性。在圖4中，NSGAⅡ_3在6個案例上實驗所得的Pareto前沿解，無論收斂性還是多樣性均優(yōu)于NSGAⅡ_2，說明了本文所提改進(jìn)選擇算子的有效性，其在一定程度上能夠保證種群的多樣性，避免算法早熟。從表3可見，在6個案例的12組解中，NSGAⅡ_3取得其中10個較好解，占83.3%，而NSGAⅡ_2僅在案例J20c5a10和J20c5a7上關(guān)于(c,emin)取得解的質(zhì)量好于NSGAⅡ_3，僅占到16.7%。進(jìn)一步說明了本文改進(jìn)選擇算子的有效性。

對比NSGAⅡ_3與NAGAⅡ_1，NSGAⅡ_3在6個案例上實驗的Parteto前沿解的分布性和收斂性均優(yōu)于NAGAⅡ_1，說明在將3種解碼策略有機(jī)混合的同時結(jié)合保證種群多樣性的選擇算子對NSGAⅡ_3產(chǎn)生了積極的影響。一方面，帶有引導(dǎo)性的解碼算法FF和AME能夠有效引導(dǎo)算法搜索解空間；另一方面，改進(jìn)的選擇算子又可以根據(jù)擁擠度以較大概率淘汰某一區(qū)間過度密集的解，從而有效提高種群多樣性，避免算法陷入局部最優(yōu)。這為以后設(shè)計多目標(biāo)算法提出了新的思路。

3.4 與已有算法的實驗對比

將本文改進(jìn)的NSGAⅡ_3與一種改進(jìn)的粒子群優(yōu)化算法NIW-PSO[25]和EA-MOA[26]在3組案例j15c5a1～j15c5a5，j20c5a1～j20c5a10，j30c5a1～j30c5a5上進(jìn)行實驗對比，公平起見，將限制算法迭代次數(shù)改為每種算法的運(yùn)行時間均不超過5 min，并將本文所提移動策略應(yīng)用于每個算法，NIW-PSO和EA-MOA的其他參數(shù)均遵循原有算法設(shè)置。將3種算法針對每個案例所求的Pareto前沿解合并進(jìn)行非支配排序，求出被支配等級為0的非支配解，記作理想Pareto前沿解PF*，分別統(tǒng)計3種算法的Pareto前沿解出現(xiàn)在PF*中的個數(shù)，具體統(tǒng)計結(jié)果如表4所示。

表4 3種算法的實驗結(jié)果統(tǒng)計

從表4可見，15個案例中，本文算法在14個案例上求解的Pareto前沿解出現(xiàn)在PF*中的個數(shù)均大于其他兩種算法，其中在算例j15c5a4，J30c5a3，J30c5a5三個案例上，本文算法NSGAⅡ_3求出的前沿解和PF*完全相同。算法EA-MOA在案例J20c5a6上的求解結(jié)果較好，算法NIW-PSO的表現(xiàn)最差，說明了本文算法的有效性。

4 結(jié)束語

本文以最小化最大完工時間和最小能耗為目標(biāo)對HFSP進(jìn)行研究，提出該問題的混合整數(shù)規(guī)劃模型，在此基礎(chǔ)上提出解決該問題的一種改進(jìn)的NSGAⅡ。首先，該算法染色體編碼能夠保證算法在問題的整個解空間中搜索Pareto前沿解集，有效避免了針對HFSP的常用染色體編碼存在的弊端?；旌辖獯a策略將帶有明顯偏向性的解碼算法應(yīng)用于多目標(biāo)問題，從而有效引導(dǎo)算法種群進(jìn)化，實驗證明了該策略的有效性，為多目標(biāo)問題的求解提供了一條新的設(shè)計思路。為了避免帶有導(dǎo)向性的解碼策略使算法陷入局部最優(yōu)，出現(xiàn)早熟問題，提出一種改進(jìn)的選擇算子，該算子在采用精英保留策略的基礎(chǔ)上，大概率淘汰擁擠度為0的染色體，從而保證Pareto前沿解的收斂性和分布性，最后通過實驗驗證了本文所提算法的有效性。

未來的研究方向為：①對多約束車間調(diào)度問題進(jìn)一步展開研究，以提升研究成果的應(yīng)用價值；②進(jìn)一步研究多目標(biāo)車間調(diào)度的解決方法。