基于員工學(xué)習(xí)行為的多目標(biāo)柔性車間調(diào)度

曹 磊，葉春明，黃 霞,2

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

0 引言

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

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

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

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

1 基于Dejong學(xué)習(xí)效應(yīng)的調(diào)度問題

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

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

(1)

α=lgl/lg2。

(2)

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

(3)

(4)

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

(5)

αkm=lgLkm/lg 2。

(6)

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

2 基于學(xué)習(xí)行為的多目標(biāo)柔性制造系統(tǒng)

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

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

求解FJSP的關(guān)鍵是為工序分配適當(dāng)?shù)臋C(jī)器，并對每臺機(jī)器上的工序進(jìn)行排序，根據(jù)工序約束和機(jī)器約束計算出每道工序的開始時間和結(jié)束時間，從而求得制造系統(tǒng)的某個或某些指標(biāo)的最優(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表示當(dāng)前工序在機(jī)器i上的加工順序；式(7)和式(8)表示工序間存在先后約束；式(9)表示在給定的調(diào)度方案下，每一工件的完工時間存在上界Cmax；式(10)和式(11)表示同一時刻同一臺機(jī)器只能加工一道工序；式(12)表示機(jī)器約束，即同一時刻同一道工序只能且僅能被一臺機(jī)器加工；式(13)和式(14)表示每一臺機(jī)器存在循環(huán)操作；式(15)規(guī)定了工序的開始和結(jié)束時間均非負(fù)。

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

(16)

(17)

(18)

3 算法設(shè)計

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

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

(19)

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

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

(20)

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

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

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

(21)

算法流程圖如圖1所示。

3.2 雜草個體編碼

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

從IWO算法的優(yōu)化機(jī)理可以看出，基本IWO算法可以直接用來解決連續(xù)優(yōu)化問題，而要求解本文模型，需要提出一種有效的編碼方案，使雜草個體可以解釋為一可行的調(diào)度方案。隨機(jī)鍵編碼是一種較為有效的編碼方式，它可以實現(xiàn)連續(xù)空間到離散空間的映射[30]。以一2工件3機(jī)器完全FJSP為例(如表2),雜草個體由前后兩段構(gòu)成，前段編碼長度為工序總數(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 工序解碼與機(jī)器選擇

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

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

(22)

3.2.2 員工指派

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

3.3 變鄰域搜索策略

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

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

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

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

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

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

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

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

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

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

多目標(biāo)優(yōu)化的目的在于發(fā)現(xiàn)一組解而非單個解方案，在保證解質(zhì)量的前提下盡可能找到一組均勻分布的非劣解集。為描述群體的分布情況，利用擁擠距離刻畫個體間的聚集程度。一般情況下，擁擠距離大的個體的聚集密度小。設(shè)I[i]distance表示種群I中第i個個體的擁擠距離，I[i].k表示第i個個體在子目標(biāo)k上的函數(shù)值，當(dāng)有m個子目標(biāo)函數(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個目標(biāo)函數(shù)值對群體I排序的函數(shù)。通過計算非支配排序和擁擠距離，群體中所有個體都有排序號和擁擠距離兩個特征向量。比較兩個個體時，如果非劣層級不同，則取層級高的個體；如果兩個個體在同一層級，則取擁擠距離大(聚集密度小)的個體。用I[i]rank表示i個體的排序，得到i和j的偏序關(guān)系?n：

i?nj=

(24)

3.5 灰熵關(guān)聯(lián)適應(yīng)度分配策略

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

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

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

(25)

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

(26)

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

步驟4求可行解各子目標(biāo)的比重

(27)

步驟5求可行解各子目標(biāo)的信息熵

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

(28)

步驟6求可行解各目標(biāo)的熵值權(quán)重

(29)

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

(30)

3.6 外部檔案更新

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

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算法流程歸結(jié)如下：

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

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

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

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

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

步驟6判斷是否達(dá)到終止條件，是則輸出調(diào)度方案和目標(biāo)函數(shù)值并終止算法，否則轉(zhuǎn)步驟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è)置如下：最小雜草個數(shù)為10、最大雜草個數(shù)為15、非線性因子n=4、最小最大種子分別為1和3、初始和終止步長分別為0.1和0.001，鄰域搜索次數(shù)為20，最大迭代次數(shù)為100。

4.1 算法性能測試

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

表3 Kacem基準(zhǔn)問題對比實驗

從實驗結(jié)果可以看出，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在支配性能指標(biāo)上不占優(yōu)勢。綜上，VNIWO可有效求得8×8問題的可行解，而且解的質(zhì)量也有一定優(yōu)勢。

4.2 案例分析

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

表4 員工技能水平

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

(32)

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

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

5 結(jié)束語

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

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