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

李嘉曜 倪靜

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

關(guān)鍵詞： 跨單元調(diào)度； 跨單元運(yùn)輸時(shí)間； 改進(jìn)NSGA-II算法； 全局能耗

中圖分類(lèi)號(hào)：TP301? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：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)服務(wù)于多品種、小批量的制造業(yè)企業(yè)，區(qū)別于傳統(tǒng)生產(chǎn)車(chē)間，單元制造系統(tǒng)必須考慮運(yùn)輸對(duì)于生產(chǎn)過(guò)程的影響。于是跨單元調(diào)度問(wèn)題（Inter Cell Scheduling Problem， ICSP）產(chǎn)生。

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

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

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

1 問(wèn)題描述與數(shù)學(xué)模型

1.1 模型建立

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

ICGSP需要滿足以下約束件：

⑴ 任一工序在任一時(shí)刻只能在一個(gè)單元的一臺(tái)機(jī)器上加工；

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

⑶ 任一機(jī)器在任一時(shí)刻只能加工一道工序；

⑷ 工序間不允許搶占；

⑸ 加工過(guò)程不考慮中斷情況；

⑹ 所有單元的運(yùn)輸能力充足且相同。

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

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

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

[f1=minCmax=minCMm]? ⑴

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

[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的機(jī)器k0，? 其他]? ⒁

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

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

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

2 改進(jìn)變鄰域NSGA-II算法

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

2.1 初始化

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

2.2 編碼

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

2.3 解碼

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

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

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

2.4 交叉和變異

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

[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]基礎(chǔ)交叉率取值范圍為[0.5，1]，[fit（n）]為當(dāng)前個(gè)體適應(yīng)度值，[fitavg]為種群適應(yīng)度均值，[fitmax]和[fitmin]分別為種群適應(yīng)度值最大和最小值[fitb（n）]為兩個(gè)父代中較大的適應(yīng)度值，通常交叉率最優(yōu)范圍在[0.9，1][13]，當(dāng)適應(yīng)度值大于均值時(shí)，表示新生成的子代解較差，應(yīng)當(dāng)較大的交叉率，反之則為0.9。式（18）中[Pkm]為基礎(chǔ)變異率，范圍為[0.05，0.1]，變異率最佳取值范圍是[0，0.1][13]，自適應(yīng)變化原理與交叉率相同。

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

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

在MS交叉中機(jī)器變化的同時(shí)單元層也會(huì)隨之改變，因此對(duì)MS操作進(jìn)行修復(fù)如圖8所示。

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

2.5 變鄰域搜索算子

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

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

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

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

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

如果鄰域結(jié)構(gòu)中存在同一關(guān)鍵工序塊上需要交換的相鄰工序?yàn)橥还ぜ械膬傻拦ば虻那闆r，則不進(jìn)行交換，否則將破壞工序間約束。

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

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

3 數(shù)值實(shí)驗(yàn)和分析

3.1 算例構(gòu)造和評(píng)價(jià)指標(biāo)分析

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

3.2 算法性能對(duì)比

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

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

3.3 運(yùn)輸時(shí)間相關(guān)性

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

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

4 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

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