胡金昌，劉紫薇，馬文凱，吳耀華

(山東大學(xué) 控制科學(xué)與工程學(xué)院，山東 濟(jì)南 250061)

0 引言

學(xué)習(xí)效應(yīng)[1]是生產(chǎn)中常見的現(xiàn)象，只要有人工參與的生產(chǎn)活動幾乎都存在學(xué)習(xí)效應(yīng)。隨著對工藝熟悉程度的增加，工人的操作越來越熟練，操作時間隨之減少。半自動機(jī)床只需人工上料和下料操作便可以自動化加工，無需看守，因此管理者通常安排一個工人監(jiān)管多臺機(jī)床。這樣的加工模式提高了工人操作機(jī)器的頻率，從而增大了學(xué)習(xí)效應(yīng)的影響。Biskup[2]和Cheng等[3]最早將學(xué)習(xí)效應(yīng)應(yīng)用于排序問題；Kuo等[4]提出依賴加工時間和的學(xué)習(xí)效應(yīng)模型，即工人實(shí)踐的時間越長，表現(xiàn)越好，該模型被大量應(yīng)用于單機(jī)、平行機(jī)、流水車間等調(diào)度問題；Wu等[5]研究了基于依賴加工時間和的學(xué)習(xí)效應(yīng)的多機(jī)訂單調(diào)度問題，以最小化誤工時間；Wu等[6]在單機(jī)調(diào)度問題中考慮截斷的基于依賴加工時間和的學(xué)習(xí)效應(yīng)與基于前期工件加工順序的配送時間；Rudek[7]研究了平行機(jī)調(diào)度問題，以最小化最大完工時間，其工件加工時間應(yīng)用一般性基于加工時間和的數(shù)學(xué)模型，該模型適用于學(xué)習(xí)效應(yīng)和衰退效應(yīng)；Zou等[8]研究了兩階段3臺機(jī)器的裝配車間調(diào)度問題，不同機(jī)器的工件加工時間受依賴不同機(jī)器加工時間和的學(xué)習(xí)效應(yīng)的影響；Mousavi等[9]分析了安裝時間和加工時間均受學(xué)習(xí)效應(yīng)影響的流水車間調(diào)度模型；Tayebi Araghi等[10]在作業(yè)車間調(diào)度問題研究中考慮了受學(xué)習(xí)效應(yīng)影響的安裝時間和受惡化效應(yīng)影響的工件加工時間；Heizer等[11]指出不同產(chǎn)品的學(xué)習(xí)率在70%～90%之間，這意味著后一個生產(chǎn)單位的加工時間是前一個的70%～90%，同種工件的加工時間因?yàn)轫樞虿煌嬖诿黠@差異，所以考慮學(xué)習(xí)效應(yīng)的調(diào)度系統(tǒng)必然會提高調(diào)度的準(zhǔn)確性。

因?yàn)闉閱稳瞬僮鞫嗯_機(jī)器，工人行走于各個機(jī)器之間的耗時較長，如果工人頻繁、反復(fù)穿梭于各個機(jī)器間，會影響其熱情和工作滿意度，所以考慮工人的行走路徑也具有一定必要性。現(xiàn)有車間調(diào)度研究考慮了最短行走路徑因素，例如Nip等[12]研究了流水線車間調(diào)度和最短路徑組合問題，目的是最小化行走路徑和加工總時間，并提出了近似算法；Range等[13]解決了考慮行走路徑的多分類多機(jī)器且機(jī)器加工能力有限的車間調(diào)度問題；劉凱等[14]討論了工人作業(yè)時間隨機(jī)分布且與工人行走路徑時間相互獨(dú)立的U型線平衡問題。與工人行走類似，部分研究人員考慮了工件的運(yùn)輸時間，Zhang等[15]提出改進(jìn)的遺傳算法解決考慮機(jī)器之間工件運(yùn)輸時間的柔性作業(yè)車間調(diào)度問題；Karimi等[16]針對考慮運(yùn)輸時間的柔性作業(yè)車間調(diào)度模型，構(gòu)建了兩種混合整數(shù)規(guī)劃模型，提出混合帝國主義競爭算法解決大規(guī)模問題；Jiang等[17]研究了一種由輸送帶運(yùn)輸?shù)目紤]運(yùn)輸時間的流水車間調(diào)度問題；軒華等[18]研究了可重入混合流水車間調(diào)度，運(yùn)輸時間指工件不同加工階段之間的運(yùn)輸時間。上述研究中的運(yùn)輸指同一個工件的不同工序在不同機(jī)器之間的運(yùn)輸，與此不同，本文單人作業(yè)場景的運(yùn)輸時間為由加工工件變化帶來的加工機(jī)器轉(zhuǎn)換的耗時，這使行走時間和最大完工時間成為一對相悖的目標(biāo)。例如，工人如果選擇加工完一臺機(jī)器的所有工件后再加工另一臺機(jī)器的工件，則行走時間較短，但等待機(jī)器的時間較長，其他機(jī)器的利用率較低，最大完工時間增加。因此，有必要在調(diào)度時平衡工人行走時間和加工效率的關(guān)系。

