梁向檁 宋豫川 雷 琦 孫愛紅

重慶大學(xué)機(jī)械傳動國家重點(diǎn)實(shí)驗(yàn)室,重慶,400044

0 引言

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

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

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

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

1 問題描述及數(shù)學(xué)模型

1.1 問題描述

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

1.2 數(shù)學(xué)模型

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

表1 符號及含義

基于本文給出的假設(shè)及表1中的符號變量,建立的數(shù)學(xué)模型如下:

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

2 改進(jìn)教學(xué)優(yōu)化算法設(shè)計(jì)

2.1 算法總體流程

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

本文設(shè)計(jì)的ITLBO算法總體流程如圖1所示,算法的具體步驟如下:

圖1 改進(jìn)教學(xué)優(yōu)化算法流程圖

(1)根據(jù)設(shè)置的種群規(guī)模,采用混合啟發(fā)式方法初始化種群。

(2)對種群個體進(jìn)行解碼,得到每個個體的適應(yīng)度值。由于調(diào)度目標(biāo)為總成本最小,因此,適應(yīng)度值取總成本的相反數(shù)。

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

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

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

(6)學(xué)生自學(xué)。對于每個學(xué)生,產(chǎn)生一個0-1的隨機(jī)數(shù)P,若P小于設(shè)定的學(xué)生自學(xué)概率系數(shù)Pm,則通過變異算子來實(shí)現(xiàn)該學(xué)生的自學(xué)。

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

2.2 編碼與解碼

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

圖2 編碼實(shí)例

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

圖3 解碼流程圖

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

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

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

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

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

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

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

2.3 初始化

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

2.4 教師階段

標(biāo)準(zhǔn)TLBO算法設(shè)置一個全局最優(yōu)解為教師,這種設(shè)置方式可能會導(dǎo)致種群的平均適應(yīng)度值增大緩慢且種群多樣性過早丟失。為克服此弱點(diǎn),本文在整個群體中選擇最優(yōu)的前a%個個體作為教師。由于教師解的質(zhì)量較高,采用全局搜索不利于探索到更高質(zhì)量的解,因此,通過變鄰域搜索實(shí)現(xiàn)教師的自學(xué)。鄰域結(jié)構(gòu)的設(shè)計(jì)是變鄰域搜索的關(guān)鍵?；诠と嘶A(chǔ)成本、拖期懲罰成本與時(shí)間指標(biāo)密切相關(guān),對關(guān)鍵路徑上的關(guān)鍵工序進(jìn)行擾動有利于縮短完工時(shí)間,因此,本文以關(guān)鍵工序?yàn)閷ο笤O(shè)計(jì)鄰域結(jié)構(gòu)。

關(guān)鍵路徑是指滿足工序順序約束的條件下獲得的最長加工路徑,關(guān)鍵路徑中包含的工序即為關(guān)鍵工序。針對本文所研究問題的特點(diǎn),設(shè)計(jì)了如下兩種鄰域結(jié)構(gòu):

(1)鄰域結(jié)構(gòu)一。隨機(jī)選擇兩道不屬于同一工件的工序,其中至少一道工序?yàn)殛P(guān)鍵工序,交換這兩道工序,但不改變工序的加工機(jī)器。

(2)鄰域結(jié)構(gòu)二。隨機(jī)選擇一道關(guān)鍵工序,將其加工機(jī)器更換為其他可選機(jī)器。

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

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

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

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

2.5 學(xué)生階段

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

圖4 學(xué)生向他人學(xué)習(xí)算子

標(biāo)準(zhǔn)TLBO算法在教師教學(xué)、學(xué)生互學(xué)后會保留適應(yīng)度更高的解,雖然此方法可以保證更優(yōu)的個體進(jìn)入下一代,但也容易導(dǎo)致算法陷入局部最優(yōu)。為了克服這一缺陷,本文選擇交叉后適應(yīng)度高的個體作為臨時(shí)個體,以Metropolis準(zhǔn)則判斷是否接受臨時(shí)個體,Metropolis準(zhǔn)則的計(jì)算表達(dá)式如下:

(15)

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

學(xué)生完成向他人學(xué)習(xí)后,以Pm的概率進(jìn)行自學(xué),本文選用變異算子實(shí)現(xiàn)學(xué)生自學(xué),其中,對于WNA、MS編碼,隨機(jī)選中l(wèi)個位置,將其編碼隨機(jī)更改為可選范圍內(nèi)的其他值,OS編碼采用插入變異,如圖5所示。

圖5 學(xué)生自學(xué)算子

3 實(shí)驗(yàn)分析

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

3.1 測試算例

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

(16)

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

3.2 算法參數(shù)

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

表2 參數(shù)水平表

表3 正交試驗(yàn)表

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

圖6 參數(shù)水平趨勢圖

3.3 鄰域結(jié)構(gòu)有效性測試

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

表4 鄰域結(jié)構(gòu)有效性測試結(jié)果

3.4 與其他算法對比測試

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

表5 對比算法參數(shù)表

表6 三種算法所求的最優(yōu)解

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

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

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

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

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

圖7 DSP-WN03迭代圖

圖8 DSP-WN10迭代圖

圖9、圖10分別為所提算法在DSP-WN03、DSP-WN10測試算例中取得的最優(yōu)解的調(diào)度甘特圖。

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

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

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

4 結(jié)論

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

本文所研究的問題在未來還有進(jìn)一步的發(fā)展空間,主要包括:①由于機(jī)器、工人均對加工時(shí)間的準(zhǔn)確性產(chǎn)生影響,因此在本文所提問題的基礎(chǔ)上進(jìn)一步考慮模糊生產(chǎn)環(huán)境對實(shí)際生產(chǎn)意義重大;②在本文問題的基礎(chǔ)上,構(gòu)建多目標(biāo)優(yōu)化模型;③構(gòu)建在機(jī)器維護(hù)、工人請假等情況下的動態(tài)調(diào)度模型。