曹 磊，葉春明，黃 霞,2

(1.上海理工大學 管理學院，上海 200093；2.江蘇科技大學張家港校區(qū) 電信學院，江蘇 張家港 215600)

0 引言

行為調(diào)度體現(xiàn)了企業(yè)、員工、顧客、環(huán)境、社會價值的多重統(tǒng)一，對提高企業(yè)效益、員工價值、顧客價值、資源利用率和社會效益具有重要的意義[1]。從制造、服務到供應鏈及產(chǎn)品研發(fā)的絕大多數(shù)運作中,人都是系統(tǒng)的重要組成部分，人類的行為可能會大大影響運作系統(tǒng)[2]。在實際生產(chǎn)中，人的行為具有多變性、復雜性，而大多數(shù)模型不考慮人的行為因素，忽略了人的素質稟賦、知識經(jīng)驗、認知狀態(tài)等。近年來，一些生產(chǎn)制造領域的學者開始研究人的行為因素，構建了新的調(diào)度模型[3-5]。學習效應是實際制造系統(tǒng)中普遍存在的一種現(xiàn)象，研究學習效應有助于縮小理論研究與生產(chǎn)實踐之間的差距，有助于生產(chǎn)型企業(yè)做出更為合理的決策。

Wright[6]通過研究航空制造業(yè)中人的行為對生產(chǎn)效率的影響，首次提出學習效應曲線理論，通過構建相應的函數(shù)對其進行量化，隨后諸多學者對此進行了研究。Biskup最早提出了與工件加工位置有關的學習效應，并在文獻[7]中對學習效應模型進行總結歸納。大多學者是在Biskup學習效應模型的基礎上進行研究[8-11]。Lee等研究了一個雙指標的單臺機調(diào)度問題,目標是極小化一個包括完成時間和最大滯后的線性組合，給出一個分支定界算法和一個啟發(fā)式算法幫助其尋找最優(yōu)解和近似最優(yōu)解[12]。然而，與工件加工位置有關的學習效應模型忽略了各工件之間加工時間的差異性，Kuo等[13]首先提出一種工件實際加工時間為前面所有工件基本加工時間之和的指數(shù)模型?；谖恢玫膶W習效應模型都存在一個共同的缺點，即當加工工件數(shù)量很大時,加工位置十分靠后的工件的實際處理時間會趨向于零。1957年，Dejong[14]提出一種學習效應模型，克服了Wright所提模型以及后續(xù)大量基于位置的學習效應模型的缺點，而且更加貼近現(xiàn)實生產(chǎn)環(huán)境，然而該學習模型在調(diào)度領域中卻很少被研究。

如今，企業(yè)面臨的經(jīng)營環(huán)境日趨多樣化和復雜化，顧客越來越重視產(chǎn)品的質量和服務，以往大批量連續(xù)生產(chǎn)的制造模式難以適應當前激烈的競爭環(huán)境。柔性作業(yè)車間調(diào)度問題(Flexible Job-shop Scheduling Problem, FJSP)完美體現(xiàn)了生產(chǎn)的柔性，工件的每一道工序可以在多臺相同或不同的機器上加工。在FJSP中，決策者往往期望制造周期短、交貨及時、機器負載均衡等，多目標柔性作業(yè)車間調(diào)度問題(Multi-Objective FJSP, MOFJSP)是一種更為實際的柔性生產(chǎn)作業(yè)模型。傳統(tǒng)多目標優(yōu)化方法有加權組合法、理想點法和極小極大法等，這些多目標優(yōu)化方法或者是直接將多個目標合并為一個目標處理，或者是每次只考慮一個目標，其他目標通過不同方式(如排序等)作為約束進行優(yōu)化。這些優(yōu)化方法有一定局限性，例如權重系數(shù)一般需要由決策者事先給出；一些算法對Pareto最優(yōu)前端的形狀很敏感；往往一次僅能獲得一個Pareto最優(yōu)解[15]。近十幾年來，通過模擬自然界中生物或物理過程而發(fā)展起來的元啟發(fā)式算法越來越多地應用于研究MOFJSP，如遺傳算法(Genetic Algorithm, GA)[16-18]、蟻群優(yōu)化(Ant Colony Optimization, ACO)算法[19]、禁忌搜索(Tabu Search, TS)算法[20]、粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法[21]等。Kacem等是較早運用GA求解MOFJSP問題的學者，他們應用該方法同時優(yōu)化最大完工時間、機器總負載和瓶頸機器負載3個目標[16-17]；張靜等提出一種基于Pareto支配的混合PSO算法求解MOFJSP，3個目標與文獻[16-17]一致，并通過求解基準案例驗證了算法的有效性[21]；仲于江等[22]將小生境的概念引入PSO算法中，提出一種新型的混合算法，并通過實驗驗證了算法的有效性。從現(xiàn)有研究看，元啟發(fā)式算法可有效求解MOFJSP，目標多是完工時間最大、機器總負載和瓶頸機器負載最小。為方便比較，本文所用的目標與文獻[16]相同。