由于考慮了學(xué)習(xí)效應(yīng)，本文目標(biāo)值的計算復(fù)雜度會增加。計算目標(biāo)值時間的增加影響了算法迭代次數(shù)，導(dǎo)致求解效果下降，因此提高算法的鄰域搜索能力成為求解本文問題的重點(diǎn)。另外，考慮學(xué)習(xí)效應(yīng)和運(yùn)輸時間的單人單工序作業(yè)車間的多目標(biāo)調(diào)度問題，目前尚未有合適的算法直接求解。作為解決多目標(biāo)問題的經(jīng)典啟發(fā)式算法，帶精英策略的快速非支配排序遺傳算法(fast elitist Non-dominated Sorting Genetic Algorithm，NSGA-Ⅱ)的結(jié)構(gòu)簡單、適用性強(qiáng)，很多多目標(biāo)車間調(diào)度問題在其基礎(chǔ)上進(jìn)行改進(jìn)，例如吳秀麗等[19]考慮問題特性設(shè)計了降準(zhǔn)解碼算法；朱偉[20]改進(jìn)染色體編碼，采用了線性次序交叉和逆序變異的方法；Wang等[21]結(jié)合啟發(fā)式算法提高搜索能力；Sheikhalishahi等[22]建立了考慮工人犯錯和預(yù)防性維護(hù)的最優(yōu)化工人犯錯率、機(jī)器利用率和總加工時間調(diào)度模型，通過實(shí)驗(yàn)證明相對于多目標(biāo)粒子群優(yōu)化(Multi-Objective Particle Swarm Optimization，MOPSO)算法和增強(qiáng)Pareto進(jìn)化算法(Strength Pareto Evolutionary Algorithm-Ⅱ，SPEA-Ⅱ)，NSGA-Ⅱ的優(yōu)化效果更優(yōu)；Ahmadi等[23]解決了最優(yōu)化總加工時間和穩(wěn)定性的柔性車間調(diào)度問題，通過實(shí)驗(yàn)證明了NSGA-Ⅱ在多個指標(biāo)下的有效性。這些基于NSGA-Ⅱ設(shè)計的算法對解決文本問題提供了參考。另外，迭代Pareto貪婪算法(Iterated Pareto Greedy algorithm，IPG)可以有效提高鄰域搜索能力，在解決流水車間多目標(biāo)問題上應(yīng)用廣泛，如文獻(xiàn)[24-27]等，其主要思想是在解集中選擇某一解，提取該解中多個工件，剩余的工件可視為子序列，然后逐個插入提取的工件。因?yàn)槊總€工件可以插入子序列中的不同位置，所以每次插入工件會生成多個子序列，保留其中不被支配的子序列，直到所有工件完成插入，該過程可以有效搜索解的鄰域，被稱為解構(gòu)和重構(gòu)。然而，當(dāng)這種方法所選擇解構(gòu)的解的數(shù)量或每個解中所提取工件的數(shù)量較多時，會使目標(biāo)值的計算次數(shù)激增，迭代次數(shù)減少，從而影響搜索效果；當(dāng)數(shù)量較小時不能有效擴(kuò)展解空間，也會影響搜索效果。因此，傳統(tǒng)的IPG很難直接求解本文問題。

