張維存 顧洪羽

河北工業(yè)大學(xué)經(jīng)濟(jì)管理學(xué)院,天津,300401

0 引言

隨著我國制造裝備的升級,刀具生產(chǎn)企業(yè)的多品種、小批量甚至定制化訂單不斷攀升,生產(chǎn)成本不斷增加。刀具生產(chǎn)中,雖然自動化的生產(chǎn)設(shè)備擴(kuò)大了工件的加工范圍,提高了工件的質(zhì)量和精度,但仍需工人進(jìn)行裝載、卸載、質(zhì)量檢查和狀態(tài)監(jiān)控等輔助作業(yè),因此,“一人多機(jī)”的并行工作方式得到了重視和應(yīng)用。

刀具的種類、材料、工裝卡具,以及工人學(xué)習(xí)能力的差異影響著工人的作業(yè)效率和實際的作業(yè)調(diào)度。為貼近刀具企業(yè)“一人多機(jī)”的生產(chǎn)環(huán)境,筆者將傳統(tǒng)車間調(diào)度中的工序作業(yè)細(xì)化為裝載、卸載和機(jī)器加工,考慮作業(yè)相似性和工人學(xué)習(xí)效應(yīng)使裝卸時間具有的彈性,將有限的工人合理分配到裝卸任務(wù)中,通過對裝卸和加工任務(wù)的調(diào)度,盡可能縮短工時、節(jié)約人力、平衡工作負(fù)荷。

現(xiàn)實中,工人會因不斷重復(fù)生產(chǎn)而積累工作經(jīng)驗的現(xiàn)象稱為學(xué)習(xí)效應(yīng)[1-2]。線性模型[1]反映了產(chǎn)品數(shù)量與時間的關(guān)系,但難以反映實際工時的變化趨勢。為更真實地反映不同應(yīng)用場景下的學(xué)習(xí)效應(yīng),后續(xù)又提出了Stanford-B模型、Plateau模型[3]、S-曲線模型和DeJong模型[4]。DeJong模型[4]認(rèn)為學(xué)習(xí)效應(yīng)一直存在于生產(chǎn)過程中,且隨著生產(chǎn)作業(yè)的累積,學(xué)習(xí)曲線逐漸趨于穩(wěn)定,符合本文研究的情景,為人-機(jī)的合理分配提供了依據(jù)。

近年來,學(xué)習(xí)效應(yīng)在調(diào)度問題的求解中得到越來越多的關(guān)注。LI[5]研究了學(xué)習(xí)效應(yīng)受隨機(jī)處理時間和隨機(jī)作業(yè)位置影響的單機(jī)調(diào)度問題,以最小化預(yù)期的總流程時間和最大化持續(xù)制造時間。JI等[4]建立了具有同質(zhì)并行機(jī)的調(diào)度模型,應(yīng)用DeJong學(xué)習(xí)效應(yīng)函數(shù)計算了實際的作業(yè)時間。LIN[6]研究了具有可控加工時間和作業(yè)相關(guān)學(xué)習(xí)效應(yīng)的并行機(jī)調(diào)度問題。LIANG等[7]基于對數(shù)處理時間的學(xué)習(xí)效應(yīng),解決了多目標(biāo)流水車間調(diào)度問題。WANG等[8]研究了基于位置學(xué)習(xí)效應(yīng)的置換流水車間調(diào)度問題。在更復(fù)雜的作業(yè)車間中,董君等[9]提出了受加工時間與加工位置共同影響的學(xué)習(xí)效應(yīng)模型,并將其用于半導(dǎo)體晶圓制造的調(diào)度問題。ZOU等[10]研究了考慮學(xué)習(xí)效應(yīng)的三機(jī)兩階段裝配調(diào)度,在作業(yè)次數(shù)的基礎(chǔ)上擴(kuò)充了累計加工時間對學(xué)習(xí)效應(yīng)的影響。胡金昌等[11]研究了基于工件位置學(xué)習(xí)效應(yīng)的作業(yè)車間調(diào)度問題,并建立了多目標(biāo)數(shù)學(xué)模型。顯然,對復(fù)雜調(diào)度環(huán)境下學(xué)習(xí)效應(yīng)的研究更貼近實際和便于應(yīng)用,但更多研究還局限于單人單機(jī)的調(diào)度問題,多人多機(jī)且處理多工序的研究有待進(jìn)一步擴(kuò)充和完善。

