考慮運(yùn)輸時(shí)間的分布式柔性作業(yè)車間綠色調(diào)度

2022-11-21 10:50張洪亮徐公杰潘瑞林

中國機(jī)械工程 2022年21期

張洪亮徐公杰鮑薔潘瑞林

安徽工業(yè)大學(xué)管理科學(xué)與工程學(xué)院，馬鞍山，243032

0 引言

在中國，制造企業(yè)消耗了全國50%以上的電能，并產(chǎn)生了至少26%的二氧化碳排放量[1]。通過研發(fā)節(jié)能設(shè)備或采用新的加工技術(shù)減小節(jié)能減排壓力的方法通常需要大量的投入，而綠色調(diào)度能在不增加企業(yè)成本的情況下有效減少碳排放并提高能源效率[2]。

隨著信息技術(shù)以及全球化的飛速發(fā)展，許多制造企業(yè)從傳統(tǒng)的單工廠模式逐漸向能降低人工成本、提高生產(chǎn)效率[3]的分布式多工廠模式轉(zhuǎn)變。分布式柔性作業(yè)車間調(diào)度問題(distributed flexible job shop scheduling problem，DFJSP)作為分布式車間調(diào)度問題的重要形式之一，重點(diǎn)關(guān)注多個(gè)柔性作業(yè)車間類型的工廠協(xié)同生產(chǎn)。現(xiàn)在對該問題的研究主要分為單目標(biāo)DFJSP和多目標(biāo)DFJSP。單目標(biāo)DFJSP主要以完工時(shí)間為優(yōu)化目標(biāo)，對應(yīng)研究中，GIOVANNI等[4]設(shè)計(jì)了一種包含局部搜索策略的遺傳算法；LIU等[5]將概率融入實(shí)參數(shù)編碼方法，設(shè)計(jì)了一種改進(jìn)的遺傳算法；吳銳等[6]提出一種改進(jìn)的人工蜂群算法；MENG等[7]提出了4種混合整數(shù)線性規(guī)劃模型和1種約束規(guī)劃模型。對于多目標(biāo)DFJSP，吳秀麗等[8]設(shè)計(jì)了一種改進(jìn)的差分進(jìn)化算法來優(yōu)化總成本和提前/延期懲罰；LI等[9]設(shè)計(jì)了一種基于Pareto的混合禁忌搜索算法來優(yōu)化完工時(shí)間、機(jī)器負(fù)荷和提前/延期懲罰。

上述研究存在以下不足：①要求同一工件的所有工序必須在同一工廠內(nèi)完成，沒有考慮工件在工廠之間的轉(zhuǎn)移。實(shí)際上，分布式生產(chǎn)系統(tǒng)中，一些工件可能在不同的工廠加工。②要求工件在前道工序加工完成后立即執(zhí)行下一道工序，忽略了工序之間的運(yùn)輸時(shí)間。實(shí)際上，工件在工序之間流轉(zhuǎn)需要運(yùn)輸時(shí)間，且加工時(shí)間和運(yùn)輸時(shí)間之間有較強(qiáng)的耦合關(guān)系。③主要關(guān)注時(shí)間相關(guān)的目標(biāo)且以單目標(biāo)為主，沒有考慮能耗相關(guān)的目標(biāo)。隨著綠色制造的推進(jìn)，在生產(chǎn)調(diào)度決策中考慮與能耗相關(guān)的目標(biāo)變得至關(guān)重要。

綜上所述，考慮運(yùn)輸約束的DFJSP研究具有重要意義，盡管一些學(xué)者在單個(gè)工廠的車間調(diào)度問題中考慮了運(yùn)輸時(shí)間[1，10-13]，但考慮運(yùn)輸時(shí)間的DFJSP研究還很少。此外，尚未有學(xué)者在DFJSP的研究中考慮能耗相關(guān)目標(biāo)。因此，本文以考慮運(yùn)輸時(shí)間的分布式柔性作業(yè)車間綠色調(diào)度問題(distributed flexible job shop green scheduling problem with transportation time，DFJGSPT)為研究對象，建立最小化完工時(shí)間和總能耗的混合整數(shù)規(guī)劃模型，并設(shè)計(jì)一種改進(jìn)的非支配排序遺傳算法(improved non-dominated sorting genetic algorithm Ⅱ，INSGA-Ⅱ)。通過測試45個(gè)算例，以及與常用的多目標(biāo)進(jìn)化算法的對比來驗(yàn)證本文提出的INSGA-Ⅱ的有效性。

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

