考慮工人數量配置優化的柔性作業車間調度問題研究

梁向檁 宋豫川 雷 琦 孫愛紅

重慶大學機械傳動國家重點實驗室,重慶,400044

0 引言

制造業是立國之本、興國之器、強國之基。我國的制造業發展已經邁入了由中國制造到中國智造的階段。隨著個性化生產的需求增加,多品種、小批量生產的產值大約占到了機械工業總產值的80%[1]。提高生產的柔性是企業應對動態多變的市場需求的有效方式,因此,柔性作業車間調度受到了學者們的廣泛關注。盡管制造業的發展方向是設備全自動化生產,但就目前而言,工人在制造過程中仍不可或缺。此外,制造行業競爭激烈,人工成本也快速上升,成本的控制對于提升企業的競爭力至關重要。在此背景下,從降低成本的角度,確定參與制造任務的不同技術水平工人的數量及最優的生產調度方案,對制造企業的發展具有重大的實際意義。

柔性作業車間調度問題(flexible job-shop scheduling problem,FJSP)在作業車間調度問題的基礎上增加了機器選擇的柔性。工人在實際生產中也是重要的資源,同時考慮機器與工人資源的柔性作業車間調度問題被稱為雙資源柔性作業車間調度問題(dual resource constrained flexible job-shop scheduling problem,DRCFJSP)。郭鵬等[2]以最小完工時間為目標,考慮工人的操作效率差異,采用基于工序排序、機器選擇、工人指派三層編碼的Jaya算法進行求解。董海等[3]同時考慮多能工和并行工序順序柔性,以最大完工時間、總能耗、工人總加工時長方差最小為目標,設計了四段編碼的離散回溯搜索算法進行求解。MENG等[4]在DRCFJSP中考慮了能耗目標,并采用了通過開關機減少能耗的策略。張洪亮等[5]從交貨期、節能的角度,設計了一種基于三階段解碼方式的改進NSGA-Ⅱ算法對DRCFJSP進行優化。孫愛紅等[6]不僅考慮了工人操作效率的異質性,還考慮了工人操作合格率的異質性,并將機床分為普通機床與數控機床,以完工時間和加工質量為目標,設計了一種兩級嵌套蟻群算法進行優化。TAN等[7]研究了具有工人疲勞意識的DRCFJSP,以最小化最大完工時間和最大工人疲勞值為目標,通過改進的NSGA-Ⅱ算法求解。周亞勤等[8]在DRCFJSP的基礎上,考慮關鍵工序需要特定設備和人員的約束,并將關鍵設備利用率納入了優化目標。PENG等[9]研究了包括工件運輸時間和工人學習效應約束的DRCFJSP,并提出了一種多目標帝國競爭算法進行求解。綜上可知,國內外已有部分學者在DRCFJSP上進行了擴展,包括考慮節能、工人疲勞、學習效應、工件質量等。但據筆者所知,有關DRCFJSP的研究幾乎均假定工人的數量是確定的,目前幾乎沒有相關文獻考慮不同的工人數量配置方案對調度結果的影響。

制造企業本質上是以盈利為目的的生產經營組織,在保質保量的前提下降低成本是制造企業的現實目標。目前,已有一些學者基于成本的視角考慮在FJSP及其擴展模型的目標函數中加入成本指標。朱偉等[10]考慮只與機器選擇有關的加工成本,設計了一種改進遺傳算法求解帶有工件移動時間的FJSP。劉彩潔等[11]建立了分時電價下的FJSP模型,并在目標函數中考慮了能耗成本,采用動態控制參數的NSGA-Ⅱ算法進行優化。WU等[12]將提前/拖期懲罰成本考慮至FJSP中,并通過基于3D析取圖的混合蟻群算法進行求解。ZHENG等[13]研究了允許工序重疊的FJSP,以工序重疊成本和最大完工時間為目標進行了優化。李佳路[14]在研究分布式FJSP時,考慮了原料到工廠、工廠內部、工廠到成品倉庫的運輸成本,并設計了多種群人工蜂群算法求解。肖華軍[15]在求解多目標的DRCFJSP時考慮了總成本,包括工人加工成本與機床成本。由上述文獻可以看出,國內外學者在研究FJSP相關問題時已從工件、機器、工人等角度考慮了成本因素,但極少有學者同時考慮拖期懲罰成本與工人成本,并且考慮工人成本的文獻基本上只考慮了工人的加工成本,而現實生活中,工人的工資大多以基礎工資加績效工資的形式構成。