在考慮學(xué)習(xí)效應(yīng)的調(diào)度問題研究中,部分學(xué)者意識到相似的零件和工藝對各工序加工轉(zhuǎn)換時間的影響。PARGAR等[12]研究了具有學(xué)習(xí)效應(yīng)的混合流水車間調(diào)度問題,將工人能力的提高建模為重復(fù)類似任務(wù)的模型,通過相似工具共享和相似工序緊鄰縮短轉(zhuǎn)換時間。CHENG等[13]研究了位置加權(quán)學(xué)習(xí)效應(yīng)下的調(diào)度問題,工人通過處理一組類似作業(yè)來獲得工作經(jīng)驗、提升學(xué)習(xí)能力,進(jìn)而得到更好的調(diào)度結(jié)果。此類研究更多關(guān)注作業(yè)相似對加工轉(zhuǎn)換時間的影響,忽略了對裝卸作業(yè)時間的影響。

在多目標(biāo)優(yōu)化問題中,隨著目標(biāo)數(shù)的增加,Pareto解的數(shù)量呈指數(shù)增長,為求解算法的選擇和解集的維護(hù)增加了巨大的壓力。目前,國內(nèi)外學(xué)者對連續(xù)多目標(biāo)優(yōu)化算法進(jìn)行了大量研究。CAI等[14]給出了基于網(wǎng)格加權(quán)和的支配關(guān)系,并將其用于Pareto解的局部搜索,對非支配解的篩選獲得了明顯效果。KHALILPOURAZARI等[15]提出了多目標(biāo)隨機(jī)分形搜索(MOSFS)方法,并利用外部檔案、優(yōu)勢規(guī)則和網(wǎng)格機(jī)制,精確逼近真正的Pareto鋒面。雖然離散多目標(biāo)問題在實踐中隨處可見,但由于離散多目標(biāo)優(yōu)化問題的可行域是斷開或割裂的,因此算法難以實現(xiàn)。構(gòu)建近似Pareto前沿具有挑戰(zhàn)性,實驗效果難以驗證,對其研究也相對較少。YU等[16]提出一種基于離散的通用多目標(biāo)粒子群優(yōu)化方法,采用分解策略,根據(jù)一組權(quán)向量將問題轉(zhuǎn)化為多個單目標(biāo)子問題。MANSON等[17]將高斯過程作為代理,結(jié)合基于高斯相似性的距離度量,提出一種能有效處理連續(xù)變量和離散變量的多目標(biāo)算法。離散多目標(biāo)優(yōu)化算法存在計算量大、結(jié)構(gòu)重分析次數(shù)多、不同量綱目標(biāo)值協(xié)調(diào)難、搜索效率偏低等問題,所求解集的多樣性難以保證。

綜上,“一人多機(jī)”生產(chǎn)模式下考慮學(xué)習(xí)效應(yīng)的作業(yè)車間調(diào)度問題,及該模式下相似學(xué)習(xí)效應(yīng)對裝卸作業(yè)時間的影響沒有得到充分研究,同時也缺少相應(yīng)高效的離散多目標(biāo)求解算法。本文在“一人多機(jī)”生產(chǎn)模式下,考慮作業(yè)相似性和學(xué)習(xí)效應(yīng)對裝卸時間的影響,滿足資源獨占、工藝和作業(yè)順序約束,體現(xiàn)工人多機(jī)作業(yè)特征,構(gòu)建了多目標(biāo)調(diào)度模型。采用兩階段解碼方式,并利用改進(jìn)的N6鄰域搜索和啟發(fā)式規(guī)則高效生成多目標(biāo)的非支配調(diào)度方案。設(shè)計了基于網(wǎng)格篩選外部檔案的遺傳算法(grid filter external archive genetic algorithm,GFEAGA),利用網(wǎng)格技術(shù)對外部檔案中的非支配解進(jìn)行評價和選擇,促進(jìn)生成多樣化的非支配解。