1.1 問題描述

DFJGSPT可以描述為：N個(gè)工件需要在F個(gè)類型為柔性作業(yè)車間的分布式工廠內(nèi)進(jìn)行加工。每個(gè)工件有ni道工序，每個(gè)工廠有Mf臺(tái)機(jī)器。工件需要通過運(yùn)輸工具在工廠以及機(jī)器之間運(yùn)輸。工件的加工時(shí)間，工件在機(jī)器、工廠間的運(yùn)輸時(shí)間，以及機(jī)器的相關(guān)能耗信息已知。調(diào)度目標(biāo)為最小化最大完工時(shí)間和總能耗。假設(shè)：①所有工件和機(jī)器0時(shí)刻可用；②每臺(tái)機(jī)器同一時(shí)刻只能加工一道工序；③每個(gè)工件同一時(shí)刻只能在一臺(tái)機(jī)器上加工；④不考慮中斷情況；⑤同一工件不同工序之間有順序約束；⑥有足夠的運(yùn)輸工具完成工件的轉(zhuǎn)移；⑦不考慮裝卸載時(shí)間。

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

基于以上描述可得DFJGSPT的數(shù)學(xué)模型：

minCmax=min(max(Ci))

(1)

minTEC=min(PE+TE+IE)

(2)

(3)

(4)

(5)

αilk+βifu≤1

(6)

cijkf=sijkf+pijkfxijkf

(7)

cijkf≥cghkf+pijkf-M(1-yijghkf)

(8)

(9)

(10)

(11)

式中，Cmax為最大完工時(shí)間；Ci為工件i的完工時(shí)間；TEC為總能耗；PE為所有機(jī)器的加工能耗；TE為所有運(yùn)輸任務(wù)的運(yùn)輸能耗；IE為所有機(jī)器的空閑能耗；xijkf為0-1決策變量，如果Oij在工廠f的機(jī)器k上加工，則xijkf為1，否則為0；F為工廠數(shù)量；Mf為工廠f中機(jī)器的數(shù)量；yijghkf為0-1決策變量，工廠f的機(jī)器k加工完Ogh后加工Oij，則yijghkf為1，否則為0；n為工件數(shù)量；ni為工件i的工序數(shù)量；αilk為0-1決策變量，如果工件i從機(jī)器l運(yùn)送到機(jī)器k，則αilk為1，否則為0；βifu為0-1決策變量，如果工件i從工廠f運(yùn)送到工廠u，則βifu為1，否則為0；cijkf為Oij在工廠f的機(jī)器k上的加工結(jié)束時(shí)間；sijkf為Oij在工廠f的機(jī)器k上的加工開始時(shí)間；pijkf為Oij在工廠f的機(jī)器k上的加工時(shí)長；M為一個(gè)足夠大的正數(shù)；pekf為工廠f中機(jī)器k的單位加工能耗；iekf為工廠f中機(jī)器k的單位空閑能耗；fte為工廠之間的單位運(yùn)輸能耗；TTfu為工件從工廠f到工廠u的運(yùn)輸時(shí)間；mte為機(jī)器之間的單位運(yùn)輸能耗；ttlk為工件從機(jī)器l到機(jī)器k的運(yùn)輸時(shí)間；i、g為工件索引；j、h為工序索引；l、k為機(jī)器索引；f、u為工廠索引。

式(1)、式(2)為優(yōu)化目標(biāo)——最小化最大完工時(shí)間和最小化總能耗；式(3)保證每道工序只能在一個(gè)工廠的一臺(tái)機(jī)器上加工；式(4)、式(5)表示每道工序的緊后或者緊前工序最多只有一道；式(6)確保每個(gè)工件不能同時(shí)在機(jī)器和車間之間進(jìn)行運(yùn)輸；式(7)表示工序的完工時(shí)間等于開始時(shí)間加上加工時(shí)長；式(8)確保機(jī)器不能同時(shí)加工多個(gè)工件；式(9)～式(11)分別表示機(jī)器加工能耗、機(jī)器空閑能耗和運(yùn)輸能耗。