綜上所述,在DRCFJSP中幾乎沒有學者考慮工人的數量配置優化,并且在考慮工人成本時,幾乎沒有學者從符合實際的基礎工資加績效工資的角度考慮,因此,本文在DRCFJSP的基礎上考慮不同技術水平工人的數量配置優化,建立了以最小化總成本為目標的混合整數規劃模型,其中,總成本包括拖期懲罰成本和基礎工資加績效工資形式的工人成本。此外,雖然已有學者運用教學優化算法求解車間調度問題[16-18],但少有學者將其運用在DRCFJSP中。鑒于此,本文設計了一種改進的教學優化(improved teaching-learning-based optimization,ITLBO)算法對研究對象進行求解,決策出各種技術水平工人的最優數量及工人、設備資源約束下的最優生產調度方案,以實現總成本最小化地完成制造任務。通過對不同規模的10組算例進行測試,并與流行的遺傳算法(GA)、粒子群優化(PSO)算法對比,驗證了本文所提出的ITLBO算法的可行性與有效性。

1 問題描述及數學模型

1.1 問題描述

柔性作業車間中存在m(M1,M2,…,Mm)臺機器,有w(W1,W2,…,Ww)名工人可進行作業,工人的技術水平可分為k(K1,K2,…,Kk)種,如:初級、中級、高級,假設同一技術水平的工人無差異,不同技術水平的工人存在差異,現需對n(J1,J2,…,Jn)個工件進行生產,每個工件Ji包含vi(i=1,2,…,n)道工序。加工每道工序Oij(i=1,2,…,n;j=1,2,…,vi)的可選機器集合為Mij,Mij?M,操作機器q(q∈Mij)完成工序Oij加工的可選工人所屬技術水平集合為Kijq,Kijq?K,選擇不同的機器、不同技術水平的工人加工工序Oij的加工時間不同。此外,不同技術水平工人的成本也不同。考慮工人數量配置優化的DRCFJSP是在同時滿足工序約束、機器約束、工人約束的前提下,確定最優工人數量配置方案(即各技術水平工人的實際數量),并為各道工序確定最優機器與工人組合以及最優開工時間。本文的目標為最小化總成本,包括拖期懲罰成本和工人成本,其中,工人成本由基礎工資成本與績效工資成本組成。為了簡化問題,本文給出了如下假設:①所有工件均在零時刻已經到達,所有機器與工人也均在零時刻準備就緒;②每個工件均需嚴格按照工藝順序進行加工,不同工件間的加工順序沒有約束;③機器可加工不止一道工序,工人也可操作不止一臺機器;④同一時刻下,一臺機器只能加工一道工序,工人也只能操作一臺機器;⑤各工件之間無優先級,且加工過程中不允許搶占;⑥準備時間、移動時間包含在加工時間中,可忽略不計;⑦各個技術水平的工人數量有上限,即某一技術水平的工人數量不能超過給定的最大值;⑧工序在不同機器上加工的成本差異相比于不同調度方案引起的拖期懲罰成本差異、工人成本差異較小,可忽略。

1.2 數學模型

本文在普通DRCFJSP數學模型[2,6,15]的基礎上,新增不同技術水平工人的具體數量為決策變量,并設置目標函數為總成本,包括工件拖期懲罰成本、基礎工資加績效工資形式的工人成本。為清晰地表述所構建的數學模型,本文涉及的符號及含義如表1所示。

表1 符號及含義

基于本文給出的假設及表1中的符號變量,建立的數學模型如下:

f=min(CT)

(1)

CT=CD+CW

(2)

(3)

(4)

約束條件如下:

(5)

(6)

Tqr+L(Xijqr-1)≤Sij

(7)

Sgh+L(1-δijghq)≥Eij

(8)

Tqr+L(1-εq′qr)≥Tq′r