本文針對考慮學(xué)習(xí)效應(yīng)的單人作業(yè)車間多目標(biāo)調(diào)度問題，提出考慮學(xué)習(xí)效應(yīng)的多目標(biāo)貪婪算法，融合NSGA-Ⅱ與基于貪婪的鄰域搜索，構(gòu)造了迭代多目標(biāo)遺傳算法(Iterated Multi-Objective Genetic Algorithm, IMOGA)，并通過仿真實(shí)驗(yàn)證明了該算法解決本文問題的有效性。

1 問題描述與建模

定義如下決策變量和輔助變量：

zki為決策變量，zki=1表示第k個工件在機(jī)器i上加工，否則zki=0。

xki為輔助變量，表示準(zhǔn)備安裝第k個工件時在機(jī)器i可以安裝的最早時間。

構(gòu)建如下數(shù)學(xué)模型：

f1=minCmax；

(1)

f2=minD。

(2)

s.t.

(3)

(4)

xki≥0,i=1,2,…,M;k=1,2,…,N；

(5)

i=1,2,…,M,k=2,3,…,N；

(6)

V(1-zkiz(k-1)l),i=1,2,…,M,

l=1,2,…,M,i≠l,k=2,3,…,N；

(7)

i=1,2,…,M,k=1,2,…,N；

(8)

(9)

其中：式(1)表示目標(biāo)1，即最小化最大完工時間；式(2)表示目標(biāo)2，即最小化行走時間；式(3)限制每個工件只能被加工一次；式(4)限制每個機(jī)器只能加工相應(yīng)數(shù)量的工件；式(5)限制每個工件只能在零時刻之后被安裝；式(6)限制第k個工件的加工機(jī)器的允許安裝時間，對于所有機(jī)器，準(zhǔn)備安裝第k個工件時，機(jī)器i可以安裝的時間一定大于或等于準(zhǔn)備安裝第k-1個工件時機(jī)器i可以安裝的時間，如果第k個工件的加工機(jī)器與第k-1個工件相同，則需要第k-1個工件安裝并加工完成后才允許安裝第i個工件；式(7)限制了機(jī)器的安裝只能發(fā)生在工人到達(dá)該機(jī)器之后，即xki大于等于工人完成第k-1個工件安裝后到達(dá)第k個工件加工機(jī)器的時間，其中V為足夠大的數(shù)，其使zkiz(k-1)l=0時式(7)變?yōu)闊o效條件；式(8)限制最大完工時間應(yīng)在所有工件加工完成后；式(9)定義了行走時間的計算方式。

該模型和傳統(tǒng)的車間調(diào)度問題模型不同，對比文獻(xiàn)[28]對傳統(tǒng)模型的分析，本文模型呈現(xiàn)以下特點(diǎn)：

(2)本文考慮了兩機(jī)器之間工人的行走時間，該變量需要通過決策變量確定機(jī)器的先后順序，因此第k和第k-1個工件加工機(jī)器之間的工人行走時間表示為zkiz(k-1)ltil，使模型中增加了二次不等式約束，即式(7)。

(3)單人操作和工件為單工序的前提，決定了本文需要依次確定各個工件的加工機(jī)器，因此定義了決策變量zki和輔助變量xki，其數(shù)量均為MN，約束條件的數(shù)量為N+M+3MN+M(M-1)(N-1)+1。

鑒于此，該數(shù)學(xué)模型不易求解，本文提出考慮學(xué)習(xí)效應(yīng)的貪婪算法和IMOGA。

2 考慮學(xué)習(xí)效應(yīng)的多目標(biāo)貪婪算法

2.1 目標(biāo)計算方式

Ck(π)=Ok(π)+pπk；

(10)

(11)

(12)

(13)

(14)

2.2 考慮學(xué)習(xí)效應(yīng)的多目標(biāo)貪婪算法

