基于改進變鄰域NSGA-II的綠色跨單元調度問題

李嘉曜 倪靜

摘? 要： 針對綠色背景下跨單元調度存在加工效率低和能源消耗高等問題，建立了以最小化完工時間和全局能耗的多目標數學模型。提出了一種改進變鄰域NSGA-II算法求解模型。首先引入三層編碼表達問題特征，然后設計了考慮運輸時間的解碼方法，提出一種基于Sigmoid函數的自適應交叉變異率以保證種群多樣性，最后構建了三種變鄰域結構融入改進后的NSGA-II算法來增強局部搜索能力。實驗表明，改進后的算法能有效求解模型，運輸時間能夠協調完工時間和能耗關系。

關鍵詞： 跨單元調度； 跨單元運輸時間； 改進NSGA-II算法； 全局能耗

中圖分類號：TP301? ? ? ? ? 文獻標識碼：A? ? ?文章編號：1006-8228（2023）09-69-06

Intercell green scheduling problem based on improved variable neighborhood NSGA-II

Li Jiayao， Ni Jing

（Business School， University of Shanghai for Science & Technology， Shanghai 200093， China）

Abstract： Aiming at the poor processing efficiency and high energy consumption in intercell scheduling under green background， a multi-objective mathematical model is established to minimize the completion time and global energy consumption， and an improved variable neighborhood NSGA-II algorithm is proposed to solve the model. Firstly， a three-layer coding is introduced to express the problem characteristics. Then， a decoding method considering transportation time is designed， and an adaptive crossover mutation rate based on Sigmoid function is proposed to ensure the population diversity. Finally， three kinds of variable neighborhood structures are constructed and integrated into the improved NSGA-II algorithm to enhance the local search ability. The experiments show that the improved algorithm can solve the model effectively， and the transportation time can coordinate the relationship between the completion time and energy consumption.

Key words： intercell scheduling; intercell transportation time; improved NSGA-II algorithm; global energy consumption

0 引言

單元制造系統服務于多品種、小批量的制造業企業，區別于傳統生產車間，單元制造系統必須考慮運輸對于生產過程的影響。于是跨單元調度問題（Inter Cell Scheduling Problem， ICSP）產生。

有關的研究從各個角度解決ICSP問題，如Subhaa等[1]人提出了集成單元形成和跨單元調度的模型，降低了產品在單元間的流動時間，同時為每個工序分配合適的機器。Feng[2]為了減少產品可重入路徑，為設備劃分不同單元，同時解決后續生產過程的調度問題。上述文獻研究了單元劃分和調度問題，但在實際生產中針對各種類產品組成布局單元需要大量成本，因此，從調度方向解決跨單元問題更貼切企業實際情況。Li等[3]發現，加工過程中存在冗余的運輸路徑，從降低路徑的角度，設計了一種基于智能體的調度方法以優化時間目標。劉兆赫[4]在跨單元問題中增加運輸能力約束，設計了超啟發式算法以降低運輸時間對于系統的影響。呂潔[5]對多批量產品進行批量分割，通過合理分配不同批次的加工路徑以到達總加工成本的優化目的。也有研究發現，復雜網絡中的出入度滿足單元制造系統的特征表達，鄒萌邦等[6]提出了單元模塊度的概念，通過降低模塊度消除了加工過程中冗余路徑。近年來國家推崇低碳綠色的生產環境以減輕能源消耗對自然環境的影響，因此降低制造業能耗的需求日益明顯[7]，有關的研究如徐晨昕[8]在企業間合作產生的網絡化多單元系統背景下，分析了加工和運輸等碳排放對生產過程的影響，目前針對綠色低碳背景的跨單元調度的研究較少。

改進的NSGA-II算法已被廣泛運用于求解車間調度問題，王亞昆等[9]針對帶有運輸約束的柔性車間改進了解碼方式并為算法設計了學習機制的最優解生成法，保證種群進化的有效性。張洪亮等[10]設計了一種適用于分布式柔性車間的NSGA-II算法以求解帶有能耗目標的調度問題，改進了交叉和變異以保證迭代個體的多樣性。Paolo等[11]為NSGA-II建立一種基于開關策略的插入式解碼方式，運用該策略降低了加工過程中空閑能耗。