(9)

(10)

0≤Hs≤As

(11)

(12)

(13)

Sij≥0Tqr≥0tijqr≥0

(14)

其中,式(1)表示優化目標為最小化總成本;式(2)～式(4)分別表示車間調度的總成本、拖期懲罰成本、工人成本;式(5)表示工序的加工不允許搶占;式(6)表示同一工件的各工序間存在先后順序約束;式(7)表示每道工序均需在對應的機器和工人準備好后才能開工;式(8)和式(9)表示同一時刻下工人只能操作一臺機器對工序進行加工;式(10)表示每道工序只能選擇一臺機器和一名工人進行加工;式(11)表示每種技術水平工人的決策數量應不超過給定的最大數量;式(12)表示工人的決策總數量為各種技術水平工人的決策數量之和;式(13)表示對于任意一道工序,至少有一名工人滿足加工條件;式(14)表示零時刻時,工件已經全部到達,工人、機器全部準備就緒,加工時間大于0。

2 改進教學優化算法設計

2.1 算法總體流程

教學優化(TLBO)算法是RAO等[19-20]基于模擬教學過程提出的一種群體智能優化算法,進化原理為教師解引導學生解向最優解所在的空間收斂以及學生解之間相互學習以避免算法快速陷入局部最優。傳統TLBO算法適用于連續型問題的求解,且在局部搜索能力、保持種群多樣性方面存在不足。針對本文研究問題的特點,對傳統TLBO算法進行改進,采用基于工人數量配置、工序排序、機器選擇的三層編碼方案。教師階段采用變鄰域搜索(variable neighborhood search,VNS)算法進行教師自學。學生階段以概率選擇向老師學習或向其他學生學習,并以Metropolis準則判斷是否接受新解。此外,學生小概率地進行自學。

本文設計的ITLBO算法總體流程如圖1所示,算法的具體步驟如下:

圖1 改進教學優化算法流程圖

(1)根據設置的種群規模,采用混合啟發式方法初始化種群。

(2)對種群個體進行解碼,得到每個個體的適應度值。由于調度目標為總成本最小,因此,適應度值取總成本的相反數。

(3)將個體按照適應度值降序排序,根據教師解占比系數a%,取前a%的個體作為教師解,其余個體為學生解。

(4)教師自學。采用VNS算法對教師解進行局部搜索。

(5)學生向他人學習。對于每個學生,產生一個0-1的隨機數P,若P小于設定的學習方式概率系數Pc,則任選一名教師對該學生進行教學;否則,該學生任選一名同學互相學習。兩種向他人學習的方式均通過交叉算子來實現,并以Metropolis準則判斷是否接受新解。

(6)學生自學。對于每個學生,產生一個0-1的隨機數P,若P小于設定的學生自學概率系數Pm,則通過變異算子來實現該學生的自學。

(7)判斷是否滿足終止條件,若滿足,則結束循環并輸出最優解;否則,跳轉至步驟(2)。其中,小規模算例收斂速度快,終止條件選擇為最大迭代次數;大規模算例可能收斂速度較慢,終止條件選擇為最大最優解不變次數。

2.2 編碼與解碼

考慮工人數量配置優化的DRCFJSP模型,需要同時解決工人數量配置、工序排序、機器選擇、工人選擇四個子問題。目前,學者們在解決車間調度問題時,采取的編碼方式可分為兩類:全解空間編碼、部分解空間編碼。全解空間編碼雖能實現在整個解空間內搜索,但對于解空間極大的模型,算法的效果通常不理想。相反,采用部分解空間編碼容易保證算法的收斂性與穩定性[21]。因此,為了綜合考慮算法的搜索空間與收斂性,本文采用基于工人數量配置(WNA)、工序排序(OS)、機器選擇(MS)的三層部分解空間編碼。圖2展示了一個編碼實例,WNA行的長度等于工人技術水平數,從左往右指代的工人技術水平由低到高,各數字表示相應技術水平工人的數量;OS行的長度等于總工序數,各數字表示工件號,各數字出現的次數表示工序號;MS行的長度等于總工序數,從左往右依次指代J1至Jn的相應工序,各數字表示相應工序可選機器集中的順序號,而非機器號。