傳統(tǒng)貪婪算法的思想是按一定規(guī)則選擇未插入調(diào)度列表的工件，將其插入調(diào)度列表，使插入之后的列表符合某最優(yōu)條件，例如NEH(M.Nawaz, E.E.Enscore, I.Ham)啟發(fā)式算法需要保證最大完工時間最小[24-27]，這些傳統(tǒng)貪婪算法一般只能對單一目標(biāo)求解。對于本文的多目標(biāo)問題，傳統(tǒng)貪婪算法不能實(shí)現(xiàn)求解的廣泛性和均勻性，因此本文提出考慮學(xué)習(xí)效應(yīng)的多目標(biāo)貪婪算法(Multi-Objective Greedy algorithm with Learning effect, MOGL)。MOGL的基本思想是分配一部分工件，以最小化完工時間作為插入位置的判斷準(zhǔn)則，另一部分工件以最小化工人行走時長作為插入位置的判斷準(zhǔn)則，通過變化分配的比例調(diào)節(jié)兩個目標(biāo)的貪婪程度，從而獲得多個貪婪解。該比例用r表示，前rN個工件插入時以最小化最大完工時間作為插入位置的判斷準(zhǔn)則，剩余工件以最小化工人行走時長作為插入位置的判斷準(zhǔn)則，每個解生成方式如下：

步驟1隨機(jī)選擇某一工件放入調(diào)度列表，生成僅包含一個工件的初始列表，執(zhí)行步驟2。

步驟2若調(diào)度列表中的工件數(shù)量N′=N，則該解生成結(jié)束；若N′>rN，則轉(zhuǎn)步驟4；否則執(zhí)行步驟3。

步驟4隨機(jī)選擇一個剩余工件，計算其插入列表的首位、末位和任意兩工件之間時新列表的D′，插入使D′最小的位置，返回步驟2。

r的取值越豐富、越均勻，解集的廣泛性越好。因此構(gòu)造多個解時，只要調(diào)節(jié)r的取值，利用上述方式求解，便可得到對兩個目標(biāo)不同貪婪程度的解集。

3 迭代多目標(biāo)遺傳算法

傳統(tǒng)的非支配排序遺傳算法(Nondominated Sorting Genetic Algorithm, NSGA)由Srinivas和Deb于1994年提出[29]，其進(jìn)一步改進(jìn)算法，提出了NSGA-Ⅱ，以及非支配解排序方法、精英選擇策略和擁擠度計算方法。本文針對單人作業(yè)車間調(diào)度問題，定義了NSGA-Ⅱ的編碼和變異方法。交叉的操作效果和變異差別不大，為降低算法復(fù)雜度，在生成新種群時刪除了交叉操作。NSGA-Ⅱ是IMOGA迭代中的一部分，起隨機(jī)擾動的作用，在完成NSGA-Ⅱ后，IMOGA增加了基于貪婪的鄰域搜索來優(yōu)化尋優(yōu)效果。迭代前，本文采用MOGL構(gòu)造初始解集。

(1)染色體編碼

本文NSGA-Ⅱ染色體為所有工件排列成的有序數(shù)組，每個工件代表一個基因。例如{1,1…,2,2,…,M,M,…}為一條染色體，每條染色體均為該問題的可行解，如圖1所示。

(2)初始種群

初始種群對算法效果的影響較大，傳統(tǒng)的NSGA-Ⅱ采用隨機(jī)方式或啟發(fā)式算法構(gòu)建初始解。對于傳統(tǒng)IPG，有的以隨機(jī)方式產(chǎn)生初始解，如文獻(xiàn)[25]；有的采用貪婪算法構(gòu)建針對單目標(biāo)的初始解，下文稱這樣的解為極端解，例如文獻(xiàn)[24，27]采用啟發(fā)式算法求極端解，文獻(xiàn)[26]采用NEH和隨機(jī)的方式構(gòu)建初始解集。

本文構(gòu)建通用型MOGL來獲得多樣性的初始解，參數(shù)r=1時，MOGL可以獲得最小完工時間的極端解，此時MOGL改變了傳統(tǒng)NEH啟發(fā)式算法選擇工件的方法，使其更適應(yīng)單人作業(yè)場景；參數(shù)r=0時，MOGL可以獲得最小化行走時間的極端解；r取其他值可以得到兩個目標(biāo)不同貪婪程度的解。本文利用MOGL的靈活性設(shè)計了生成初始種群的方法，并通過實(shí)驗(yàn)測試了不同初始解集對IMOGA的影響。

(3)變異