2 改進(jìn)NSGA-Ⅱ

NSGA-Ⅱ是一種有效求解多目標(biāo)優(yōu)化問題的進(jìn)化算法，但在求解多目標(biāo)柔性作業(yè)車間調(diào)度問題時(shí)，存在早熟和易陷入局部最優(yōu)的不足。本文針對DFJGSPT的特性，對NSGA-Ⅱ進(jìn)行以下改進(jìn)：①設(shè)計(jì)了同時(shí)考慮加工時(shí)間和能耗的初始化方法，以提高初始種群的質(zhì)量；②設(shè)計(jì)了考慮運(yùn)輸時(shí)間的貪婪插入解碼方法，將染色體轉(zhuǎn)換為可行有效的調(diào)度方案；③采用多父代交叉和兩點(diǎn)插入及隨機(jī)選擇的變異方式進(jìn)行種群更新；④設(shè)計(jì)了一種變鄰域搜索策略來提高Pareto前沿的質(zhì)量。

2.1 基于工序和機(jī)器的雙層編碼

本文采用基于工序和機(jī)器的雙層編碼方式對染色體編碼，工廠的分配則通過解碼策略確定。以表1所示的數(shù)據(jù)為例，編碼方案示例見圖1。

表1 MODFJGSPT示例

圖1 編碼示例

2.2 考慮加工時(shí)間和能耗的種群初始化

本文設(shè)計(jì)了一種考慮加工時(shí)間和能耗的種群初始化方法：工序?qū)拥木幋a通過隨機(jī)的方式產(chǎn)生；機(jī)器層編碼通過設(shè)計(jì)的全局選擇(globalselection，GS)、局部選擇(local selection，LS)、隨機(jī)選擇(random select，RS)3種策略產(chǎn)生。參考文獻(xiàn)[14]，通過全局選擇、局部選擇和隨機(jī)選擇產(chǎn)生的初始解數(shù)量比例設(shè)為6∶3∶1。種群初始化的偽代碼如下。

算法1:種群初始化 ∥ Gr、Lr和Rr分別為通過全局選擇、局部選擇和隨機(jī)選擇所產(chǎn)生的初始解數(shù)量在種群占比,其值分別為0.6、0.3和0.11:采用隨機(jī)的方式產(chǎn)生工序?qū)拥木幋aOS2:創(chuàng)建兩個(gè)值為0的數(shù)組分別記錄所有機(jī)器的加工時(shí)間PTk和加工能耗PEk(1≤k≤m)3:If n<=Nind*(1-Rr)4:隨機(jī)選擇一個(gè)工件i ∥每個(gè)工件只被選擇一次5: For j=1 to ni6: TempPTk=pijk +PTk;TempPEk=pijk×pek + PEk(k∈K_use) ∥ K_use:Oij的可用機(jī)器集7: 根據(jù)TempPTk和TempPEk計(jì)算Pareto支配關(guān)系8: 選擇具有非支配TempPTk和TempPEk的機(jī)器k的索引放入機(jī)器層編碼MA中9: 更新PTk和PEk10: End For11: If n>Nind*Gr&&n <=Nind*(Gr+Lr)12: 將數(shù)組PTk和PEk的值設(shè)為013: End If14: 轉(zhuǎn)到步驟5,直到所有作業(yè)都被選中一次15:Else16:采用隨機(jī)的方式產(chǎn)生機(jī)器層編碼MA17:End If

2.3 考慮運(yùn)輸時(shí)間的貪婪插入解碼方法

通過編碼建立了工件和機(jī)器的映射關(guān)系，為進(jìn)一步確定工件在對應(yīng)機(jī)器上的開工時(shí)間，本文設(shè)計(jì)了一種考慮運(yùn)輸時(shí)間的貪婪插入解碼方法。首先通過機(jī)器編碼確定工件所在的工廠，然后考慮運(yùn)輸時(shí)間并引入貪婪的思想，將工件盡可能地插入機(jī)器的空閑時(shí)段內(nèi)，以減少機(jī)器的空閑時(shí)間和能耗，提高生產(chǎn)效率。解碼方法的偽代碼如下。