圖2 編碼實例

編碼中未涉及的工人選擇通過在解碼過程中使用啟發式規則確定。考慮到問題的優化目標,采用插入式貪婪解碼以獲得活動調度。考慮工人數量優化配置的DRCFJSP的解碼流程如圖3所示,具體的解碼步驟如下:

圖3 解碼流程圖

(1)通過WNA編碼獲取各技術水平工人的數量,從左往右依次讀取MS編碼以獲取機器選擇矩陣。其中,機器選擇矩陣各元素表示各工序選擇的機器號,而非可選機器集中的順序號。

(2)對WNA編碼進行可行性檢查,若存在某道工序可選工人集為空集,則隨機選擇一種可加工該工序的工人類型,令該類型的技術水平工人數為1,直至滿足所有工序的加工要求。

(3)對修正數量后的所有工人進行編號,按照技術水平由低到高的順序依次令工人編號為1,2,…,U。

(4)從左往右依次讀取OS編碼,結合機器選擇矩陣得到工序的加工機器號與可選加工工人集。采用間隙擠壓法確定各可選加工工人最早完成工序加工的時間,選擇完成時間最早的工人加工此工序,若最早能完成的工人不唯一,則選擇其中工人編號最小的工人以降低工人績效成本。

(5)檢查所有工人的加工時間表,若存在某名工人的加工時間表為空(即該工人未加工任何工序),則將WNA編碼中對應的技術水平的工人數減1,直至遍歷完所有工人。

(6)按照式(2)～式(4)計算總成本。

本文所設計的解碼方法既考慮了盡早完工以降低拖期懲罰成本和工人基礎成本,又在保證盡早完工的同時考慮了選擇技術水平較低的工人以降低工人績效成本。通過選擇最早完工的工人還可達到均衡工人負荷、識別勞動力過剩的效果。

2.3 初始化

由于本文研究的問題是FJSP的擴展,算法的搜索空間更為龐大,因此初始解的質量對TLBO算法求解的質量和速度起著非常關鍵的作用。張國輝[22]從機器負荷盡可能平衡的角度出發,針對機器選擇提出了一種全局選擇(GS)、局部選擇(LS)、隨機選擇(RS)相結合的初始化方法。趙詩奎等[23]在機器選擇初始化時,不考慮工序的順序約束,從最小化極限調度完工時間的角度,提出了改進全局選擇(IGS)、改進局部選擇(ILS)、RS相結合的初始化方法。針對本文的編碼特性,WNA和OS部分采用隨機初始化方法,MS部分采用GS、IGS、LS、ILS、RS相結合的混合初始化方法。由于初始化階段并未指定工序的工人選擇,因此在MS部分初始化時,工序在指定機器上的加工時間由可選工人加工時間的平均值代替。結合文獻[22-23]的建議及實驗測試,最終選定GS、IGS、LS、ILS、RS各自的占比分別為0.3、0.3、0.15、0.15、0.1。

2.4 教師階段

標準TLBO算法設置一個全局最優解為教師,這種設置方式可能會導致種群的平均適應度值增大緩慢且種群多樣性過早丟失。為克服此弱點,本文在整個群體中選擇最優的前a%個個體作為教師。由于教師解的質量較高,采用全局搜索不利于探索到更高質量的解,因此,通過變鄰域搜索實現教師的自學。鄰域結構的設計是變鄰域搜索的關鍵。基于工人基礎成本、拖期懲罰成本與時間指標密切相關,對關鍵路徑上的關鍵工序進行擾動有利于縮短完工時間,因此,本文以關鍵工序為對象設計鄰域結構。

關鍵路徑是指滿足工序順序約束的條件下獲得的最長加工路徑,關鍵路徑中包含的工序即為關鍵工序。針對本文所研究問題的特點,設計了如下兩種鄰域結構:

(1)鄰域結構一。隨機選擇兩道不屬于同一工件的工序,其中至少一道工序為關鍵工序,交換這兩道工序,但不改變工序的加工機器。

(2)鄰域結構二。隨機選擇一道關鍵工序,將其加工機器更換為其他可選機器。

