曹 磊，葉春明，黃 霞,2

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

0 引言

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

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

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

受雜草叢生現(xiàn)象啟發(fā)，2006年Mehrabian提出一種新型的元啟發(fā)式算法[23]——雜草優(yōu)化(Invasive Weed Optimization, IWO) 算法，該算法原理簡(jiǎn)單、自適應(yīng)性好，被廣泛應(yīng)用于函數(shù)尋優(yōu)、天線隊(duì)列設(shè)計(jì)、應(yīng)急調(diào)度管理、DNA計(jì)算等。作為一種新興算法，IWO算法已在諸多問(wèn)題上得到了應(yīng)用，但在生產(chǎn)調(diào)度中的應(yīng)用較少，且基本沒(méi)有應(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)算法求解該問(wèn)題。

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

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

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

(1)

α=lgl/lg2。

(2)

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

(3)

(4)

N位員工在正式上崗之前會(huì)有一定的崗前培訓(xùn)，之后被分配到N個(gè)不同工位上。不同員工接受新知識(shí)的能力略有不同，而且某些員工可能在以前的工作崗位上有類似的工作經(jīng)驗(yàn)，這些都會(huì)在一定程度上影響員工的初始能力。初始能力矩陣Pinitial表征員工正式上崗前對(duì)每工位(本文指機(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é)符號(hào)，如表1所示。FJSP比傳統(tǒng)作業(yè)車間調(diào)度問(wèn)題更加接近實(shí)際調(diào)度情況，其可用數(shù)學(xué)模型描述為：Jj∈{J1,J2,…,Jn}的所有工序被安排在m臺(tái)機(jī)器上加工，同工件各工序間存在固定的加工順序，每一道工序都有其特定的機(jī)器集合，且至少有一道工序的機(jī)器集合中的機(jī)器個(gè)數(shù)大于1。

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

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

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

(16)

(17)

(18)

3 算法設(shè)計(jì)

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

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

(19)

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

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

(20)

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

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

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

(21)

算法流程圖如圖1所示。

3.2 雜草個(gè)體編碼

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

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

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

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

(22)

3.2.2 員工指派

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

3.3 變鄰域搜索策略

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

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

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

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

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

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

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

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

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

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

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

(23)

Crowding-distance(I)

{ l=|I|;

initial所有個(gè)體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個(gè)目標(biāo)函數(shù)值對(duì)群體I排序的函數(shù)。通過(guò)計(jì)算非支配排序和擁擠距離，群體中所有個(gè)體都有排序號(hào)和擁擠距離兩個(gè)特征向量。比較兩個(gè)個(gè)體時(shí)，如果非劣層級(jí)不同，則取層級(jí)高的個(gè)體；如果兩個(gè)個(gè)體在同一層級(jí)，則取擁擠距離大(聚集密度小)的個(gè)體。用I[i]rank表示i個(gè)體的排序，得到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é)中表示物種的多樣性。近年來(lái)，學(xué)者們嘗試將熵與元啟發(fā)式算法融合來(lái)解決優(yōu)化問(wèn)題[32-34]，本文借助熵值權(quán)重的思想，提出基于灰熵關(guān)聯(lián)的適應(yīng)度值分配策略，具體步驟如下：

步驟1分別對(duì)單目標(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)個(gè)數(shù)。另外，對(duì)種群中的可行解xi，分別計(jì)算其子目標(biāo)函數(shù)值fm(i),組成序列Yi={f0(i),f1(i),…,fM(i)}。其中：m=1,…,M，i=1,2,…,N。

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

(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)兩個(gè)子群。其中，外部檔案存儲(chǔ)了非劣解集，可被繁殖子群更新。總種群規(guī)模為N，外部檔案子群規(guī)模為N1，繁殖子群規(guī)模為N2。外部檔案子群記錄非支配子集，繁殖子群記錄非支配前沿Fi(i=1,2,…,k,k為非支配前沿?cái)?shù))。第一代外部檔案取自繁殖子群中的F1，若非劣解個(gè)數(shù)大于N1，則取前N1個(gè)個(gè)體，否則取F1的所有個(gè)體。外部檔案生成后，可用繁殖子群(pop)對(duì)外部檔案子群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個(gè)

}

3.7 算法流程

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

步驟1設(shè)置參數(shù),包括初始雜草個(gè)數(shù)G、最大雜草個(gè)數(shù)P、問(wèn)題的維數(shù)D、目標(biāo)個(gè)數(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ī)則初始化雜草群體，計(jì)算3個(gè)子目標(biāo)的適應(yīng)度值，并按照3.6節(jié)計(jì)算出灰熵關(guān)聯(lián)度，作為雜草個(gè)體的適應(yīng)度值。

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

步驟4運(yùn)用IWO算法進(jìn)行迭代優(yōu)化，按式(19)計(jì)算雜草個(gè)體的子代個(gè)數(shù)，雜草的種子按式(20)以隨機(jī)步長(zhǎng)在一定范圍內(nèi)進(jìn)行空間擴(kuò)張生長(zhǎng)出新雜草，并將新生成的雜草加入雜草群體。計(jì)算新生雜草的適應(yīng)度值，取排名前10%的精英雜草進(jìn)行變鄰域搜索。將變鄰域搜索得到的優(yōu)良個(gè)體按3.6節(jié)更新外部檔案子群ES，雜草群體按3.4節(jié)方法對(duì)新雜草群體進(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 仿真實(shí)驗(yàn)

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

4.1 算法性能測(cè)試

為了驗(yàn)證本文所提VNIWO算法的性能，求解文獻(xiàn)[17]中8×8,10×10,15×10 3個(gè)不同規(guī)模的基準(zhǔn)問(wè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]對(duì)比，實(shí)驗(yàn)結(jié)果如表3所示。針對(duì)基準(zhǔn)案例中一部分柔性案例(8×8)和完全柔性案例(15×10)，繪制Pareto解集中一個(gè)解的甘特圖，如圖5和圖6所示。

表3 Kacem基準(zhǔn)問(wèn)題對(duì)比實(shí)驗(yàn)

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

4.2 案例分析

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

表4 員工技能水平

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

(32)

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

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

5 結(jié)束語(yǔ)

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

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