變異是隨機(jī)選擇兩個不相同的工件，交換其位置，該方式在算法優(yōu)化前期起迅速擴(kuò)展解空間的作用，后期對解集進(jìn)行隨機(jī)擾動，以輔助解集跳出局部最優(yōu)。多數(shù)傳統(tǒng)IPG[24-25,27]沒有隨機(jī)擾動操作，只在加工序列解構(gòu)和重構(gòu)過程中擴(kuò)展解空間，其搜索鄰域的范圍不夠充分，本文彌補(bǔ)了此項(xiàng)不足。

(4)基于貪婪的鄰域搜索

經(jīng)典IPG[24-27]是利用一定規(guī)則在解集中選取一解，然后在該解中提取多個工件，依次插入剩余加工序列的兩兩工件之間，并在插入每個工件時保留非支配解。對于本文問題，如果提取多個工件依次插入兩兩工件之間，則計算量大，較為耗時。因此本文進(jìn)行了改進(jìn)，每次僅提取一個工件，然后對每一個非支配解執(zhí)行多次工件提取后插入的操作，使每個非支配解的鄰域均可被搜索，從而提高了搜索的有效性和廣泛性，并節(jié)省了搜索時間，增加了算法迭代次數(shù)。另外，本文的鄰域搜索部分增加了快速非支配解排序、計算擁擠度、精英選擇策略，從而有效保留了每次鄰域搜索中得到的優(yōu)質(zhì)解。每個染色體提取插入操作的次數(shù)用參數(shù)w表示，假設(shè)當(dāng)前解集為Pg，染色體數(shù)量為|Pg|，則鄰域搜索算法步驟如下：

步驟3對Pg∪Qg中的所有解進(jìn)行快速非支配解排序，并計算擁擠度，同時根據(jù)精英選擇策略保留|Pg|個染色體代替當(dāng)前種群Pg，鄰域搜索結(jié)束。

(5)終止條件

算法設(shè)置兩種迭代的終止條件，一是到達(dá)迭代次數(shù)閾值，即L

(6)IMOGA主流程

步驟1初始化染色體數(shù)NP、初始種群Pg、每次迭代中NSGA-Ⅱ世代數(shù)上限G、參數(shù)Lend和w，令迭代次數(shù)L=0。

步驟2檢測是否達(dá)到終止條件，如果達(dá)到終止條件，則算法終止，輸出HL；否則，令L=L+1，g=1，執(zhí)行步驟3。

步驟3如果g≤G，則執(zhí)行步驟4；否則，執(zhí)行步驟6。

步驟4在種群Pg中隨機(jī)選擇兩條染色體進(jìn)行變異，將生成的兩條新染色體填充至Pg。循環(huán)步驟4，直到Pg中包含3NP條染色體后執(zhí)行步驟5。

步驟5計算Pg中所有染色體的目標(biāo)值，對目標(biāo)值相同的染色體去重后進(jìn)行快速非支配解排序，并計算擁擠度。根據(jù)精英選擇策略，保留NP條染色體，生成Pg+1，g=g+1。返回步驟3。

步驟6對Pg進(jìn)行基于貪婪的鄰域搜索，更新Pg，HL=Pg，返回步驟2。

快速非支配解排序、計算擁擠度、精英選擇策略可參考相關(guān)文獻(xiàn)，本文不再贅述。

綜上所述，IMOGA在傳統(tǒng)NSGA-Ⅱ解決多目標(biāo)問題優(yōu)勢的基礎(chǔ)上，融合了迭代貪婪算法的思想，可以有效提高精英解的質(zhì)量并保留到下一代；IMOGA利用MOGL產(chǎn)生初始解集，突破了傳統(tǒng)貪婪算法只能對單一目標(biāo)求解的局限性，不但可以求得各個目標(biāo)較優(yōu)的極端解，而且使其能夠適應(yīng)考慮學(xué)習(xí)效應(yīng)的加工環(huán)境；基于貪婪的鄰域搜索考慮本文在計算目標(biāo)值方面耗時較長的問題，改進(jìn)了搜索思路，可以有效搜索各非支配解的鄰域，并簡化每次搜索的流程，增加了算法迭代次數(shù)。

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