受雜草叢生現(xiàn)象啟發(fā)，2006年Mehrabian提出一種新型的元啟發(fā)式算法[23]——雜草優(yōu)化(Invasive Weed Optimization, IWO) 算法，該算法原理簡單、自適應性好，被廣泛應用于函數(shù)尋優(yōu)、天線隊列設計、應急調(diào)度管理、DNA計算等。作為一種新興算法，IWO算法已在諸多問題上得到了應用，但在生產(chǎn)調(diào)度中的應用較少，且基本沒有應用于具有學習效應的多目標柔性調(diào)度研究。Dejong學習效應模型與Biskup模型相比更為一般化，模型中的“不可壓縮因子”反映了加工環(huán)境中的人機配比情況。因此，本文考慮Dejong學習效應，構建了具有異質性學習效應的MOFJSP模型，并提出一種雙段編碼的變鄰域雜草優(yōu)化(Variable Neighbourhood Invasive Weed Optimization, VNIWO)算法求解該問題。

1 基于Dejong學習效應的調(diào)度問題

傳統(tǒng)的面向制造的生產(chǎn)調(diào)度很少考慮操作者的參與體驗，即便考慮，也多將人視為能夠按照一定規(guī)則運作的完全理性人，忽略了人的素質稟賦、知識經(jīng)驗、認知狀態(tài)、心理因素甚至社會環(huán)境的影響。而在基于學習效應的制造系統(tǒng)中，操作角色廣泛參與于制造過程，他們不斷學習、自我超越，是制造系統(tǒng)中最活躍的資源之一。

學習效應指生產(chǎn)者在長期生產(chǎn)過程中，通過不間斷反復地做同一件事情，在一個合理的時間段內(nèi)，由于知識的不斷積累使得學習主體的經(jīng)驗得到增加，熟練程度得到提升，從而減少時間或成本的現(xiàn)象。受Wright在飛機制造業(yè)領域內(nèi)學習效應研究的啟發(fā)，Biskup[24]和Cheng等[25]開啟了調(diào)度領域學習效應的研究。此后,大量學者致力于對生產(chǎn)調(diào)度領域中學習效應模型的研究，包括Koulamas等[26]、Biskup[7]、Lu等[27]、Cheng等[28]。以上研究大多基于工件位置，文獻[7]對此類學習效應模型做了綜述研究。基于位置的學習效應模型都存在一個共同的缺點，即當加工工件數(shù)量很大時，加工位置十分靠后的工件的實際處理時間會趨向于零。與Biskup模型相比，Dejong學習效應模型是一種更為一般化的模型[14]，即：

(1)

α=lgl/lg2。

(2)

在生產(chǎn)系統(tǒng)中，員工的學習效果主要受初始能力、學習能力、任務難度和工作重復次數(shù)4個因素影響[29]。其中，任務難度和作業(yè)重復次數(shù)在很大程度上與作業(yè)本身有關，初始能力和學習能力主要與員工本身有關。為清晰表述員工的異質性，定義員工初始技能矩陣Pinitial和學習率L矩陣：

(3)

(4)

N位員工在正式上崗之前會有一定的崗前培訓，之后被分配到N個不同工位上。不同員工接受新知識的能力略有不同，而且某些員工可能在以前的工作崗位上有類似的工作經(jīng)驗，這些都會在一定程度上影響員工的初始能力。初始能力矩陣Pinitial表征員工正式上崗前對每工位(本文指機器)的操作能力，學習矩陣L表征每位員工在不同工位的學習能力?？紤]到員工的異質性，修正了Dejong學習效應模型：

(5)

αkm=lgLkm/lg 2。

(6)

修正模型除了考慮員工的初始技能水平，還兼顧員工后期的學習能力，然后將其應用到考慮員工技能異質性的柔性作業(yè)車間調(diào)度中。