算法2:解碼方法 ∥ TO:工序總數(shù);ts/tf:第一個(gè)滿足插入條件的空閑時(shí)間段的開始/結(jié)束時(shí)間1:NOMk=?(k=1,2,…,m) %機(jī)器k上已經(jīng)安排的工序數(shù)量2:For h=1 to TO3: Oij=OS(h)4: 獲取Oij的加工機(jī)器k,pijk和運(yùn)輸?shù)竭_(dá)機(jī)器k的時(shí)間ta5: If j==1 &&NOMk==?6: sijk=0;cijk=sijk + pijk7: Else If j ～=1 &&NOMk==?8: sijk=ta;cijk=sijk+pijk9: Else If j==1 &&NOMk～=?10: Ins=find(IDk>=pijk)11: If Ins==?12: sijk=max{TMk,ta};cijk=sijk+pijk13: Else14: sijk=ts;cijk=sijk+pijk15: End If16: Else If j ～=1 &&NOMk～=?17: Ins=find(IDk>=pijk)18: NIns=find(tf-max{ts,ta} >=pijk)19: If NIns==?20: sijk=max{TMk,ta};cijk=sijk+pijk21: Else22: sijk=max{ts,ta};cijk=sijk+pijk23: End If24: End If25: 更新機(jī)器k的空閑時(shí)間時(shí)段IDk、NOMk和TMk26:End For

2.4 多父代交叉操作

為了融合多父代的信息，獲得更高質(zhì)量的子代，并增加種群的多樣性，本文采用多父代交叉方式[15]更新種群。工序?qū)雍蜋C(jī)器層的交叉方式分別如圖2、圖3所示。

圖2 工序?qū)咏徊?/p>

圖3 機(jī)器層交叉

工序?qū)咏徊娴牟襟E如下：

(1)隨機(jī)選擇父代個(gè)體P1、P2和P3；

(2)將工件索引集合Job={1，2，…，n}隨機(jī)劃分為2個(gè)互不包含的集合Job1和Job2；

(3)將P1中包含集合Job2的元素復(fù)制到子代C1，將P3中包含集合Job1的元素復(fù)制到子代C1；

(3)將P2中包含集合Job1的元素復(fù)制到子代C2，將P3中包含集合Job2的元素復(fù)制到子代C2。

機(jī)器層交叉的步驟如下：

(1)隨機(jī)選擇父代個(gè)體P1、P2和P3；

(2)隨機(jī)產(chǎn)生一個(gè)長度與工序總數(shù)一致且由 0、1 組成的集合R；

(3)在P2和P3中隨機(jī)選出與R中的1位置對應(yīng)的編碼，復(fù)制到子代C1中的相應(yīng)位置上；

(4)在P1和P3中隨機(jī)選出與R中的1位置對應(yīng)的編碼，復(fù)制到子代C2中的相應(yīng)位置；

(5)將P1和P2中其他的編碼分別保留到子代C1和C2中。

2.5 變異操作

對工序?qū)雍蜋C(jī)器層編碼分別采用不同的變異方式：①工序?qū)?，采用兩點(diǎn)插入變異方式，隨機(jī)選擇2個(gè)互不相鄰的位置l1和l2(l1

圖4 工序?qū)幼儺?/p>

2.6 變鄰域搜索

為進(jìn)一步提高個(gè)體的質(zhì)量，本文設(shè)計(jì)了一種用于Pareto前沿的變鄰域搜索策略。通過以下兩種鄰域結(jié)構(gòu)獲得新解：①隨機(jī)選擇工序?qū)泳幋a方案的2個(gè)位置，將這2個(gè)位置之間的編碼進(jìn)行翻轉(zhuǎn)；②獲取運(yùn)輸時(shí)間最長的2道相鄰工序，將后一道工序換到另一臺(tái)運(yùn)輸時(shí)間短的機(jī)器上進(jìn)行加工。如果新解更優(yōu)，則更新。

2.7 算法整體步驟

INSGA-Ⅱ的主要步驟如下：①初始化參數(shù)，產(chǎn)生初始種群；②交叉變異產(chǎn)生子代；③解碼并對種群進(jìn)行非支配排序；④對Pareto前沿進(jìn)行變鄰域搜索；⑤通過對非支配排序和擁擠距離計(jì)算，獲得下一代種群；⑥如果滿足終止條件則輸出Pareto前沿，否則轉(zhuǎn)到②。

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