本文設(shè)計了多組實(shí)驗(yàn)來測試IMOGA的性能。所有實(shí)驗(yàn)在Intel(R)Core(TM)i7-8550U CPU@1.80 GHz雙核處理器16.00 G的計算機(jī)上完成，NSGA-Ⅱ采用軟件MATLAB 2019A編寫。實(shí)驗(yàn)中，各機(jī)器的工人標(biāo)準(zhǔn)安裝時間si和機(jī)器標(biāo)準(zhǔn)加工時間pi分別滿足[1,15]，[5,25]的均勻分布；兩兩機(jī)器之間工人的行走時長tlj由坐標(biāo)值滿足[1,10]的均勻分布的點(diǎn)計算得到，M=5，10，15，20，ni在區(qū)間[1,20]和[5,25]隨機(jī)取值，因此實(shí)驗(yàn)共有4×2=8種場景，每種實(shí)驗(yàn)場景生成10個案例；a=-0.322。本文采用不同算法求解所有實(shí)驗(yàn)案例，從以下方面對實(shí)驗(yàn)結(jié)果進(jìn)行分析比較。為統(tǒng)一標(biāo)準(zhǔn)，所有算法生成解數(shù)量為100的解集，并設(shè)定相同的時間閾值TotalTime。

本文引入Hypervolume指標(biāo)衡量多目標(biāo)算法的求解效果。Hypervolume指標(biāo)是衡量求解多目標(biāo)優(yōu)化算法較為公正的指標(biāo)[30-31]，可以衡量解集的綜合性能。Hypervolume指標(biāo)評價方法由Zitzler等[32]提出，表示解集中的個體與參考點(diǎn)在目標(biāo)空間中所圍成的超立方體的體積，用式(15)計算，Hypervolume指標(biāo)值用H表示。實(shí)驗(yàn)選擇坐標(biāo)(1.2,1.2)作為參考點(diǎn)，將兩目標(biāo)值分別歸一化后進(jìn)行計算，H值越大，解集的收斂性越好。

(15)

4.1 初始解對IMOGA的影響

為對比不同解集對算法的影響，本文構(gòu)造了7種方法生成初始解集，解集規(guī)模為100，分別是：

(1)r=0,0.01,…,0.99，分別用MOGL各生成1個解。

(2)r=0,1，分別用MOGL各生成50個解，即生成多個兩目標(biāo)的極端解。

(3)r=0,1，分別用MOGL各生成1個解，其余98個解以隨機(jī)方式生成。

(4)r=0,0.25,0.5,0.75,1，分別用MOGL各生成20個解。

(5)r=1，用MOGL生成100個解，即解集中全部為以最小化最大完工時間為目標(biāo)的極端解。。

(6)r=0，用MOGL生成100個解，即解集中全部為以最小化行走時間為目標(biāo)的極端解。

(7)隨機(jī)生成100個解。

表1所示為不同初始解集時IMOGA的Hypervolume指標(biāo)值，算法的參數(shù)取值為w=10，G=200，TotalTime=0.5N。觀察不同方式的均值可得，方法2的效果最好。方法2的特點(diǎn)是對每個目標(biāo)執(zhí)行貪婪算法的次數(shù)最多，因此可以得到盡量優(yōu)質(zhì)的極端解，其對解集的擴(kuò)展起積極的作用，這一點(diǎn)通過與方法1和方法4對比得到。方法1和方法4增加了初始解的均勻性和廣泛性，通過圖2可見方法1生成的初始解集的分布。但是方法1和方法4計算兩目標(biāo)極端解的次數(shù)少，不能得到較優(yōu)的極端解，在算法執(zhí)行時間較長時，初期廣泛性的優(yōu)勢不再明顯，而方法2生成的解集中極端解的優(yōu)勢可以更好地體現(xiàn)出來。方法3與方法1、方法4的差別不大，但其解集中極端解的數(shù)量已經(jīng)減少到最小，說明了極端解在初始解集中的重要性，對于本文問題，初始解集中只要包括兩個極端解，便可得到相對較優(yōu)的結(jié)果。對比方法5和方法6可知，如果解集中只有一個目標(biāo)的極端解，則以最小化行走時間為目標(biāo)的極端解構(gòu)成的初始解集優(yōu)于以最小化最大完工時間為目標(biāo)的情況，更接近包括兩個極端解的初始解集的結(jié)果。方法7是將隨機(jī)解集作為初始解，其效果遠(yuǎn)不如其他方法，因此采用本文提出的MOGL計算初始解集可以有效提升算法性能。下文均以方式2作為初始種群的生成方式。