2 基于學習行為的多目標柔性制造系統(tǒng)

為方便討論，引入數(shù)學符號，如表1所示。FJSP比傳統(tǒng)作業(yè)車間調(diào)度問題更加接近實際調(diào)度情況，其可用數(shù)學模型描述為：Jj∈{J1,J2,…,Jn}的所有工序被安排在m臺機器上加工，同工件各工序間存在固定的加工順序，每一道工序都有其特定的機器集合，且至少有一道工序的機器集合中的機器個數(shù)大于1。

注：數(shù)字符號含義僅適用于本章。

求解FJSP的關鍵是為工序分配適當?shù)臋C器，并對每臺機器上的工序進行排序，根據(jù)工序約束和機器約束計算出每道工序的開始時間和結束時間，從而求得制造系統(tǒng)的某個或某些指標的最優(yōu)或近似最優(yōu)解。一般FJSP需滿足如下約束：

i=1,2,3,…,m，j=1,2,3,…,n，

h=1,2,3,…,hj；

(7)

cjh≤sj(h+1)，j=1,2,3,…,n，

h=1,2,3,…,hj-1；

(8)

cjhj≤Cmax，j=1,2,3,…,n；

(9)

j=1,2,…,n，k=1,2,3,…,n，h=1,2,3,…,hj，

l=1,2,3,…,hk，i=1,2,3,…,m；

(10)

cjh≤sj(h+1)+L(1-yiklj(h+1))，

j=1,2,…,n，k=1,2,3,…,n，h=1,2,3,…,

hj-1，l=1,2,3,…,hk，i=1,2,3,…,m；

(11)

(12)

l=1,2,3,…,hk，i=1,2,3,…,m；

(13)

j=1,2,3,…,n，h=1,2,3,…,hk；

(14)

sjh≥0,cjh≥0，j=1,2,…,n，h=1,2,3,…,hj。

(15)

其中：rih表示當前工序在機器i上的加工順序；式(7)和式(8)表示工序間存在先后約束；式(9)表示在給定的調(diào)度方案下，每一工件的完工時間存在上界Cmax；式(10)和式(11)表示同一時刻同一臺機器只能加工一道工序；式(12)表示機器約束，即同一時刻同一道工序只能且僅能被一臺機器加工；式(13)和式(14)表示每一臺機器存在循環(huán)操作；式(15)規(guī)定了工序的開始和結束時間均非負。

在實際FJSP生產(chǎn)環(huán)境中，管理者的決策往往涉及諸多目標，這些目標有時互相沖突，管理者根據(jù)生產(chǎn)需要選取幾個目標進行優(yōu)化，并根據(jù)自己的偏好在Pareto解集中按照一定的規(guī)則選擇某一調(diào)度方案。本文基于車間層面選擇3個目標進行優(yōu)化，即最小化最大完工時間、最小化機器總負載、最小化瓶頸機器負載。3個目標定義如下：

(16)

(17)

(18)

3 算法設計

3.1 雜草算法的優(yōu)化機理

雜草是指非栽培的野生植物或對人類無用的植物。在自然環(huán)境下，雜草具有超強的環(huán)境適應能力和繁殖能力。由于限定區(qū)域內(nèi)資源的稀缺性，適應性強的雜草有較大幾率存活并產(chǎn)生子代，從而使區(qū)域內(nèi)雜草群體的適應性得到提升。IWO算法中存在如下對應關系:雜草個體—可行解、雜草種群—可行解集、空間擴張—位置更新、資源限制條件—雜草種群規(guī)模限制。從以上分析看，IWO算法體現(xiàn)了大自然中種內(nèi)競爭、優(yōu)勝劣汰的生態(tài)現(xiàn)象。優(yōu)勢雜草個體會產(chǎn)生更多子代，如式(19)所示；迭代后期，種內(nèi)競爭加劇，雜草擴張能力逐漸減弱，如式(20)所示。

(19)

式中：fbest和fworst分別表示當前雜草種群中最優(yōu)雜草和最差雜草的適應度；fitnessi表示第i個體的適應度；smax和smin分別表示雜草個體產(chǎn)生種子個數(shù)的上界和下界。

新生種子在父代周圍繁殖，繁殖半徑與迭代次數(shù)有關，如式(20)所示。種子在每一維度上的實際步長服從均值為0、標準差為σ的正態(tài)分布。