本文算法基于MATLAB語言實(shí)現(xiàn)，并在Intel CPU E3-1240 V5、8 GB RAM的電腦上運(yùn)行。

3.1 算例生成及評(píng)價(jià)指標(biāo)

鑒于目前尚沒有DFJGSPT測試算例，本文對文獻(xiàn)[16]中的基準(zhǔn)算例進(jìn)行拓展，生成了45組測試算例。具體方式如下：對每個(gè)基準(zhǔn)算例分別考慮2、4和6個(gè)工廠的場景，工廠內(nèi)機(jī)器間的運(yùn)輸時(shí)間在[1，5] min內(nèi)隨機(jī)產(chǎn)生，工廠間的運(yùn)輸時(shí)間在[10，15] min內(nèi)隨機(jī)產(chǎn)生。機(jī)器單位加工能耗pek∈[10，15]kW，機(jī)器單位空閑能耗iek∈[1，3] kW，機(jī)器間的單位運(yùn)輸能耗mte=2 kW，工廠間的單位運(yùn)輸能耗fte=5 kW。采用多目標(biāo)優(yōu)化問題中廣泛應(yīng)用的覆蓋率C[3]和反世代距離IGD[17]評(píng)估算法性能，具體含義和公式如下：

(12)

(13)

式中，A、B分別為需要對比的兩種算法的Pareto前沿；|B|為集合B的大小；|PF*|為第一前沿的非支配解集PF*的大?。籨(x，y)為x點(diǎn)與y點(diǎn)之間的歐氏距離。

C(A，B)越大，A越好；IGD(A，PF*)越小，A越好。在本文研究中，各實(shí)例的PF*由每一種算法運(yùn)行10次得到的非支配解集綜合形成。

3.2 算法參數(shù)

本文提出的INSGA-Ⅱ有4個(gè)參數(shù)：種群規(guī)模(Nind)、交叉率(Pc)、突變率(Pm)和最大迭代次數(shù)(Maxit)。為保證參數(shù)設(shè)置的合理性，參考文獻(xiàn)[13]，采用正交試驗(yàn)確定最佳的參數(shù)組合。每個(gè)參數(shù)選擇4個(gè)水平，各個(gè)水平的值如表2所示。根據(jù)參數(shù)和水平的個(gè)數(shù)，選擇L16(45)正交表進(jìn)行試驗(yàn)。針對算例Mk2-01，算法在每種參數(shù)組合下運(yùn)行10次，以IGD作為各種參數(shù)組合的評(píng)價(jià)指標(biāo)，計(jì)算結(jié)果如表3所示。

表2 參數(shù)水平表

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

根據(jù)表3的結(jié)果繪制出參數(shù)水平的趨勢，見圖6?？芍?dāng)Nind為第一水平、Pc為第四水

(a)Nind的水平趨勢圖

平、Pm為第二水平、Maxit為第三水平時(shí)，IGD最小。因此，最終確定的參數(shù)組合為Nind=50，Pc=0.9，Pm=0.1，Maxit=300。

3.3 改進(jìn)策略的有效性

為驗(yàn)證本文設(shè)計(jì)的種群初始化策略和變鄰域搜索策略的有效性，本文將INSGA-Ⅱ(A1)與采用隨機(jī)初始化策略的INSGA-Ⅱ(A2)和不包含變鄰域搜索策略的INSGA-Ⅱ(A3)進(jìn)行對比。

參考文獻(xiàn)[7]，以Mk01、Mk04、Mk09、Mk12和Mk15在不同工廠數(shù)下對應(yīng)的15組算例為測試算例，對這3種算法進(jìn)行測試。每種算法運(yùn)行10次，采用C和IGD比較算法的性能。在15組算例測試結(jié)果中，C(A1，A2)=C(A1，A3)=1，C(A2，A1)=C(A3，A1)=0，說明算法A1可以獲得更優(yōu)的Pareto解集。此外，IGD(A1)均為0，IGD(A2)、IGD(A2)如表4所示，可以看出IGD(A1)遠(yuǎn)小于IGD(A2)和IGD(A3)，進(jìn)一步表明算法A1獲得的Pareto解集更優(yōu)。測試結(jié)果可以證明本文設(shè)計(jì)的種群初始化策略和變鄰域搜索策略的有效性。