綜上所述，跨單元調度問題通常以單元形成和降低跨單元運輸時間的方向優化目標，當前很少有研究同時考慮完工時間和總能耗的跨單元調度問題，也少有學者改進NSGA-II求解該問題，本文建立了考慮時間和能耗的多目標ICSP的數學模型，將問題描述為（Inter Cell Green Scheduling Problem， ICGSP），同時提出了適用于模型的改進非支配排序算法NSGA-II，混合了變鄰域搜索算法為ICGSP提供新思路，實驗結果表明：提出的改進算法能有效的求解ICGSP；改變運輸時間可以調節完工時間和能耗間的協調關系。

1 問題描述與數學模型

1.1 模型建立

ICGSP的機器被劃分于多個單元內，具體可描述為：工件集合[J∈{J1，J2，…，Jn}]個工件具有工序集合[O∈{O1，O2，…，Oh}]需要在單元集合[U∈U1，U2，…，Uc]中的機器集合[M∈{M1，M2，…，Mk}]上加工，每道工序可選擇一臺或多臺設備來加工。設備具有柔性，即每道工序有若干臺機器可以選擇，調度的意義就是給所有工序合理排序以及分配機器以達到目標調度的最優，在ICGSP在中每個工件至少有一道工序需要跨單元生產，工件的前后工序會在單元間流動，因此運輸時間不可避免，圖1為ICGSP問題的示意圖，其中[R1]和[R2]分別為兩條路徑，[J1]如果選擇[R1]則需要在[U1]中的[M1]加工第一道工序后在同一單元內的[M3]加工后道工序。[R2]路徑中[J1]的第一道工序加工完后需要從[U2]的[M1]轉移至[U1]中的[M4]，產生5的運輸時間，如圖1所示。

ICGSP需要滿足以下約束件：

⑴ 任一工序在任一時刻只能在一個單元的一臺機器上加工；

⑵ 同一工件的工序需要滿足緊前后條件；

⑶ 任一機器在任一時刻只能加工一道工序；

⑷ 工序間不允許搶占；

⑸ 加工過程不考慮中斷情況；

⑹ 所有單元的運輸能力充足且相同。

1.2 數學模型

本文以完工時間[f1]和總能耗[f2]兩個函數共同組成ICGSP多目標優化模型。該優化目標具體表達如下：

⑴ 最終完工時間：最終完工時間指整個系統中最后一道工序的結束時間，完工時間越小代表整體加工效率越高。

[f1=minCmax=minCMm]? ⑴

⑵ 全局能耗：全局能耗包含所有加工能耗、機器空閑能耗以及單元間運輸能耗，在實際生產中三者對于加工過程影響較大，降低總能耗有利制造企業節約成本。式⑶、式⑷和式⑸分別為加工能耗、空閑能耗和運輸能耗。

[f2=minET=min （Ep+Ei+Et）]? ⑵

[Ep=u=1ck=1mpij*peku*xijku]? ⑶

[Ei=u=1ck=1msij-wlku*ieku]? ⑷