(20)

式中：iter為當前迭代次數(shù)，itermax為最大迭代次數(shù)，σinit和σfinal分別為繁殖半徑初始值和終止值，n為非線性調(diào)和因子?？梢?，雜草種群的繁殖半徑隨迭代的進行呈逐漸減少的趨勢，從而使算法在前期具有較強的全局搜索能力。隨著σ的逐步減小，子代雜草圍繞父代雜草進行局部搜索。

IWO算法使用不固定規(guī)模的種群μ(即μ≠λ)，但有最大雜草規(guī)模限定，父代種群λ和子代種群μ中的λ+μ個體中選擇適應度值較優(yōu)的個體作為新一代種群Pg，這種選擇方式稱為(λ+μ)-ES演化策略，可描述為

γt=[μ≠λ,(μ+λ),記錄并更新Pg]。

(21)

算法流程圖如圖1所示。

3.2 雜草個體編碼

編碼策略是解決調(diào)度問題的基礎和關鍵。根據(jù)第1章和第2章描述，基于學習行為的MOFJSP需要解決人員指派、工序排序和機器選擇3個子問題。對于傳統(tǒng)的FJSP，學者們一般采用文獻[22]中的二段式編碼方式解決工序排序與機器調(diào)度問題。本文采用連續(xù)二段式編碼方式對雜草個體進行編碼，前段表示工序排序，后段表示人員指派，機器選擇采用啟發(fā)式方法。

從IWO算法的優(yōu)化機理可以看出，基本IWO算法可以直接用來解決連續(xù)優(yōu)化問題，而要求解本文模型，需要提出一種有效的編碼方案，使雜草個體可以解釋為一可行的調(diào)度方案。隨機鍵編碼是一種較為有效的編碼方式，它可以實現(xiàn)連續(xù)空間到離散空間的映射[30]。以一2工件3機器完全FJSP為例(如表2),雜草個體由前后兩段構成，前段編碼長度為工序總數(shù)，后段編碼長度為員工總數(shù)，其前段x1=[0.814 7,0.901 8,0.127 0,0.913 4,0.639 4]，后段x2=[1.2,2.8,1.8]。

3.2.1 工序解碼與機器選擇

工序的解碼過程如圖2所示，按照位置分量從大到小排列工件號(分量值相同時近左優(yōu)先)。為保證排序的合法性，同類工件號的排列順序表示工序的先后順序。

對每道工序采用貪婪策略選擇機器。設Mjh為工序Ojh可選的加工機器集合，集合中機器Mi已完成li道工序的加工任務，完工時間為m_endili,工序Oj(h-1)的完工時間為j_endj(h-1)，則工序Ojh在機器Mi上的預完工時間Cijh=max(m_endili,j_endj(h-1))+tijh；在機器集合Mjh中，選擇使Cijh最小的機器Mi′作為Ojh的加工機器，則最終Ojh的完工時間

(22)

3.2.2 員工指派

對于后段向量，基于ROV(ranked order value)隨機鍵編碼方式，使個體的連續(xù)位置矢量與員工所處的機器位置一一對應。與3.2.1節(jié)類似，根據(jù)每個員工對應的位置分量值，依次挑選分量大的員工，將其安排到未有員工操作的機器號最小的機器上，當位置分量相同時，優(yōu)先挑選員工號小的員工。圖3所示為員工指派的解碼過程。

3.3 變鄰域搜索策略

鄰域是優(yōu)化領域中的一個重要概念，它定義了基于當前解或解集的搜索方向和范圍。對于一般的連續(xù)優(yōu)化問題，鄰域可視為以一點為中心的球區(qū)域。組合優(yōu)化問題不再適用傳統(tǒng)的距離概念，需要定義新的鄰域結構。變鄰域搜索算法(Variable Neighborhood Search, VNS)是一種基于局部搜索算法提出的一種啟發(fā)式算法，該方法已被學者們用于求解諸多組合優(yōu)化問題。鄰域結構的設計是VNS算法的關鍵，本文采用以下3種鄰域結構：

(1)N1(逆序) 在可行工序序列中任意選擇兩個位置，將其中間的工序逆序排列，并按照工序約束修正非法解。

(2)N2(交換) 選擇兩個工序位置對調(diào)工序，并按照工序約束修正非法解。