表1 不同初始解集時IMOGA的Hypervolume指標(biāo)值

為更明顯地體現(xiàn)不同解集對算法的影響，圖2展示了方法1生成的初始解集和以方法5～方法7生成初始解集的IMOGA對某一案例的求解結(jié)果，執(zhí)行時間(單位:s)分別為N，0.5N，0.25N，0.125N，案例的M=10，ni在區(qū)間[1,20]隨機(jī)取值。方法2～方法4生成初始解集的IMOGA的結(jié)果與方法6近似。觀察圖2a可見，在算法執(zhí)行時間較短時，方法1生成初始解集的IMOGA的結(jié)果優(yōu)于隨機(jī)解集的結(jié)果；方法5生成最小化最大完工時間解的優(yōu)勢明顯，但是最小化行走時間解的效果不佳，因此其非支配解集的收斂程度和廣泛性不如方法6；方法6生成的初始解集使IMOGA能夠在較短時間內(nèi)得到較廣泛的非支配解集，其各方面性能明顯優(yōu)于方法5和方法7。觀察圖2b～圖2d可見解集的變化趨勢，隨著算法執(zhí)行時間的增長，方法7生成初始解集的IMOGA的結(jié)果逐漸向方法5靠近，方法6生成初始解集的IMOGA的結(jié)果逐漸向最小化最大完工時間的方向收斂。

綜合分析得，初始解集中兩個極端解越優(yōu)質(zhì)，IMOGA的效果越好；相對最小化最大完工時間為目標(biāo)的極端解，以最小化行走時間為目標(biāo)的極端解可以使IMOGA獲得更好的結(jié)果；隨機(jī)初始解集和全部以最小化最大完工時間為目標(biāo)的初始解集時IMOGA的效果明顯不如其他初始解集。

4.2 參數(shù)對IMOGA的影響

本文以w=10，G=200，TotalTime=0.5N為基準(zhǔn)參數(shù)，分別變化w，G，TotalTime，統(tǒng)計結(jié)果如表2所示。當(dāng)問題規(guī)模較小時，w對IMOGA的影響不穩(wěn)定，隨著問題規(guī)模的增加，當(dāng)w=20時，算法的求解效果較好。當(dāng)問題規(guī)模較小時，G取值較大時的算法效果較好，隨著問題規(guī)模的增加，較小的G可以獲得更優(yōu)解，原因是G的取值影響算法中貪婪鄰域搜索的頻率，頻率越大，算法的效果越好。顯然，TotalTime越大算法的優(yōu)化效果越好，但是隨著執(zhí)行時間的增長，優(yōu)化效果的變化幅度減小，說明算法逐漸收斂于Pareto前沿。

表2 不同參數(shù)時IMOGA求解結(jié)果的Hypervolume指標(biāo)值

4.3 IMOGA與傳統(tǒng)算法的對比

為證明IMOGA的有效性，本文將其與傳統(tǒng)的NSGA-Ⅱ和IPG兩種啟發(fā)式算法進(jìn)行了對比，結(jié)果如表3所示。其中傳統(tǒng)的NSGA-Ⅱ改變了每代交叉得到的新染色體的數(shù)量，分別為NP，2NP，4NP；IMOGA的參數(shù)為w=10，G=100，TotalTime=0.5N；初始解集通過4.1節(jié)的方法1生成；傳統(tǒng)IPG采用文獻(xiàn)[26]的算法?？梢?，IMOGA在各種規(guī)模時均能得到較優(yōu)的解集，相對傳統(tǒng)的IPG，其Hypervolume指標(biāo)值可以提高15.07%，證明了本文對傳統(tǒng)IPG改進(jìn)的有效性，其原因是簡化的鄰域搜索保證了算法的迭代次數(shù)，增加了搜索效率。因?yàn)閭鹘y(tǒng)的NSGA-Ⅱ以隨機(jī)方式生成初始解集，限制了其優(yōu)化效果，改變傳統(tǒng)NSGA-Ⅱ染色體交叉的數(shù)量雖然對結(jié)果有一定影響，但是作用不明顯，所以采用IMOGA所得結(jié)果的Hypervolume指標(biāo)值比傳統(tǒng)NSGA-Ⅱ平均提高31.78%。總之，傳統(tǒng)型NSGA-Ⅱ解決本文問題的能力隨問題規(guī)模的增加逐漸下降，而IMOGA、傳統(tǒng)IPG和MOGL解決問題的能力比較穩(wěn)定。因此在規(guī)模較大時，傳統(tǒng)型NSGA-Ⅱ所得解集的Hypervolume指標(biāo)值不如MOGL，MOGL所得解集的平均Hypervolume指標(biāo)值水平略低于傳統(tǒng)IPG。