1 數(shù)學(xué)模型的建立

1.1 問題描述

“一人多機(jī)”模式下,考慮相似學(xué)習(xí)效應(yīng)的作業(yè)車間調(diào)度問題可描述為:工件Ji(i∈{1,2,…,n})的m個工序分別在m臺不同的自動化設(shè)備上加工,Oij(j∈{1,2,…,m})為工件i的第j個工序。每道工序依次可分為三個作業(yè)(裝載、加工、卸載),并由設(shè)備k(k=1,2,...,m)完成。每個裝卸作業(yè)需在w個工人中選擇一人執(zhí)行。不同的裝卸作業(yè)具有相似性,且工人具備不同的學(xué)習(xí)能力,因此,執(zhí)行裝卸作業(yè)的實際時間有所不同。工人可在裝卸作業(yè)(設(shè)備)之間自由行走。調(diào)度過程可描述為:考慮工人在設(shè)備間的行走時間和學(xué)習(xí)效應(yīng),選擇裝卸執(zhí)行人員,并安排工人和設(shè)備執(zhí)行裝卸及加工作業(yè)的次序,使每道工序完成裝載、加工、卸載;在滿足生產(chǎn)約束的條件下,實現(xiàn)最大完工時間、工人總負(fù)荷、工人最大負(fù)荷和工人數(shù)量的最小化。模型中所涉及的參數(shù)符號定義如表1所示,涉及的變量符號定義如表2所示。

表1 參數(shù)符號定義

表2 變量符號定義

假設(shè):①工人和設(shè)備同時只能處理一個工件;②不考慮搬運時間;③不考慮設(shè)備故障;④加工過程不允許中斷;⑤工件間無優(yōu)先級;⑥所有工人和設(shè)備零時刻可用;⑦設(shè)備緩存區(qū)足夠大。

1.2 模型建立

模型中決策變量符號定義如表3所示。

表3 決策變量符號定義

DeJong函數(shù)[4]在設(shè)定學(xué)習(xí)效應(yīng)模型時考慮了自動化程度M,DeJong的學(xué)習(xí)曲線模型為

(1)

實際生產(chǎn)中,工人的學(xué)習(xí)效應(yīng)受主觀因素和客觀因素的影響。主觀因素表現(xiàn)為工作經(jīng)驗、學(xué)習(xí)能力等,客觀因素表現(xiàn)為作業(yè)相似性、現(xiàn)場秩序、作業(yè)指導(dǎo)等。調(diào)度問題中,現(xiàn)場秩序和作業(yè)指導(dǎo)等屬于背景因素,不可調(diào)度或改變;工人的學(xué)習(xí)能力差異和作業(yè)相似性可通過工人選派和作業(yè)次序調(diào)整進(jìn)行優(yōu)化,這樣可使調(diào)度方案更加貼合實際生產(chǎn)。因此,本文在DeJong學(xué)習(xí)曲線模型的基礎(chǔ)上進(jìn)行改進(jìn)。改進(jìn)后的學(xué)習(xí)曲線模型

(2)

既能體現(xiàn)工人學(xué)習(xí)效應(yīng),又能體現(xiàn)作業(yè)相似性對作業(yè)時間的影響。所有作業(yè)均相同即θijτ,hgρ=1時,則式(2)轉(zhuǎn)換為式(1);當(dāng)所有作業(yè)均不同即θijτ,hgρ=0時,則式(2)退化為Rijτ=tijτ。如圖1所示,改進(jìn)后的學(xué)習(xí)曲線在原DeJong學(xué)習(xí)曲線上方,且作業(yè)相似性越高,改進(jìn)曲線越貼近原學(xué)習(xí)曲線。

圖1 學(xué)習(xí)曲線模型對比

據(jù)此建立本研究模型如下:

(1)目標(biāo)函數(shù)為

F1=min(maxEij3)

(3)

(4)

ya,ijτ,hgρvijτ,hgρ))

(5)

F4=minw

(6)

(2)約束條件為

(7)

Eijτ=Sijτ+Rijττ=1,2,3

(8)

(9)

λa,hgρ=λa,ijτ+∑xa,ijτxa,hgρya,ijτ,hgρ

(10)

i=1,2,…,nj=1,2,…,mτ=1,3

Shg1≥max(xa,qpρxa,hg1ya,qpρ,hg1(Eqpρ+vqpρ,hg1),

Eh(g-1)3,zij3, hg1Eij3)ρ=1,3

(11)

Sij2≥Eij1

(12)

Shg3≥max(Ehg2,ya,qpτ,hg3(Eqpρ+vqpρ,hg3))ρ=1,3

(13)

模型中,式(3)～式(6)分別表示最大完工時間、工人總負(fù)荷、最大工人負(fù)荷和作業(yè)人數(shù);式(7)表示每項裝卸作業(yè)僅由一人執(zhí)行;式(8)表示裝卸及加工作業(yè)的開始與結(jié)束時間的關(guān)系;式(9)表示工人實際裝卸時間與標(biāo)準(zhǔn)時間的關(guān)系;式(10)表示工人a執(zhí)行到作業(yè)ijτ時累計的作業(yè)數(shù)量;式(11)～式(13)分別表示裝載、加工和卸載作業(yè)的開始時間計算關(guān)系。

2 算法設(shè)計

2.1 問題與算法分析

本研究將每個工序細(xì)分為裝載、加工和卸載三項作業(yè),需要選擇裝卸作業(yè)的執(zhí)行人員,并對裝卸及加工作業(yè)進(jìn)行排序。由于設(shè)備的獨占性,即設(shè)備只能同時處理單個工件的裝載、加工、卸載,因此,可將工件的裝載、加工、卸載視為一個整體,在設(shè)備上進(jìn)行排產(chǎn)。本文采用兩階段的求解策略:第一階段,將工序的裝載、加工、卸載作一個整體進(jìn)行排產(chǎn),通過鄰域搜索獲得初始調(diào)度方案集;第二階段,在初始調(diào)度方案基礎(chǔ)上,對裝載和卸載作業(yè)進(jìn)行人員選派,形成完整調(diào)度方案。

2.2 個體編碼與進(jìn)化操作

2.2.1個體編碼

采用兩段式編碼方法:前段編碼由一個基因構(gòu)成,代表決策變量w的取值;后段編碼采用基于工序編碼方式,編碼長度為mn(代表所有工序編號),個體總編碼長度為mn+1。

如圖2所示:首位3表示由3個工人參與作業(yè)分配,后段2×4個基因表示工序,工件J1、J2分別用數(shù)字1和2表示。后段編碼21221112中,第2次出現(xiàn)的數(shù)字1表示工件J1第2道工序即O12。

圖2 兩段式編碼方式

根據(jù)基因位的工件號及編碼規(guī)則,可以推出該工序的裝卸及加工作業(yè)編號。解碼過程中,通過作業(yè)編號并關(guān)聯(lián)其加工信息,可對整個染色體進(jìn)行解碼。

2.2.2進(jìn)化操作

為提高求解質(zhì)量,除針對前段基因采用等位交叉及隨機(jī)變異外,針對后段編碼,通過實驗選取了5種比較有效的交叉算子:基于順序的交叉(order-based crossover,OBX)、基于位置的交叉(position-based crossover,PBX)、次序交叉(order crossover,OX)、集合分割的交叉(set-partition crossover,SPX)、優(yōu)先操作交叉(precedence operation crossover,POX)。選取3種比較有效的變異算子:交換變異(swap mutation)、反轉(zhuǎn)變異(inversion mutation)、移碼變異(shift mutation)。

2.3 解碼過程