(3)N3(最小加工時間) 選擇任意一個工序，在其可選機器集合中選擇加工當前工序時間最短的機器。

VNS算法的基本思想是在給定的鄰域結構中不斷嘗試不同的搜索策略，基于“貪婪接受”的思想求得局部最優(yōu)解，并重復以上過程，經(jīng)過若干代迭代輸出結果。VNS算法流程圖如圖4所示。

3.4 非支配排序和擁擠距離排序

非支配排序[31]根據(jù)個體的非劣解水平對種群進行分層。該方法通過計算種群P中每個個體i的兩個參數(shù)Si和ni劃分出非支配前沿Fi(i=1,2,…,k,k為非支配前沿數(shù))。其中Si為被個體i所支配的解個體的集合,ni為在種群中支配個體i的解個體的數(shù)量。非支配排序算法的復雜度為O(mN2),m為目標函數(shù)個數(shù)，N為種群大小，該算法的具體步驟如下：

步驟1k=1，找到種群中ni=0的個體，將其存入當前集合Fk。

步驟2對于當前集合Fk的每個j，考察其所支配的個體集Sj，并將集合Sj中的每個個體q的nq值減1，若nq=0，則將個體k分入下一層非支配前沿Fk+1。

步驟3令k=k+1，如果Fk非空，則轉步驟2；否則，返回前沿F1,…,Fk并結束非支配排序。

多目標優(yōu)化的目的在于發(fā)現(xiàn)一組解而非單個解方案，在保證解質量的前提下盡可能找到一組均勻分布的非劣解集。為描述群體的分布情況，利用擁擠距離刻畫個體間的聚集程度。一般情況下，擁擠距離大的個體的聚集密度小。設I[i]distance表示種群I中第i個個體的擁擠距離，I[i].k表示第i個個體在子目標k上的函數(shù)值，當有m個子目標函數(shù)時，個體i的擁擠距離[31]

(23)

Crowding-distance(I)

{ l=|I|;

initial所有個體I[i]distance=0

for each m∈M

{I=sort(I，m)

I[1]distance=I[l]distance=∞

i=0

while(1≤i≤l)

i=i+1

}

}

其中，sort(I,m)是按第m個目標函數(shù)值對群體I排序的函數(shù)。通過計算非支配排序和擁擠距離，群體中所有個體都有排序號和擁擠距離兩個特征向量。比較兩個個體時，如果非劣層級不同，則取層級高的個體；如果兩個個體在同一層級，則取擁擠距離大(聚集密度小)的個體。用I[i]rank表示i個體的排序，得到i和j的偏序關系?n：

i?nj=

(24)

3.5 灰熵關聯(lián)適應度分配策略

在多目標優(yōu)化算法中有多種適應度值分配策略，如基于Pareto優(yōu)先關系排序的適應度值分配策略、基于隨機權重求和的適應度值分配策略、選擇性權重的適應度值分配策略等。熵是一種度量微觀分布均勻性的方法，其在熱力學中表示系統(tǒng)的混亂狀態(tài)，而在生態(tài)學中表示物種的多樣性。近年來，學者們嘗試將熵與元啟發(fā)式算法融合來解決優(yōu)化問題[32-34]，本文借助熵值權重的思想，提出基于灰熵關聯(lián)的適應度值分配策略，具體步驟如下：

步驟1分別對單目標進行尋優(yōu)，求出各子目標函數(shù)的最優(yōu)值fm(0)(m=1,…,M)，組合為理想解的目標函數(shù)值序列Y0={f1(0),f2(0),…,fM(0)}，M為目標個數(shù)。另外，對種群中的可行解xi，分別計算其子目標函數(shù)值fm(i),組成序列Yi={f0(i),f1(i),…,fM(i)}。其中：m=1,…,M，i=1,2,…,N。

步驟2對理想解和可行解的子目標函數(shù)值序列作無量綱化處理：

(25)

步驟3求灰關聯(lián)系數(shù)

(26)

式中ρ為分辨系數(shù)，一般取ρ=0.5。

步驟4求可行解各子目標的比重

(27)

步驟5求可行解各子目標的信息熵

em(i)=-pm(i)lnpm(i)。

(28)

步驟6求可行解各目標的熵值權重

(29)

步驟7求可行解的灰熵關聯(lián)度

(30)

3.6 外部檔案更新

