一人多機模式下考慮相似學習效應的車間調度問題

張維存 顧洪羽

河北工業大學經濟管理學院,天津,300401

0 引言

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

刀具的種類、材料、工裝卡具,以及工人學習能力的差異影響著工人的作業效率和實際的作業調度。為貼近刀具企業“一人多機”的生產環境,筆者將傳統車間調度中的工序作業細化為裝載、卸載和機器加工,考慮作業相似性和工人學習效應使裝卸時間具有的彈性,將有限的工人合理分配到裝卸任務中,通過對裝卸和加工任務的調度,盡可能縮短工時、節約人力、平衡工作負荷。

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

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

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

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

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

1 數學模型的建立

1.1 問題描述

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

表1 參數符號定義

表2 變量符號定義

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

1.2 模型建立

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

表3 決策變量符號定義

DeJong函數[4]在設定學習效應模型時考慮了自動化程度M,DeJong的學習曲線模型為

(1)

實際生產中,工人的學習效應受主觀因素和客觀因素的影響。主觀因素表現為工作經驗、學習能力等,客觀因素表現為作業相似性、現場秩序、作業指導等。調度問題中,現場秩序和作業指導等屬于背景因素,不可調度或改變;工人的學習能力差異和作業相似性可通過工人選派和作業次序調整進行優化,這樣可使調度方案更加貼合實際生產。因此,本文在DeJong學習曲線模型的基礎上進行改進。改進后的學習曲線模型

(2)

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

圖1 學習曲線模型對比

據此建立本研究模型如下:

(1)目標函數為

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)分別表示最大完工時間、工人總負荷、最大工人負荷和作業人數;式(7)表示每項裝卸作業僅由一人執行;式(8)表示裝卸及加工作業的開始與結束時間的關系;式(9)表示工人實際裝卸時間與標準時間的關系;式(10)表示工人a執行到作業ijτ時累計的作業數量;式(11)～式(13)分別表示裝載、加工和卸載作業的開始時間計算關系。

2 算法設計

2.1 問題與算法分析

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

2.2 個體編碼與進化操作

2.2.1個體編碼

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

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

圖2 兩段式編碼方式

根據基因位的工件號及編碼規則,可以推出該工序的裝卸及加工作業編號。解碼過程中,通過作業編號并關聯其加工信息,可對整個染色體進行解碼。

2.2.2進化操作

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

2.3 解碼過程

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

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

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

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

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

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

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

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

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

2.4 改進的N6鄰域搜索方法

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

圖3 N6鄰域可行性分析

設塊首工序為Ouv和塊尾工序為Oxy,Obc是Ouv的設備緊前工序,Ode是Oxy的設備緊后工序,現將塊內工序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后的設備有空閑時間,使Oij移動后的關鍵路徑塊可以整體前移,縮短完成時間,則將Oij移至Ouv前,需滿足

Suv>max(Ebc,Eij-1)

(14)

將Oij移至Oxy后,需滿足

Exy

(15)

其次,為使Oij移動后不產生更長的關鍵路徑,則將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 基于網格的非支配解選擇

2.5.1非支配解集更新

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

2.5.2基于網格的非支配解排序與選擇

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

首先,計算第k維網格的寬度:

(18)

其次,計算非支配解α在第k維目標上的網格坐標:

(19)

然后,依據下式計算外部檔案中非支配解的多樣性排序指標:

(20)

圖4 基于網格的非支配解排序

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

2.6 人員選派

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

(1)將緊前作業已經調度而本作業未調度的裝卸作業放入可調度作業集合φ。

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

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

(21)

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

(22)

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

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

2.7 GFEAGA實現過程

為便于應用,本算法僅需設定種群規模N和算法終止條件(進化代數PS)。算法的實現步驟如下:

(1)設定算法參數,并令迭代標識ω=0。

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

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

(4)終止條件判斷。ω

3 實驗分析

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

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

表4 人員學習因子對應表

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

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

3.1.1參數調整

3.1.2結果分析

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

表5 GFEAGA與C-CP實驗結果

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

3.2 多目標求解的有效性分析

3.2.1參數設置

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

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

(a)GFEAGA(250個解)

表6 多目標實驗結果指標

3.2.2運行結果分析

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

3.3 相似性和學習率對調度效果的影響分析

3.3.1實驗設置

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

3.3.2結果分析

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

(a)F1的下界變化

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

4 結論

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