完整的調(diào)度方案要通過兩個階段解碼過程獲得。第一階段(步驟(1)、(2)將裝載、加工、卸載作為一個整體進(jìn)行解碼,并對調(diào)度方案進(jìn)行鄰域搜索;第二階段(步驟(3)～(8)),對整體調(diào)度方案中的裝卸作業(yè)進(jìn)行人員選擇。具體解碼過程(步驟)如下:

(1)采用插入式貪婪解碼方式,得到完工時間最小的整體方案,再采用改進(jìn)的N6鄰域搜索方法,得到該調(diào)度方案的鄰域解集Ω。

(2)計算鄰域解集Ω中調(diào)度方案各工序的最晚開工時間Lijτ。

(3)重置各項作業(yè)的開始和完成時間,令Sijτ=Eijτ=-1(τ=1,2,3)。

(4)構(gòu)建選派作業(yè)集合φ,選定裝載或卸載作業(yè),并確定該作業(yè)的操作人員。

(5)根據(jù)式(11)、式(13)計算裝卸作業(yè)ijτ的開始時間Sijτ,如作業(yè)ijτ為裝載作業(yè),則根據(jù)式(12)計算其后續(xù)加工作業(yè)的開始時間;之后,再根據(jù)式(8)計算作業(yè)ijτ的完工時間Eijτ。

(6)判斷可解碼集合φ是否為空,若為空,則進(jìn)入步驟(7),若不為空,轉(zhuǎn)入步驟(4)。

(7)依據(jù)式(3)～式(6)計算該方案的目標(biāo)值,并更新外部檔案P。

(8)若鄰域解集Ω均已進(jìn)行人員選派,則解碼過程結(jié)束,否則轉(zhuǎn)入步驟(3)。

2.4 改進(jìn)的N6鄰域搜索方法

采用N6鄰域搜索方法對第一階段解碼形成的整體調(diào)度方案進(jìn)行鄰域搜索。該鄰域搜索方法將關(guān)鍵路徑塊內(nèi)的工序移至塊首工序前或塊尾工序后,創(chuàng)造出更多鄰域解,為探索更大的有效解空間提供可能。N6鄰域解不能保證最大完工時間最小化,如圖3所示,將M2的關(guān)鍵路徑中的工序O12移至塊首工序O22前,O24后移,使整體調(diào)度方案的完成時間延長。因此,本文對N6鄰域搜索方法進(jìn)行完善,使其更加高效地生成多種鄰域解。

圖3 N6鄰域可行性分析

設(shè)塊首工序為Ouv和塊尾工序為Oxy,Obc是Ouv的設(shè)備緊前工序,Ode是Oxy的設(shè)備緊后工序,現(xiàn)將塊內(nèi)工序Oij移至塊首工序Ouv前或塊尾工序Oxy后,Aij為工序Oij的加工時間,其中,u、x、b、d為工件編號,u,x,b,d∈{1,2,…,n};v、y、c、e為工序編號,v,y,c,e∈{1,2,…,m}。

首先,為保證塊首工序Ouv前和塊尾工序Oxy后的設(shè)備有空閑時間,使Oij移動后的關(guān)鍵路徑塊可以整體前移,縮短完成時間,則將Oij移至Ouv前,需滿足

Suv>max(Ebc,Eij-1)

(14)

將Oij移至Oxy后,需滿足

Exy

(15)

其次,為使Oij移動后不產(chǎn)生更長的關(guān)鍵路徑,則將Oij移至Ouv前,此時需滿足

Aij-(Suv-max(Ebc,Eij-1))<

min(Li′j′-Si′j′|i′,j′∈Φ1)

(16)

將Oij移至Oxy后,此時需滿足

Aij-(min(Sde,Sde+1)-Exy)<

min(Si′j′+1-Ei′j′|i′j′∈Φ2)

(17)

式中,Φ2為工序Oij與Oxy間的所有工序i′j′組成的集合;i′為工件編號,i′∈{1,2,…,n};j′為工序編號,j′∈{1,2,…,m}。

以式(16)為例,公式左邊表示Oij移至Ouv前會使Ouv至Oij前的所有工序i′j′(由集合Φ1表示)后移(延遲)的時間,公式右邊表示集合Φ1中工序最晚開始時間與最早開始時間之差的最小值。

2.5 基于網(wǎng)格的非支配解選擇

2.5.1非支配解集更新

對于新解α,若滿足?k∈{1,2,3,4},Fk(α)≤Fk(β)∧?k∈{1,2,3,4},Fk(α)Fk(α),β∈Ρ,則將解β從Ρ刪除。

2.5.2基于網(wǎng)格的非支配解排序與選擇

利用網(wǎng)格對外部檔案中的非支配解集進(jìn)行劃分,并按非支配解在網(wǎng)格中的多樣性指標(biāo)進(jìn)行排序,再采用錦標(biāo)賽方法選擇非支配解參與種群進(jìn)化,提高種群的多樣性。具體的網(wǎng)格排序與選擇過程如下。

首先,計算第k維網(wǎng)格的寬度:

(18)

其次,計算非支配解α在第k維目標(biāo)上的網(wǎng)格坐標(biāo):

(19)

然后,依據(jù)下式計算外部檔案中非支配解的多樣性排序指標(biāo):

(20)

圖4 基于網(wǎng)格的非支配解排序

最后,按G(α)對非支配解進(jìn)行降序排序,采用錦標(biāo)賽法隨機(jī)確定參與交叉操作的非支配解。

2.6 人員選派

第二階段解碼中,針對裝卸作業(yè)的人員選擇過程和啟發(fā)式信息設(shè)計的步驟如下:

(1)將緊前作業(yè)已經(jīng)調(diào)度而本作業(yè)未調(diào)度的裝卸作業(yè)放入可調(diào)度作業(yè)集合φ。

(2)選取調(diào)度作業(yè)集合φ中最晚開始時間Lijτ與最早可開始時間Sijτ差值最小的作業(yè)作為下一個選派作業(yè)ijτ*。

(3)針對作業(yè)ijτ*,采用賭輪法,依據(jù)

(21)

μa=|max(xa,hgρxa,ijτya,hgρ,ijτEhgρ)-max(xa,ijτSijτ)|

(22)

式中,μa為等待操作人員a的時間。

選定操作人員a*。式(21)可以使等待時間短和作業(yè)效率高的人員獲得更大的選擇概率。

2.7 GFEAGA實現(xiàn)過程

為便于應(yīng)用,本算法僅需設(shè)定種群規(guī)模N和算法終止條件(進(jìn)化代數(shù)PS)。算法的實現(xiàn)步驟如下:

(1)設(shè)定算法參數(shù),并令迭代標(biāo)識ω=0。

(2)種群初始化。依據(jù)編碼規(guī)則,隨機(jī)生成N個個體作為初始種群,并對其進(jìn)行解碼,計算個體目標(biāo)函數(shù)值,更新外部檔案。

(3)種群進(jìn)化。對于種群中的個體i:首先,從外部檔案選取個體j,構(gòu)成雙親;其次,隨機(jī)選擇交叉算子,交叉生成子代個體i′、j′;再次,任選子代個體,隨機(jī)選擇變異算子,變異生成新個體i″;最后,對子代個體i″進(jìn)行解碼,更新個體i和外部檔案。

(4)終止條件判斷。ω

3 實驗分析

以Intel CPU 2.7GHz、RAM 8G為硬件環(huán)境,以Windows 10+ Visual Studio Code 1.74.2為軟件平臺,以作業(yè)車間調(diào)度測試集LA1～LA40[18]為測試對象,設(shè)計了3種對比實驗:①基于IBM CPLEX 12.6.3求解器開發(fā)了CPLEX_CP(以下簡稱C-CP)求解模型,并將其與簡化的GFEAGA進(jìn)行對比實驗,以驗證GFEAGA求解的高效性;②與多目標(biāo)優(yōu)化算法NSGA-Ⅱ[19]和MOEA[20]進(jìn)行對比實驗,以驗證GFEAGA對多目標(biāo)問題的求解能力;③通過相似性與學(xué)習(xí)率的交叉實驗,對比分析不同相似性與學(xué)習(xí)率對調(diào)度方案和人員作業(yè)的影響,以驗證本研究問題的應(yīng)用效果。

由于本研究問題涉及人員和設(shè)備的多種因素,所以需對LA1～LA40測試數(shù)據(jù)進(jìn)行相應(yīng)的完善。其中,設(shè)備間行走時間、作業(yè)相似性和裝卸時間分別取[0.1,0.4]、[0,1]和[1,4]內(nèi)均勻分布的隨機(jī)數(shù),并要求任意3個設(shè)備間的行走時間滿足三角不等式,測試集中,原加工時間扣除裝卸時間后作為設(shè)備加工時間。與測例集中設(shè)備對應(yīng),隨機(jī)生成相應(yīng)人員的學(xué)習(xí)因子如表4所示。

表4 人員學(xué)習(xí)因子對應(yīng)表

3.1 與C-CP算法的對比實驗及分析

C-CP采用約束滿足問題的求解方法,在以最大完工時間為目標(biāo)的車間調(diào)度問題上表現(xiàn)出良好性能,因此通過與其對比來了解GFEAGA的求解性能。

3.1.1參數(shù)調(diào)整

3.1.2結(jié)果分析

設(shè)GFEAGA算法種群N為50,將相同求解時間的條件下10次運行的平均結(jié)果與C-CP算法的求解結(jié)果進(jìn)行對比。各測例對比詳見表5,其中,Cmax為最大完工時間,T為運行時間。

表5 GFEAGA與C-CP實驗結(jié)果

LA1～LA40測試數(shù)據(jù)按次序每5個為一組,分別代表了不同的問題規(guī)模(n×m)。8組測例(測例1-5、測例6-10、…、測例36-40)的具體規(guī)模分別為10×5、15×5、20×5、10×10、15×10、20×10、30×10、15×15。表5中,加粗部分為相對優(yōu)解。從求解效果分析:①對中小規(guī)模問題(LA1～LA14),C-CP與GFEAGA沒有明顯差異;②較大規(guī)模問題(LA15～LA40)上,GFEAGA明顯優(yōu)于C-CP;③從求解均值看,GFEAGA比C-CP的求解效果更好。改進(jìn)的N6鄰域搜索方法使GFEAGA在保持較高求解效率的情況下,獲得相對更好的求解效果。

3.2 多目標(biāo)求解的有效性分析

3.2.1參數(shù)設(shè)置

為驗證網(wǎng)格技術(shù)對外部檔案中非支配解的保留、評價與選擇方法的有效性,以多目標(biāo)求解算法NSGA-Ⅱ和MOEA為對比對象,采用非支配解比例(ratio of nondominated solutions,R-NDS)[21]與超體積(hypervolume,HV)[22]進(jìn)行算法有效性評價。R-NDS反映算法求得非支配解數(shù)量的占優(yōu)性,R-NDS值越大,算法求得的非支配解越多。HV反映非支配解集空間分布的多樣性,HV越大,非支配解集的空間分布越好。將LA1～LA40作為測試數(shù)據(jù)集,種群規(guī)模和進(jìn)化代數(shù)均設(shè)置為50,取10次運行的平均結(jié)果進(jìn)行比較。

R-NDS和HV的計算過程如下:①對3種算法的非支配解集進(jìn)行合并,模擬近似Pareto前沿;②以近似Pareto前沿為參照,計算各算法相應(yīng)的指標(biāo)。由表6可見:①從R-NDS看,所有測例中的 GFEAGA較NSGA-Ⅱ和MOEA優(yōu)勢明顯,R-NDS的平均勝出率分別為557%和608%,表明GFEAGA能求解數(shù)量更多的非支配解;②從HV看,GFEAGA在絕大多數(shù)測例中的表現(xiàn)優(yōu)于NSGA-Ⅱ和MOEA,HV的平均勝出率為9%,表明GFEAGA求得Pareto解集分布的多樣性方面更有優(yōu)勢。為更好展示3種算法非支配解集空間分布性,以LA3為例,給出了3種算法在4個目標(biāo)解集的平行坐標(biāo)圖(圖5)。圖5中標(biāo)注了3中算法求得的Pareto解數(shù),展示各目標(biāo)最小值及解集分布情況。

(a)GFEAGA(250個解)

表6 多目標(biāo)實驗結(jié)果指標(biāo)

3.2.2運行結(jié)果分析

GFEAGA能輸出更多有效解,在各目標(biāo)上分布較均勻且均可以達(dá)到最優(yōu)值。根據(jù)以上結(jié)果分析GFEAGA優(yōu)于MOEA與NSGA-Ⅱ的原因:①改進(jìn)的鄰域搜索方法提高了領(lǐng)域解集的質(zhì)量,為生成多樣化Pareto解奠定了基礎(chǔ);②人員選派的啟發(fā)式信息均衡了人員負(fù)荷,減少了人員的等待浪費,有助于相關(guān)人員優(yōu)化目標(biāo)的實現(xiàn);③外部檔案有利于保留更多的非支配個體,保證了非支配解集的多樣性;④采用網(wǎng)格技術(shù)進(jìn)行非支配解集的劃分及個體選擇提高了優(yōu)良父代的選擇率。

3.3 相似性和學(xué)習(xí)率對調(diào)度效果的影響分析

3.3.1實驗設(shè)置

為驗證相似性和學(xué)習(xí)率對本研究問題目標(biāo)值及人員利用率的影響,以LA1為實驗案例,分別將相似性的取值區(qū)間[-1,0]和學(xué)習(xí)率的取值區(qū)間[0,1]做10等分后進(jìn)行交叉實驗。每組實驗10次,通過目標(biāo)F1～F3的最小下界分析相似性和學(xué)習(xí)率對本研究問題求解影響及規(guī)律。

3.3.2結(jié)果分析

圖6反映相似性和學(xué)習(xí)率變化時,F1～F3的最小下界的變化情況。其中,圖6a、圖6b反映了相似性和學(xué)習(xí)率對F1、F2下界有明顯且規(guī)律的影響,表明在優(yōu)化總完工時間和人員總負(fù)荷時,相似性和學(xué)習(xí)率應(yīng)得到重視;圖6c反映了相似性和學(xué)習(xí)率與F3的下界變化具有相關(guān)性,表明在優(yōu)化最大人員負(fù)荷時,相似性和學(xué)習(xí)率也是不可忽視的因素。

(a)F1的下界變化

因此:①“一人多機(jī)”模式下,相似性和學(xué)習(xí)率使制造系統(tǒng)在壓縮工期、平衡工作負(fù)荷等方面具備更靈活的資源配置能力;②該生產(chǎn)模式下,重視作業(yè)相似性并加強(qiáng)人員的選派,是制定精確的生產(chǎn)計劃、合理利用人力資源、平衡人員工作負(fù)荷的重要基礎(chǔ);③該生產(chǎn)模式下,GFEAGA可以兼顧作業(yè)相似性和人員學(xué)習(xí)差異,為決策者提供更多調(diào)度方案選擇。

4 結(jié)論

為滿足多樣化市場需求,在“一人多機(jī)”生產(chǎn)模式下,提出了考慮相似學(xué)習(xí)效應(yīng)的多目標(biāo)作業(yè)車間調(diào)度模型和求解效率高且綜合性能好的基于網(wǎng)格篩選外部檔案的遺傳算法。研究表明:作業(yè)相似性和學(xué)習(xí)效應(yīng)對人員操作時間均有明顯影響,應(yīng)成為提高生產(chǎn)效率、節(jié)約人力資源值得關(guān)注的因素;對于該類復(fù)雜性更高的調(diào)度問題,基于網(wǎng)格篩選外部檔案的遺傳算法具有很好的局部搜索能力和離散多目標(biāo)問題搜索能力,可以為企業(yè)提供更多靈活實用的調(diào)度方案。