本文雜草種群中存在外部檔案子群(ES)和繁殖子群(pop)兩個子群。其中，外部檔案存儲了非劣解集，可被繁殖子群更新。總種群規(guī)模為N，外部檔案子群規(guī)模為N1，繁殖子群規(guī)模為N2。外部檔案子群記錄非支配子集，繁殖子群記錄非支配前沿Fi(i=1,2,…,k,k為非支配前沿數(shù))。第一代外部檔案取自繁殖子群中的F1，若非劣解個數(shù)大于N1，則取前N1個個體，否則取F1的所有個體。外部檔案生成后，可用繁殖子群(pop)對外部檔案子群ES進行更新，偽代碼如下：

Update_ES(pop)

{ Q=pop;

while(Q不為空集)

{

x∈Q,令Q=Q-{x};

x is nondominated;

for each y∈ES

{

if(x dominated y)then

ES=ES-{y};

else if(y dominated x)then

x is nondominated=false;

}

if(x is nondominated)then

ES=ES∪{x};

}

if |ES|≥N2then

crowding-distance(ES) select 前N2個

}

3.7 算法流程

綜上所述，求解MOFJSP的VNIWO算法流程歸結如下：

步驟1設置參數(shù),包括初始雜草個數(shù)G、最大雜草個數(shù)P、問題的維數(shù)D、目標個數(shù)M、初始標準差σinit和最終標準差σfinal、擴張區(qū)間大小、最大最小種子數(shù)(smax和smin)、最大迭代次數(shù)、變鄰域搜索次數(shù)VN、外部檔案規(guī)模N1。

步驟2按照3.2節(jié)的編碼規(guī)則初始化雜草群體，計算3個子目標的適應度值，并按照3.6節(jié)計算出灰熵關聯(lián)度，作為雜草個體的適應度值。

步驟3根據(jù)3.6節(jié)生成外部檔案。

步驟4運用IWO算法進行迭代優(yōu)化，按式(19)計算雜草個體的子代個數(shù)，雜草的種子按式(20)以隨機步長在一定范圍內(nèi)進行空間擴張生長出新雜草，并將新生成的雜草加入雜草群體。計算新生雜草的適應度值，取排名前10%的精英雜草進行變鄰域搜索。將變鄰域搜索得到的優(yōu)良個體按3.6節(jié)更新外部檔案子群ES，雜草群體按3.4節(jié)方法對新雜草群體進行非支配排序和擁擠距離排序。

步驟5判斷雜草群體是否達到預設的最大種群規(guī)模，是則按精英選擇策略選出下一代繁殖雜草群體，并用該群體按3.6節(jié)更新外部檔案子群ES。

步驟6判斷是否達到終止條件，是則輸出調(diào)度方案和目標函數(shù)值并終止算法，否則轉步驟4。

O(M(P+Psmax)·log(P+Psmax))

=O(MP(1+smax)·(logP+log(1+smax)))

≈O(M(1+smax)PlogP)。

(31)

4 仿真實驗

本文算法采用MATLAB 2010b編程語言實現(xiàn)，運行環(huán)境為：處理器主頻2.1 GHz，內(nèi)存2 GB、Windows7操作系統(tǒng)。VNIWO算法參數(shù)設置如下：最小雜草個數(shù)為10、最大雜草個數(shù)為15、非線性因子n=4、最小最大種子分別為1和3、初始和終止步長分別為0.1和0.001，鄰域搜索次數(shù)為20，最大迭代次數(shù)為100。

4.1 算法性能測試

為了驗證本文所提VNIWO算法的性能，求解文獻[17]中8×8,10×10,15×10 3個不同規(guī)模的基準問題，并與Kacem的局部搜索受控遺傳算法(Approach by Localization and Controlled Genetic Algorithm, AL+CGA)[16]、Xia的粒子群模擬退火混合算法PSO+SA[35]、Zhang的粒子群禁忌搜索混合算法PSO+TS[36]、Wang的多目標遺傳算法(Multi-Objective Genetic Algorithm, MOGA)[37]對比，實驗結果如表3所示。針對基準案例中一部分柔性案例(8×8)和完全柔性案例(15×10)，繪制Pareto解集中一個解的甘特圖，如圖5和圖6所示。

表3 Kacem基準問題對比實驗

