考慮運輸時間的分布式柔性作業車間綠色調度

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

中國機械工程 2022年21期

張洪亮徐公杰鮑薔潘瑞林

安徽工業大學管理科學與工程學院，馬鞍山，243032

0 引言

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

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

上述研究存在以下不足：①要求同一工件的所有工序必須在同一工廠內完成，沒有考慮工件在工廠之間的轉移。實際上，分布式生產系統中，一些工件可能在不同的工廠加工。②要求工件在前道工序加工完成后立即執行下一道工序，忽略了工序之間的運輸時間。實際上，工件在工序之間流轉需要運輸時間，且加工時間和運輸時間之間有較強的耦合關系。③主要關注時間相關的目標且以單目標為主，沒有考慮能耗相關的目標。隨著綠色制造的推進，在生產調度決策中考慮與能耗相關的目標變得至關重要。

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

1 問題描述及數學模型

1.1 問題描述

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

1.2 數學模型

基于以上描述可得DFJGSPT的數學模型：

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

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

2 改進NSGA-Ⅱ

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

2.1 基于工序和機器的雙層編碼

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

表1 MODFJGSPT示例

圖1 編碼示例

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

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

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

2.3 考慮運輸時間的貪婪插入解碼方法

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

算法2:解碼方法 ∥ TO:工序總數;ts/tf:第一個滿足插入條件的空閑時間段的開始/結束時間1:NOMk=?(k=1,2,…,m) %機器k上已經安排的工序數量2:For h=1 to TO3: Oij=OS(h)4: 獲取Oij的加工機器k,pijk和運輸到達機器k的時間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: 更新機器k的空閑時間時段IDk、NOMk和TMk26:End For

2.4 多父代交叉操作

為了融合多父代的信息，獲得更高質量的子代，并增加種群的多樣性，本文采用多父代交叉方式[15]更新種群。工序層和機器層的交叉方式分別如圖2、圖3所示。

圖2 工序層交叉

圖3 機器層交叉

工序層交叉的步驟如下：

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

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

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

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

機器層交叉的步驟如下：

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

(2)隨機產生一個長度與工序總數一致且由 0、1 組成的集合R；

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

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

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

2.5 變異操作

對工序層和機器層編碼分別采用不同的變異方式：①工序層，采用兩點插入變異方式，隨機選擇2個互不相鄰的位置l1和l2(l1

圖4 工序層變異

2.6 變鄰域搜索

為進一步提高個體的質量，本文設計了一種用于Pareto前沿的變鄰域搜索策略。通過以下兩種鄰域結構獲得新解：①隨機選擇工序層編碼方案的2個位置，將這2個位置之間的編碼進行翻轉；②獲取運輸時間最長的2道相鄰工序，將后一道工序換到另一臺運輸時間短的機器上進行加工。如果新解更優，則更新。

2.7 算法整體步驟

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

3 實驗分析

本文算法基于MATLAB語言實現，并在Intel CPU E3-1240 V5、8 GB RAM的電腦上運行。

3.1 算例生成及評價指標

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

(12)

(13)

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

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

3.2 算法參數

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

表2 參數水平表

表3 正交試驗表

根據表3的結果繪制出參數水平的趨勢，見圖6。可知，當Nind為第一水平、Pc為第四水

(a)Nind的水平趨勢圖

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

3.3 改進策略的有效性

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

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

表4 改進策略測試結果

3.4 與其他算法對比分析

為進一步驗證本文算法的有效性，將其與以被廣泛應用的多目標優化算法NSGA-Ⅱ、SPEA2和MOEA/D進行對比。對比算法的參數設置與INSGA-Ⅱ相同，其中，SPEA2和MOEA/D的外部存檔大小設置為種群大小。每個算法運行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-Ⅱ得到的解優于另外3種算法得到的解。IGD(INSGA-Ⅱ)均為0，另外3種算法的IGD如表5所示，可以看出，IGD(INSGA-Ⅱ)遠小于IGD(NSGA-Ⅱ)、IGD(SPEA2)和IGD(MOEA/D)，這與C值結果相互對應。此外，隨著工廠數量的增加，IGD(NSGA-Ⅱ)、IGD(SPEA2)和IGD(MOEA/D)增大，而IGD(INSGA-Ⅱ)不變，這說明INSGA-Ⅱ能解決不同規模的分布式柔性作業車間調度問題。

表5 平均IGD值

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

由圖7可以看出，本文算法Pareto前沿均在另外3種算法Pareto前沿的左下方，表明本文算法可以得到更優的Pareto前沿，這與上文的C和IGD評價指標計算結果相符。Pareto前沿分布圖進一步表明INSGA-Ⅱ能有效解決考慮運輸時間的分布式柔性作業車間綠色調度問題。