需注意的是,關鍵路徑可能不止一條,考慮到盡可能優化總成本,本文選擇從后往前搜尋的方式確定出一條關鍵路徑進行局部搜索。具體步驟如下:

(1)找到最后完工的工序,若不止一個,則選擇所屬工件拖期懲罰成本最高的工序作為臨時工序,并放入關鍵路徑。

(2)判斷臨時工序的同一工件緊前工序的完成時間是否與臨時工序的開始時間相同,若相同,則將其同一工件緊前工序作為臨時工序,并放入關鍵工序;否則,按照同樣的方法依次判斷臨時工序的同一機器緊前工序、同一工人緊前工序。

(3)判斷臨時工序的開始時間是否為0,若為0,則結束;否則,跳轉至步驟(2)。

2.5 學生階段

本文所設計的學生階段的學習方式可分為向他人學習與自學兩種。在向他人學習時,標準TLBO算法既包括教師教學,又包括學生互學,但考慮到本文算法在教師階段已增加了局部搜索算法,為了減少算法整體的計算時間,本文算法設計為當一名學生向他人學習時,以Pc的概率選擇任意一名教師教學,否則選擇任意一名同學互相學習。為了保證算法的收斂速度,學生解應更高概率地選擇教師教學,因此,Pc的取值應大于0.5。考慮到離散問題的特性,本文選用交叉算子實現向他人學習,其中,WNA、MS編碼采用均勻交叉(UX),OS編碼采用基于工件優先順序的交叉(POX),如圖4所示。

圖4 學生向他人學習算子

標準TLBO算法在教師教學、學生互學后會保留適應度更高的解,雖然此方法可以保證更優的個體進入下一代,但也容易導致算法陷入局部最優。為了克服這一缺陷,本文選擇交叉后適應度高的個體作為臨時個體,以Metropolis準則判斷是否接受臨時個體,Metropolis準則的計算表達式如下:

(15)

式中,df為臨時個體與原始學生目標函數值的差值;kB為溫度衰減系數,本文取kB=0.9;T0為初始溫度,考慮到不同算例的df數量級可能存在較大差異,本文將T0取為初代群體中最大目標值差(即最大目標值與最小目標值的差值)的10倍。

學生完成向他人學習后,以Pm的概率進行自學,本文選用變異算子實現學生自學,其中,對于WNA、MS編碼,隨機選中l個位置,將其編碼隨機更改為可選范圍內的其他值,OS編碼采用插入變異,如圖5所示。

圖5 學生自學算子

3 實驗分析

本文所有測試均由Python3.7實現,計算機硬件配置為英特爾i7-7700HQ CPU(2.8 GHz)、8 GB RAM,操作系統為Windows 10。

3.1 測試算例

由于目前尚未有考慮工人數量配置優化的DRCFJSP算例,因此本文基于文獻[15]中的算例進行設計。文獻[15]中的算例考慮工人數量一定且各工人技術水平皆不相同,工人成本方面只考慮了工人加工成本。基于此,本文將文獻[15]算例中的工人加工時間數據整合為2或3種技術水平工人的加工時間數據,具體為:將加工成本相近的多名工人的加工時間采用求平均值的方式整合為一種技術水平工人的加工時間。各種技術水平工人的基本成本、績效成本在[10,70]范圍內隨機生成,且滿足技術水平高的工人的成本更高。各種技術水平工人的最大數量在[2,5]范圍內隨機生成,結合實際,考慮為技術水平較低的工人的最大數量相對較多。工件的交貨期采用下式計算:

(16)

其中,Zi為工件Ji的緊迫系數,在[1,1.5]范圍內隨機生成;tij為可用的機器和工人組合加工工序Oij的時間平均值。工件的單位拖期懲罰成本在[5,40]范圍內隨機生成。最終,本文生成了10個測試算例,命名為DSP-WN01-10,測試算例的詳細數據可掃描本文首頁OSID二維碼獲取。

3.2 算法參數