從實驗結果可以看出，VNIWO求解8×8問題所得非劣解集中解的個數(shù)更多，而且分布性較好；求解10×10問題時非劣解集中解的個數(shù)有一定優(yōu)勢，非劣解集解的個數(shù)少于MOGA而多于AL+CGA，PSO+SA，PSO+TS；求解15×10問題得到的非劣解集支配AL+CGA，PSO+SA，PSO+TS和MOGA求得的非劣解集數(shù)目均為1，但與MOGA相比，VNIWO在支配性能指標上不占優(yōu)勢。綜上，VNIWO可有效求得8×8問題的可行解，而且解的質量也有一定優(yōu)勢。

4.2 案例分析

以8×8問題為例，分析具有異質性員工學習效應的FJSP。車間有員工8名，且均為新員工。經(jīng)過技能考核，員工的初始技能水平和學習能力情況如表4所示。括號外的數(shù)值為初始能力(與Pinitial中的相應值對應)，初始能力值可解釋為員工初始操作時間與標準操作工時(與原問題機器標準加工時間對應)的比值，值越小表示員工對某一機器操作越嫻熟;括號內(nèi)的數(shù)值為員工學習率，表征員工對技能的領悟能力，根據(jù)第1章描述，學習率越小，領悟能力越強。

表4 員工技能水平

在Dejong學習效應模型中，F(xiàn)為不可壓縮因子，F(xiàn)=0，1分別表示一個完全手工操作生產(chǎn)和完全由機器控制生產(chǎn)的加工環(huán)境。從實際角度看，一個合適的F值的設定取決于具體的加工任務。因此，研究Dejong學習效應模型中的F值，可以發(fā)現(xiàn)學習效應對不同制造系統(tǒng)的影響，縮小理論研究與實際生產(chǎn)間的差距，有助于決策者做出合理的決策。針對不同的F值，用VNIWO算法求解案例，獨立運行5次后合并非劣解集(部分)，統(tǒng)計結果如表5所示。圖7所示為完全手工環(huán)境下，非劣解集中的一個可行解甘特圖，員工指派方案如表6所示。敏感性分析指定量描述分析模型因素變量對優(yōu)化目標函數(shù)值的重要性程度，一般用敏感系數(shù)表示為

(32)

式中：SfA表示模型目標值f對因素變量A的敏感程度；ΔA/A表示因素變量的變化率；Δf/f表示因素變量變化ΔA時引起模型目標值的變化率。在此分別分析3個子目標函數(shù)值對M的敏感程度，3個子目標函數(shù)值取Pareto集合中目標分量的平均值，計算結果如表7所示。

實驗數(shù)據(jù)表明，本文所提算法對不同M值的柔性作業(yè)車間均可給出較為滿意的非劣解集，3個目標函數(shù)值對M值的敏感度略有不同。從表6可以看出，3個子目標函數(shù)值變化與F值的變化成明顯的正相關性，且幅度有減小的趨勢。僅在敏感因素F變化80%時，總機器負載的變化率同時小于最大完工時間和瓶頸機器負載兩個子目標的變化率。在本文案例中，異質性多技能員工的存在，使得制造系統(tǒng)更具有柔性和學習性，知識和經(jīng)驗的積累使總機器負載減小的程度比較明顯。關鍵工序鏈短和瓶頸機器上的工序數(shù)目少，學習效應積累程度不大，原因可能是最大完工時間和瓶頸機器負載兩個目標對M值變化較不敏感。

5 結束語

本文研究了一類帶有學習效應的MOFJSP，提出VNIWO算法對其進行求解。采用隨機鍵編碼的方式將雜草個體映射為一可行的調(diào)度方案，解決了工序排序、機器選擇和人員指派等問題。針對多目標問題的難解性，采用非支配排序和擁擠距離排序對雜草群體進行精英篩選和更新，給每一個雜草個體賦予一灰熵關聯(lián)適應度值，以方便其產(chǎn)生子代個體。在幾個存在異質性員工學習效應的柔性作業(yè)車間調(diào)度系統(tǒng)中，用靈敏度分析考察子目標函數(shù)值對F值變化的靈敏度。案例分析表明，制造系統(tǒng)中的學習效應對與加工時間有關的目標函數(shù)值有一定影響；不同子目標對F變化的靈敏度是有差異的，總機器負載的靈敏度較大。

本文采用的案例是連續(xù)作業(yè)系統(tǒng)，并未考慮休假、停機等干擾影響，因此設計有效算法，構建更為精細的行為調(diào)度模型，并將其運用到生產(chǎn)運營管理中，將是今后研究的重點。