[Et=i=1nj=1htuu'*teu*qi（j+1）]? ⑸

ICGSP的約束條件如下：

[k=1mxijku=1? ? ?i，j，k]? ⑹

[k=1myiji'j'=1? ? ?i，i'，j，j'，k]? ⑺

[sij+pij*xijku≥cij? ? ?i，j，k，u]? ⑻

[cij-ci'j'≥pij? ? ?i，i'，j，j']? ⑼

[si（j+1）-cij≥tuu'?i，j，u，u]? ⑽

[wlku≤sij-ci'j'?i，i'，j，j'] ⑾

[sij>0，cij>0，?i，j]? ?⑿

[CMku=maxu=1ck=1mcku? ? ?k，u]? ⒀

[xijku=1，? j被分配到單元u的機器k0，? 其他]? ⒁

[yiji'j'=1，? Oij在Oi'j'之前加工0，? 其他]? ⒂

[qij（j+1）=1，? Oij在Oi（j+1）跨單元加工0，? 其他]? ⒃

約束式⑹表示一道工序在同一時間只能在一個單元內的一臺機器上加工；約束式⑺表示工序間必須滿足緊前后關系；約束式⑻表示工序開始加工后無法中斷，其中[sij]為工序開始時間，[pijku]為工序的加工時間；式⑼代表一臺機器一次只能選擇一道工序，[cij]和[ci'j']表示一臺機器上的前后兩道不同工序；約束式⑽代表緊前后工序在轉移到下一單元加工后才能進行加工，[tuu']為單元間運輸時間，[si（j+1）]表示需要跨單元加工的工序；約束式⑾為機器某一時刻的負載量，[wlku]表示機器負載；約束式⑿表示時間變量為正數；約束式⒀定義了完工時間；約束式⒁～式⒃為決策變量。

2 改進變鄰域NSGA-II算法

本文的IVNSGA-II算法是在NSGA-II基礎上對各部分進行改進以適合求解提出的模型，對交叉變異后的解集非支配排序、精英保留策略獲得新種群，再融入變鄰域結構增強算法能力，具體流程圖如圖2所示。

2.1 初始化

初始化機制影響著解得質量，本文采用隨機法，生成N個解集作為初始種群。

2.2 編碼

編碼是算法求解問題的基礎，ICGSP需同時考慮工序、機器和單元的選擇及排序問題，雙聯式編碼無法體現單元特征，因此選擇一種三層編碼方法[12]。工序層中相同的數字表示同一個工件，相同工件序號出現的次數表示工件的工序；機器層中的數字表示對應的工序可用加工機器的序號；單元層表示機器所屬單元。以圖3為例，三層編碼的第一位表示工件3的第三道工序在單元1上的第一臺可行機器上加工。

2.3 解碼

解碼是將染色體模擬實際加工過程的步驟，根據跨單元特性設計考慮運輸時間的貪婪插入解碼法。該解碼方式可有效減少過程中的空閑時間，具體解碼過程可分為同單元插入和跨單元插入兩種方式。

圖4為同單元插入方式，[Mck]和[Mcm]為同單元的不同機器，[Oi，j]具有兩段可插入空閑區間[T1idle]和[T2idle]，選擇[T1idle]內的空閑段產生較小的開始時間[Si，j]，因此[T1idle]為同單元插入的最佳區間。[Oi，j]的開始時間為[Si，j=Ci，j-1]。

圖5為跨單元插入方式，[Mck]和[Mc'i]處于兩個不同單元內，[Oi，j]在經過運輸后具有兩段可插入空閑區間[T1idle]和[T2idle]，插入空閑段[T1idle]內將產生較小的開始時間[Si，j]，因此，[T1idle]為跨單元插入的最佳區間。[Oi，j]的開始時間為[Si，j=Ci，j-1+tuu']。

2.4 交叉和變異

優秀的交叉變異可以增加算法收斂性，迭代前期種群質量較差應給予高交叉變異率提高種群質量，在迭代后期，種群質量相對優秀，應適當降低交叉變異率。因此本文設計了一種基于sigmoid函數的自適應交叉變異率，具體公式如下：

[Pc=0.1*1Pcm+efitbn-fitavgfitmax-fitavg+0.9? ? fit（n）>fitavg0.9? ? ? ? ? ? ? ? ? ? ? ? ? ?fit（n）≤fitavg] ⒄

[Pm=0.1? ? ? ? ? ? ? ? ? ? ? ? ? ? fit（n）>fitavg0.1*（1-1Pkm+efitn-fitavgfitmax-fitavg）? ? fit（n）≤fitavg] ⒅

式⒄中[Pcm]基礎交叉率取值范圍為[0.5，1]，[fit（n）]為當前個體適應度值，[fitavg]為種群適應度均值，[fitmax]和[fitmin]分別為種群適應度值最大和最小值[fitb（n）]為兩個父代中較大的適應度值，通常交叉率最優范圍在[0.9，1][13]，當適應度值大于均值時，表示新生成的子代解較差，應當較大的交叉率，反之則為0.9。式（18）中[Pkm]為基礎變異率，范圍為[0.05，0.1]，變異率最佳取值范圍是[0，0.1][13]，自適應變化原理與交叉率相同。

交叉操作選擇工序層（OS）和機器層（MS）交叉，并選用多點交叉方式如圖6和圖7所示。

OS交叉中父代1和父代2交換工序位置生成子代1和2；MS交叉中首先對父代1和父代2分別選擇隨機位置，將父代1所選位置順序插入子代1中，剩余位置插入子代2中。父代2同理。

在MS交叉中機器變化的同時單元層也會隨之改變，因此對MS操作進行修復如圖8所示。

采用多點變異對工序層（OS）和機器層（MS）進行變異操作，OS變異中，父代1的兩個位置轉變為其他工序序號生成子代1；MS變異對父代1中機器層選定位置的序號變為其他可行機器序號生成子代1，具體過程如圖9所示。

2.5 變鄰域搜索算子

交叉變異具有盲目性，由于精英保留機制，新生成的子代質量可能不如父代，無法保證種群向指定的位置進行移動，因此本文設計了三種變鄰域結構對交叉變異后的個體進行鄰域變換，分別是考慮運輸時間的關鍵路徑鄰域算子[NS1]、運輸時間降低鄰域算子[NS2]和機器負載降低鄰域算子[NS3]。以此幫助算法向理想位置更新，三種鄰域結構如下。

⑴ 鄰域結構[NS1]采用N5關鍵路徑的鄰域結構[14]調整工序OS部分，關鍵路徑在車間調度問題中已經獲得廣泛運用，在改變關鍵路徑中的關鍵工序塊上同時工序滿足緊前后約束，同時如果工序塊的變換涉及到運輸時間，則需要判斷前道跨單元加工工序的運輸完成時間。算法每次只對一個關鍵工序塊中的路徑進行位置交換以防止生成大量非法解集。選擇支配等級最高的個體[Xi]，確定個體調度的關鍵路徑，選擇關鍵工序塊進行交換，具體方法如下：

方法①：若起始關鍵工序塊包含二道或以上工序則交換塊中末尾兩道工序。

方法②：若中間關鍵工序塊中包含三道或以上工序則交換其塊首的相鄰工序，如果前兩道工序進行了跨單元運輸則對后續影響到的工序進行右移。

方法③：若尾部關鍵工序塊中包含兩道或以上工序則交換塊尾的相鄰兩道工序。

如果鄰域結構中存在同一關鍵工序塊上需要交換的相鄰工序為同一工件中的兩道工序的情況，則不進行交換，否則將破壞工序間約束。

⑵ 鄰域結構[NS2]對所有加工工件中跨單元運輸時間最長的工件進行鄰域變換。根據解碼結果選擇運輸時間的工件[Jn]中最后需要運輸的前后兩道工序，根據前道工序判斷后道工序是否能在同一單元的一臺機器上加工，如果可行則選擇一臺可行機器，若不滿足則再選擇工件[Jn-1]，直到滿足要求。

⑶ 鄰域結構[NS3]對所有機器中負載量最高的設備進行鄰域變換，根據解碼選定負載最大的單元中負載量最大的機器，將機器上最后一道工序轉移到另一臺可行機器上，若不存在則更換一道工序直到滿足要求。

3 數值實驗和分析

3.1 算例構造和評價指標分析

IVNSGA-II實驗環境為Matlab2016，AMDRyzen5 3600X，3.8GHz，內存為8g的計算機上實現。參數設置為：種群規模[Pop]=150代，最大迭代次數[Maxgen]=200，基礎交叉概率[Pcm]=0.5，基礎變異概率[Pkm]=0.08。由于暫無跨單元調度的基準算例，本文選取基準算例集的Brandimarte中的MK01和MK03以及Hurink中的LA16作為實驗對象，對三個算例進行單元劃分，算例信息如表1所示。機器單位加工能耗[pek∈[8，15]]kW，機器單位空閑能耗[iek∈[1，5]]kW，單元間的單位運輸能耗[teu]=5kW。

3.2 算法性能對比

表2為IVNSGA-II、NSGA-II和IWOA算法在三個算例的運行結果。對每個算例運行10次得到三個指標，[?max]為最差值，[?min]為最優值，[?avg]為均值。根據對比可得，IVNSGA-II均取得了最優結果，對于MK01-2算例，IVNSGA-II算法在完工時間目標上優勢并不高，但在全局能耗上遠低于其他兩種算法；在MK03-3算例上，IVNSGA-II的求解結果優秀程度較為明顯，在LA16-4上，算法在全局能耗目標上得到了最好的效果，本文算法運行時間也取得了最優。通過觀察每一代的目標值分析算法性能，如圖10所示。

圖10中，實線表示算法每一代最優值，虛線表示每一代最優值的均值，完工時間的最優值在76代達到最優收斂，其均值在100代也迭代到最低；總能耗在110代已接近收斂，之后能耗值繼續降低，驗證了變鄰域結構能幫助算法跳出了局部最優。

3.3 運輸時間相關性

運輸時間會影響總體加工效率和全局能耗，具體表現為：當運輸時間[tuu']增加時，在機器[Mk]上的工序[Oij]如果無法進行左移插入，則空閑時間和空閑能耗隨之增加，但對于一臺負載量較大的機器，增加一段運輸時間可能會幫助工序[Oij]轉移到一臺較為空閑的機器[Mc]上，因此該工序的完成時間反而降低，為了驗證這一點，本文將運輸時間映射為跨單元運輸次數與總能耗和負載量的關系，如圖11所示。

圖11中負載比率為總運輸時間和機器總負載的比率，能耗比率為總運輸時間和總能耗的比率。由此可以看出，跨單元在后期會上升，原因是在調度后期部分機器負載量較高，工序選擇了較為忙碌的機器加工，使得機器的負載量升高。能耗部分由于工序無法插入到空閑時間內導致空閑能耗增加，因此決策者可以通過調節運輸時間來協調完工時間和能耗，從而決定合理的優化結果。

4 結束語

本文針對ICGSP跨單元調度問題，首先建立了考慮完工時間和全局能耗的調度模型。提出一種IVNSGA-II求解該模型。引用了一種三層編碼表達工序、機器和單元層的具體關系，設計了考慮運輸時間的貪婪解碼法以降低空閑時間在調度過程中的影響，提出一種自適應交叉變異率增加算法尋優能力，融入了三種變鄰域搜索結構來提高算法的局部搜索能力。最后通過算例驗證了改進算法的有效性，同時分析了運輸時間與兩個優化目標的關系，為單元制造系統提供了新思路。在后續研究中將考慮將運輸工具作為實際約束加入到模型中，以及動態情況跨單元調度中的求解算法，探討解決跨單元調度問題的新思路。

參考文獻（References）：

[1] SubhaaR，JawaharN，Ponnambalam SG.An improved designforcellular manufacturing system associating scheduling decisions[J].Sādhanā，2019，44：1-23.

[2] Feng H， Xia T， Da W， et al. Concurrent design of cell

formation and scheduling with consideration of duplicate machines and alternative process routings[J]. Journal of Intelligent Manufacturing，2019，30：275-289.

[3] Li D， Wang Y， Xiao G， et al. Dynamic parts scheduling in?multiple job shop cells considering intercell moves and flexible routes[J]. Computers & Operations Research，2013，40（5）：1207-1223.

[4] 劉兆赫，李冬妮，王樂衡，等.考慮運輸能力限制的跨單元調度方法[J].自動化學報，2015，41（5）：885-898.

[5] 呂潔，王潔.基于批量分割的虛擬單元制造系統多階段動態調度[J].江蘇科技大學學報（自然科學版），2014，28（3）：292-297.

[6] 鄒萌邦，劉瓊，尹勇.基于改進小世界遺傳算法的網絡環境下跨單元調度[J].計算機集成制造系統，2019，25（8）：1991.

[7] 周濟.智能制造是“中國制造2025”主攻方向[J].企業觀察家，2019（11）：54-55.

[8] 徐晨昕.網絡環境下面向低碳的跨單元調度優化[D].湖北：華中科技大學，2018.

[9] 王亞昆，劉應波，吳永明，等.改進NSGA-II算法求解考慮運輸約束的柔性作業車間節能調度問題[J/OL].計算機集成制造系統，2023（3）：1-22.

[10] 張洪亮，徐公杰，鮑薔，等.考慮運輸時間的分布式柔性作業車間綠色調度[J].中國機械工程，2022，33（21）：2554-2563，2645.

[11] Renna P， MateriS.Switch off policies in job shop?manufacturing systems including workload evaluation[J]. International Journal of Management Science and Engineering Management，2021，16（4）：254-263.

[12] Feng Y， Li G， Sethi S P. A three-layer chromosome?genetic algorithm for multi-cell scheduling with flexible routes and machine sharing[J]. International Journal of Production Economics，2018，196：269-283.

[13] 姜一嘯，吉衛喜，何鑫，等.基于改進非支配排序遺傳算法的多目標柔性作業車間低碳調度[J].中國機械工程，2022，33（21）：2564-2577.

[14] 任璽悅，王修賢，耿娜，等.考慮多急件到達的作業車間重調度研究[J].工業工程與管理，2022，27（3）：74-83.