本文提出的ITLBO算法除了前文中已經確定的參數設定外,還需確定種群規模N、教師解占比系數a%、學習方式概率系數Pc、學生自學概率系數Pm、最大迭代次數或最大最優解不變次數Gt。若種群規模太小,會導致初始解的分布密度過低且多樣性較差,不利于對整個解空間的搜索;若種群規模太大,會導致算法運行時間明顯增加[24],因此,本文對小規模算例設定種群規模為100,對大規模算例設定種群規模為300。針對算法終止條件,考慮到隨著算例規模的增大,算法的收斂速度通常是降低的,本文對小規模算例設定最大迭代次數為100,對大規模算例設定最大最優解不變次數為100。剩余的三個參數通過正交試驗確定最優的參數組合,每個參數選擇3個水平,如表2所示。選擇L9(33)正交表進行試驗,算例選擇改編的DSP-WN02,取算法運行10次的平均總成本(average total cost,ATC)作為各種參數組合下的評價指標,計算結果如表3所示。

表2 參數水平表

表3 正交試驗表

根據表3結果繪制參數水平趨勢圖(圖6),可以看出,當a%、Pc、Pm分別取第三水平、第二水平、第一水平時,ATC最小,因此,本文最終設定a%=10%,Pc=0.8,Pm=0.05。

圖6 參數水平趨勢圖

3.3 鄰域結構有效性測試

為驗證所設計鄰域結構的有效性,在初始化方法、學生階段及算法參數保持不變的基礎上,將教師階段中變鄰域搜索的鄰域結構替換為圖5中OS、MS的變異算子,為描述方便,將此算法命名為NTLBO。將NTLBO和ITLBO兩種算法在3.1節生成的DSP-WN01-10算例中進行對比測試,對于每個算例,每種算法獨立運行10次,測試結果如表4所示。表4中加粗的部分表示更優,其中,最優工人配置表示各種技術水平工人的數量,從左往右工人的技術水平依次提高,如(3,0,1)表示工人的技術水平總共有3種,其中,初級工3人,中級工0人,高級工1人。測試結果表明,兩種算法僅在DSP-WN01小規模算例上的求解性能持平,在其余的9個測試算例中ITLBO算法取得的最優解與平均值更好。這表明本文設計的鄰域結構能有效地增強算法的局部搜索能力,并提高算法搜索更優解的概率。

表4 鄰域結構有效性測試結果

3.4 與其他算法對比測試

為進一步驗證本文所提算法的優越性,同時驗證所設計的編解碼方法、進化算子應用于不同算法框架的有效性,采用遺傳算法(GA)、粒子群優化(PSO)算法作為對比算法,對3.1節生成的DSP-WN01-10算例進行測試。對于每個算例,每種算法獨立運行10次,各算法決策出不同技術水平工人的最優數量配置及總成本最低的生產調度方案,并對算法獲取的最優解及穩定性進行分析。其中,GA、PSO算法的框架分別采用文獻[22]和文獻[25]所提出的框架。為了保證對比的公平性,兩種對比算法的初始化均采用2.3節提出的初始化方法。對比算法的關鍵參數參考文獻[22,25]的建議,如表5所示。三種算法所求出的最優解如表6所示。

表5 對比算法參數表

表6 三種算法所求的最優解

表6中加粗的部分為各個測試算例中獲取到的最優總成本、最優工人配置。從表6中可以看出,本文所設計的編解碼方法及交叉、變異算子應用于三種算法中時均能優化所建立的模型,從而驗證了編解碼方法及進化算子的有效性且通用于多種算法框架。此外,本文所設計的ITLBO算法在生成的10個測試算例中均獲得了最佳解,其余兩種算法只在最小規模算例DSP-WN01中獲得了與本文所設計算法同等效果的解,這是因為DSP-WN01算例的解空間相對較小,算法的求解難度較低,而在剩余9個算例中獲得的最優解的質量均低于本文所設計算法,這是因為算例的規模越大,算法搜索到最優解的難度也就越大。總之,就算法搜索最優解的性能而言,本文所設計算法明顯優于對比算法。

為了避免誤差的影響,且更加準確地對比三種算法的性能,本文進一步使用平均總成本(ATC)、最大總成本(maximum total cost,MTC)、總成本標準差(standard-deviation of total cost,STC)三個指標對算法性能進行分析,結果如表7所示。其中,ATC、MTC、STC分別表示算法在10次運行中獲得的最優解的平均值、最大值、標準差。

