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

李嘉曜 倪靜

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

關(guān)鍵詞： 跨單元調(diào)度； 跨單元運輸時間； 改進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 引言

單元制造系統(tǒng)服務于多品種、小批量的制造業(yè)企業(yè)，區(qū)別于傳統(tǒng)生產(chǎn)車間，單元制造系統(tǒng)必須考慮運輸對于生產(chǎn)過程的影響。于是跨單元調(diào)度問題（Inter Cell Scheduling Problem， ICSP）產(chǎn)生。

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

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

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

1 問題描述與數(shù)學模型

1.1 模型建立

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

ICGSP需要滿足以下約束件：

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

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

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

⑷ 工序間不允許搶占；

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

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

1.2 數(shù)學模型

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

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

[f1=minCmax=minCMm]? ⑴

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

[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，? 其他]? ⒃

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

2 改進變鄰域NSGA-II算法

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

2.1 初始化

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

2.2 編碼

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

2.3 解碼

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

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

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

2.4 交叉和變異

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

[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）]為兩個父代中較大的適應度值，通常交叉率最優(yōu)范圍在[0.9，1][13]，當適應度值大于均值時，表示新生成的子代解較差，應當較大的交叉率，反之則為0.9。式（18）中[Pkm]為基礎變異率，范圍為[0.05，0.1]，變異率最佳取值范圍是[0，0.1][13]，自適應變化原理與交叉率相同。

交叉操作選擇工序?qū)樱∣S）和機器層（MS）交叉，并選用多點交叉方式如圖6和圖7所示。

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

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

采用多點變異對工序?qū)樱∣S）和機器層（MS）進行變異操作，OS變異中，父代1的兩個位置轉(zhuǎn)變?yōu)槠渌ば蛐蛱柹勺哟?；MS變異對父代1中機器層選定位置的序號變?yōu)槠渌尚袡C器序號生成子代1，具體過程如圖9所示。

2.5 變鄰域搜索算子

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

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

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

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

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

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

⑵ 鄰域結(jié)構(gòu)[NS2]對所有加工工件中跨單元運輸時間最長的工件進行鄰域變換。根據(jù)解碼結(jié)果選擇運輸時間的工件[Jn]中最后需要運輸?shù)那昂髢傻拦ば颍鶕?jù)前道工序判斷后道工序是否能在同一單元的一臺機器上加工，如果可行則選擇一臺可行機器，若不滿足則再選擇工件[Jn-1]，直到滿足要求。

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

3 數(shù)值實驗和分析

3.1 算例構(gòu)造和評價指標分析

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

3.2 算法性能對比

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

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

3.3 運輸時間相關(guān)性

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

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

4 結(jié)束語

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

參考文獻（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] 劉兆赫，李冬妮，王樂衡，等.考慮運輸能力限制的跨單元調(diào)度方法[J].自動化學報，2015，41（5）：885-898.

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

[6] 鄒萌邦，劉瓊，尹勇.基于改進小世界遺傳算法的網(wǎng)絡環(huán)境下跨單元調(diào)度[J].計算機集成制造系統(tǒng)，2019，25（8）：1991.

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

[8] 徐晨昕.網(wǎng)絡環(huán)境下面向低碳的跨單元調(diào)度優(yōu)化[D].湖北：華中科技大學，2018.

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

[10] 張洪亮，徐公杰，鮑薔，等.考慮運輸時間的分布式柔性作業(yè)車間綠色調(diào)度[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] 姜一嘯，吉衛(wèi)喜，何鑫，等.基于改進非支配排序遺傳算法的多目標柔性作業(yè)車間低碳調(diào)度[J].中國機械工程，2022，33（21）：2564-2577.

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