表3 IMOGA與傳統(tǒng)算法的Hypervolume指標(biāo)值對比

為去除初始解集對不同算法的影響，本文對比了基于同樣初始解的傳統(tǒng)NSGA-Ⅱ和IMOGA的求解效果，如表4所示。IMOGA在不同求解時間和不同問題規(guī)模下的求解效果均略高于傳統(tǒng)NSGA-Ⅱ，其Hypervolume指標(biāo)值平均提高2%。另外，問題規(guī)模越大、執(zhí)行時間越長，IMOGA的優(yōu)勢越明顯，這與貪婪鄰域搜索的執(zhí)行次數(shù)有關(guān)，適當(dāng)頻率的貪婪鄰域搜索可使算法得到更優(yōu)的結(jié)果。因此，貪婪鄰域搜索對優(yōu)化算法有效。

表4 不同時間閾值時IMOGA與傳統(tǒng)型NSGA-Ⅱ的對比

綜上所述，本文所提IMOGA的優(yōu)越性主要體現(xiàn)如下：

(1)針對問題中的學(xué)習(xí)效應(yīng)提出MOGL，得到較優(yōu)的極端解，因此IMOGA有較好的搜索起點(diǎn)，算法可以搜索的鄰域更加廣闊。

(2)變異增加了算法的隨機(jī)搜索能力，在計算前期可以迅速擴(kuò)展解空間，后期輔助解集跳出局部最優(yōu)。

(3)基于貪婪的鄰域搜索對每個非支配解都進(jìn)行有針對性和方向性的鄰域搜索，其搜索效率更高，推動了解集向Pareto前沿收斂。

(4)采用NSGA-Ⅱ作為基本框架，使算法可以保留隨機(jī)搜索和定向搜索獲得的精英解，有效地保證了解集的廣泛性和均勻性。

5 結(jié)束語

本文針對單人單工序多機(jī)作業(yè)車間的最小化最大完工時間和工人行走時間多目標(biāo)調(diào)度問題建立數(shù)學(xué)模型，其融合了基于貪婪的鄰域搜索方法和NSGA-Ⅱ，提出并應(yīng)用MOGL構(gòu)建初始解集，設(shè)計了IMOGA。設(shè)計實(shí)驗(yàn)表明IMOGA可以有效求解該問題，因此本文研究可以有效解決單人管理多臺設(shè)備、需要同時考慮工人行走時間和加工時長的作業(yè)車間調(diào)度問題，所引入的學(xué)習(xí)效應(yīng)模型提高了解決問題的準(zhǔn)確性，決策者可以根據(jù)實(shí)際情況選擇解集中的調(diào)度方案，具有較高的靈活性，然而構(gòu)建學(xué)習(xí)效應(yīng)模型或確定學(xué)習(xí)因子需要對工人的操作行為進(jìn)行大量實(shí)驗(yàn)。

由于IMOGA中基于貪婪的鄰域搜索執(zhí)行時間受問題規(guī)模的影響較大，會降低解決更大規(guī)模問題時的效果，下一步研究將著手改善該問題。另外，單人作業(yè)車間導(dǎo)致各機(jī)器不能及時作業(yè)，造成資源和能源浪費(fèi)，因此補(bǔ)充最小化資源和能源消耗也是未來研究的方向。