表7 三種算法的ATC、MTC、STC

表7中加粗部分為各個測試算例中ATC、MTC、STC的最優值。從表7中可以看出,本文所提的ITLBO算法在10個測試算例中ATC、MTC全部取得了3種算法中的最優值,其中,9個算例的ATC、MTC小于GA、PSO算法對應的指標值,僅在最小規模算例DSP-WN01中ITLBO算法與GA、PSO算法持平,表明相較最優解相對偏差的平均值以及悲觀情況下的求解質量來看,本文所提算法存在較大優勢,特別是在求解具有一定規模的算例時優勢明顯。就算法求解結果的標準差而言,ITLBO算法在5個測試算例的STC取得了3種算法中的最優值,其余5個算例中,也有3個算例的STC與最優值比較接近。總體而言,本文所提算法在求解考慮工人數量配置優化的DRCFJSP時性能優異且較為穩定。

為更加具體地展示3種算法在求解測試算例時的性能表現,給出了3種算法在求解小規模測試算例DSP-WN03和大規模測試算例DSP-WN10時的迭代曲線,分別見圖7、圖8。需注意的是,DSP-WN03算例的終止條件為迭代次數100次,DSP-WN10算例的終止條件為最大最優解不變次數100次。從圖7、圖8中可以看出,本文所提算法相比于GA、PSO算法,在求解小規模測試算例和大規模測試算例時,不僅取得了更優的解,并且收斂速度也更快。所提算法與對比算法在測試算例中的表現存在以上差異的主要原因可能在于所提算法嵌入了基于關鍵路徑的局部搜索算法,并且在進化過程中并沒有類似于GA中的種群選擇算子,而是通過教學過程既可以向教師解學習,也可以向其他學生解學習的方式,從而保證種群的多樣性。

圖7 DSP-WN03迭代圖

圖8 DSP-WN10迭代圖

圖9、圖10分別為所提算法在DSP-WN03、DSP-WN10測試算例中取得的最優解的調度甘特圖。

圖9 DSP-WN03甘特圖(總成本為6920,最大完工時間為38)

圖10 DSP-WN10甘特圖(總成本為241 465,最大完工時間為764)

在圖9、圖10中,調度甘特圖的上半部分為機器調度甘特圖,下半部分為工人調度甘特圖,橫坐標均為加工時間,縱坐標分別為機器號、工人代號,工人代號以[工人編號,工人所屬技術水平號]的形式表達,如圖9中的[4,3]表示第4個工人,其技術水平為第3類,即為高級工。圖中方框里的數字表示工件號,從左往右依次表示該工件的加工次序,如圖9中最左邊的紫色方框表示工件J10的第1道工序,它在機器M6上由第4個且技術水平為第3類的工人完成加工,加工開始時間為0。

4 結論

本文針對考慮工人數量配置優化的柔性作業車間調度問題進行研究,實現了集成優化不同技術水平工人的具體數量及生產調度方案。首先,在雙資源柔性作業車間調度問題(DRCFJSP)的基礎上,新增不同技術水平工人的數量配置為決策變量,建立了以最小化總成本為目標的數學模型。其次,提出了一種改進的教學優化算法,該算法采用基于工人數量配置、工序排序、機器選擇的三段式編碼表示調度解,并基于優化目標,設計了一種結合啟發式規則的貪婪插入式解碼方法;初始化階段,采用了混合啟發式初始化方法;教師階段,設計了有效的鄰域結構來提高解的質量。最后,生成了適用于本文所提模型的測試算例,測試結果驗證了所設計鄰域結構的有效性。通過與其他算法對比,進一步驗證了本文所提算法能確定不同技術水平工人的具體數量,以更低的成本完成制造任務,證明了所提算法的優越性。

本文所研究的問題在未來還有進一步的發展空間,主要包括:①由于機器、工人均對加工時間的準確性產生影響,因此在本文所提問題的基礎上進一步考慮模糊生產環境對實際生產意義重大;②在本文問題的基礎上,構建多目標優化模型;③構建在機器維護、工人請假等情況下的動態調度模型。