表4 改進(jìn)策略測試結(jié)果

3.4 與其他算法對比分析

為進(jìn)一步驗(yàn)證本文算法的有效性，將其與以被廣泛應(yīng)用的多目標(biāo)優(yōu)化算法NSGA-Ⅱ、SPEA2和MOEA/D進(jìn)行對比。對比算法的參數(shù)設(shè)置與INSGA-Ⅱ相同，其中，SPEA2和MOEA/D的外部存檔大小設(shè)置為種群大小。每個(gè)算法運(yùn)行10次，采用C和IGD比較算法的性能。所有算例下，C(INSGA-Ⅱ，NSGA-Ⅱ)=C(INSGA-Ⅱ，SPEA2)=C(INSGA-Ⅱ，MOEA/D)=1，C(NSGA-Ⅱ，INSGA-Ⅱ)=C(SPEA2，INSGA-Ⅱ)=C(MOEA/D，INSGA-Ⅱ)=0，這表明INSGA-Ⅱ得到的解優(yōu)于另外3種算法得到的解。IGD(INSGA-Ⅱ)均為0，另外3種算法的IGD如表5所示，可以看出，IGD(INSGA-Ⅱ)遠(yuǎn)小于IGD(NSGA-Ⅱ)、IGD(SPEA2)和IGD(MOEA/D)，這與C值結(jié)果相互對應(yīng)。此外，隨著工廠數(shù)量的增加，IGD(NSGA-Ⅱ)、IGD(SPEA2)和IGD(MOEA/D)增大，而IGD(INSGA-Ⅱ)不變，這說明INSGA-Ⅱ能解決不同規(guī)模的分布式柔性作業(yè)車間調(diào)度問題。

表5 平均IGD值

本文設(shè)計(jì)的INSGA-Ⅱ之所以能夠獲得更優(yōu)的解，主要因?yàn)椋孩倏紤]加工時(shí)間和能耗的初始化方法能產(chǎn)生更高質(zhì)量的初始種群。該方法采用了新的全局和局部選擇策略來產(chǎn)生機(jī)器層編碼，均衡加工時(shí)間和能耗，同時(shí)，為提高種群多樣性，應(yīng)用隨機(jī)選擇方式產(chǎn)生部分機(jī)器層編碼。②考慮運(yùn)輸時(shí)間的貪婪插入解碼方法通過將工件插入機(jī)器的空閑時(shí)間內(nèi)，合理地安排工件在機(jī)器上的加工順序，能壓縮機(jī)器的空閑時(shí)間，進(jìn)而提高生產(chǎn)效率、降低能耗。③多父代交叉操作可以融合多父代的信息，獲得更高質(zhì)量的子代；新的變異操作不僅避免了算法陷入局部最優(yōu)，并且增加了種群的多樣性。④變鄰域搜索策略能進(jìn)一步提高Pareto前沿的質(zhì)量，該策略的嵌入增強(qiáng)了算法的局部搜索能力。為了進(jìn)一步展現(xiàn)本文算法的性能，以算例Mk2-01、Mk2-04、Mk2-09、Mk2-12和Mk2-15為例，繪制4種算法一次求解得到的Pareto前沿分布。

由圖7可以看出，本文算法Pareto前沿均在另外3種算法Pareto前沿的左下方，表明本文算法可以得到更優(yōu)的Pareto前沿，這與上文的C和IGD評(píng)價(jià)指標(biāo)計(jì)算結(jié)果相符。Pareto前沿分布圖進(jìn)一步表明INSGA-Ⅱ能有效解決考慮運(yùn)輸時(shí)間的分布式柔性作業(yè)車間綠色調(diào)度問題。

(a)Mk2-01 (b)Mk2-04

圖8～圖15所示為MOEA/D、NSGA-Ⅱ、SPEA2和INSGA-Ⅱ?qū)λ憷齅k2-09求解得到的調(diào)度方案，可以看出，INSGA-Ⅱ調(diào)度方案的完工時(shí)間最短，并且機(jī)器的總空閑時(shí)間明顯也短于另外3種調(diào)度方案，這意味著INSGA-Ⅱ可以提高機(jī)器的利用率，進(jìn)而提高生產(chǎn)效率、減少能源消耗。