基于改進的NSGA-III算法求解綠色柔性作業(yè)車間調(diào)度問題

摘要：為解決多目標柔性作業(yè)車間調(diào)度問題在實際生產(chǎn)中求解效率低的難題，文章提出了一種改進的NSGA-III算法，旨在同時實現(xiàn)最小化最大完工時間、最小化瓶頸機器負荷及最小化設(shè)備總能耗的目標。首先，采用MSOS混合編碼方法，以獲取更優(yōu)質(zhì)的初始解集。其次，針對精英個體數(shù)量不足可能導(dǎo)致算法收斂停滯的問題，引入了一種改進的種群補充策略，即在精英個體數(shù)量不足時，從剩余個體中隨機選取個體進行補充。最后，通過采用改進的交叉操作，進一步提升解的質(zhì)量和算法的收斂速度。通過在Brandimarte數(shù)據(jù)集上進行驗證的結(jié)果表明，改進后的NSGA-III算法在求解質(zhì)量和效率方面均表現(xiàn)出優(yōu)異的性能。

關(guān)鍵詞：柔性作業(yè)車間；多目標優(yōu)化；NSGA-III；綠色調(diào)度

中圖分類號：TP301.6" " "文獻標識碼：A" " "文章編號：1674-0688（2024）12-0097-06

0 引言

柔性作業(yè)車間調(diào)度問題（Flexible Job-shop Scheduling Problem，F(xiàn)JSP）是生產(chǎn)管理和組合優(yōu)化領(lǐng)域的經(jīng)典難題，具有高度的復(fù)雜性和NP（非確定多項式）難度。隨著現(xiàn)代制造業(yè)的迅猛發(fā)展和市場競爭的日益加劇，企業(yè)面臨著多品種、小批量和個性化定制的生產(chǎn)需求，這對生產(chǎn)調(diào)度的靈活性和高效性提出了更高要求。在此背景下，如何高效解決FJSP，特別是將能源消耗等環(huán)境因素納入考量的綠色柔性車間調(diào)度問題，已成為學術(shù)界和工業(yè)界共同關(guān)注的熱點。

傳統(tǒng)車間調(diào)度問題通常以最小化完工時間或最大化生產(chǎn)效率為目標，然而，這種單一目標的優(yōu)化方式已難以滿足現(xiàn)代制造業(yè)的需求。實際生產(chǎn)過程中，除生產(chǎn)效率外，還需綜合考慮機器負載平衡、能源消耗、碳排放等多重因素。因此，研究多目標綠色柔性作業(yè)車間的調(diào)度問題具有重要的理論意義和實際應(yīng)用價值。近年來，國內(nèi)外眾多學者對多目標柔性作業(yè)車間問題展開了研究，并取得了一系列成果。RIFAI等［1］基于智能優(yōu)化算法，對具有雙重目標的非支配排序柔性制造系統(tǒng)問題進行了優(yōu)化；GONZALO等［2］探索了多個候選解的多目標局部搜索方法，并結(jié)合兩個目標的遺傳算法進行實驗驗證，證明了通用PERTI網(wǎng)框架在獲取高質(zhì)量解方面的適用性。谷鵬飛［3］采用單鏈整數(shù)編碼的遺傳算法，并提出對均衡化機器使用率的優(yōu)化目標進行求解。隨著算法的不斷創(chuàng)新，Deb等［4］于2014年首次提出NSGA-III （Non-dominated Sorting Genetic Algorithm III）算法，用于解決高維多目標優(yōu)化問題。該算法通過采用基于參考點的非支配排序方法，改進了選擇機制，并利用預(yù)定義參考點優(yōu)化復(fù)雜權(quán)衡面和多樣性保持的問題。如今，NSGA-III 算法已成為解決多目標柔性作業(yè)車間調(diào)度問題的優(yōu)選算法之一。楊草原等［5］通過比較NSGA-III算法與 NSGA-II算法，得出 NSGA-III算法更具優(yōu)越性的結(jié)論；宋存利等［6］提出了一種改進的NSGA-III算法，針對最大完工時間、總機器負載、瓶頸機器負荷等目標函數(shù)進行優(yōu)化；陳勇等［7］對NSGA-Ⅲ算法的初始化、交叉、變異部分進行優(yōu)化，以進一步提升求解效果；歐陽洪才等［8］則改進了NSGA-III算法，以解決多目標柔性作業(yè)車間問題。

基于上述研究，本文提出了一種改進的NSGA-III算法，主要包含以下3個方面的改進：首先，為獲得更優(yōu)初始解，采用改進的種群初始化方式，結(jié)合兩段式混合編碼策略，既保持了解的可行性，又提高了搜索效率，有效緩解了求解規(guī)模擴大導(dǎo)致的初始化效率降低問題。其次，提出改進的種群補充策略，當精英個體數(shù)量不足以維持種群規(guī)模時，從剩余個體中隨機選擇，以確保種群規(guī)模保持恒定。最后，將最小化設(shè)備總能耗作為優(yōu)化目標，實現(xiàn)了綠色調(diào)度。

1 柔性作業(yè)車間調(diào)度問題

1.1 問題描述

柔性作業(yè)車間動態(tài)重調(diào)度問題可以描述如下：在多臺機器上加工多個工件，每個工件包含一系列必須嚴格按照先后順序完成的工序，并且至少有一道工序可以由多臺可選機器進行加工，從而增加了機器選擇的靈活性。針對特定的優(yōu)化目標，如最小化完工時間、平衡機器負荷以及降低能耗，需要制定有效的生產(chǎn)調(diào)度方案。

1.2 數(shù)學模型

為了解決柔性作業(yè)車間動態(tài)重調(diào)度問題，本文構(gòu)建了一套數(shù)學模型。在模型構(gòu)建時，需要基于以下假設(shè)條件：①同一臺機器在同一時刻僅能加工一個工件。②同一工件的同一道工序在同一時刻僅能被一臺機器加工。③任意工序一旦開始加工便不能中斷。④各工件之間不存在優(yōu)先級差異。⑤同一工件的工序之間存在嚴格的先后約束，而不同工件的工序之間則無此約束。⑥所有工件在零時刻均可開始加工。模型參數(shù)見表1。

在數(shù)學模型的構(gòu)建中，最小化最大完工時間的目標函數(shù)表示為

[makespan=minmax" makespani] 。" " " "（1）

機器負荷表示為

[Load_all=load_z] 。" " " " " " " " "（2）

能耗表示為

[E_all=loadzPz+FZ?loadzRz]，" " " " "（3）

[i=1， 2， …， n，z=1， 2， …， n]。" " " " " （4）

約束條件如下。

（1）工序開工后不能中斷的約束條件表示為

[Cij?Sij=Tijz?i， j， z]，" " " " " " " " " " " " （5）

其中：? 是數(shù)學模型中的邏輯符號，表示“對于所有”或“任意”；? 后跟隨的變量i，j，z表示約束條件適用于這些變量的所有可能值。

（2）任意工序在機器上只能加工一次的約束條件表示為

[z=1nXijz=1?i， j]。" " " " " " " " " " " " （6）

（3）任意工序開工時間不大于完工時間的約束條件表示為

[Sij+XijzTijz≤Cij?i， j， z]。" " " " " " " " " "（7）

（4）任意工序完工時間不大于最大完工時間的約束條件表示為

[Cij≤makespan?i， j ]。" " " " " " " " " " "（8）

（5）每臺機器在同一時刻只能加工一道工序的約束條件表示為

[XhkzChk+MGhkij?1≤XijzSij?i， j， z， h， k]。" "（9）

（6）任意工件上一道工序的完工時間不大于下一道工序的開工時間的約束條件表示為

[Cij≤Sij+1?i， j]。" " " " " " " " " " " （10）

（7）任意工序的開工、加工和完工時間都為非負的約束條件表示為

[0≤Sij，0≤Sijz，0≤Cij?i， z， j]。" " " " " "（11）

2 NSGA-III算法與改進

NSGA-III是一種用于解決多目標優(yōu)化問題的先進算法，特別適用于處理包含3個或更多目標的復(fù)雜情形。該算法通過引入?yún)⒖键c機制和采用改進的精英保留策略，成功解決了目標空間中收斂性和多樣性維護的難題。在解決 FJSP 問題時，NSGA-III利用非支配排序和參考點引導(dǎo)的選擇機制，推動種群進化，實現(xiàn)了對多個目標的同步優(yōu)化。針對FJSP問題，本研究對 NSGA-III 算法進行了如下改進：首先，提出了一種混合編碼策略，該策略結(jié)合了MSOS （多目標粒子群優(yōu)化）的位置——速度編碼機制與傳統(tǒng)的工序編碼，既確保了解的可行性，又提升了搜索效率。其次，優(yōu)化了種群補充策略，以確保種群規(guī)模的恒定。最后，在目標函數(shù)方面，除傳統(tǒng)的完工時間和機器負荷外，還納入了機器能耗作為第三個優(yōu)化目標，從而實現(xiàn)了綠色調(diào)度的目的。

2.1 算法流程

改進NSGA-III的算法流程如圖1所示，具體步驟如下：①初始化種群。采用固定比例全局選擇、局部選擇和隨機選擇3種方式，對加工工件OS及機器MS進行整數(shù)編碼，形成包含工序、機器、加工時間信息的染色體，并進行解碼。②執(zhí)行交叉與變異操作。對工序和機器編碼進行交叉和變異處理。③合并與分層。將子代和父代種群合并，形成種群數(shù)量為2N的新種群。隨后，對新種群進行非支配排序，實現(xiàn)種群的分層。假設(shè)截至FL-1層的個體總數(shù)小于等于N，則截至FL層的個體數(shù)大于N。④個體選擇。從第一層開始依次選擇個體，若FL-1層已選擇N個個體，則進入步驟5；否則，依據(jù)參考點關(guān)聯(lián)方法，在FL層選擇k個個體。⑤迭代判斷與終止。檢查算法是否達到最大迭代次數(shù)，若達到，則結(jié)束算法并輸出最優(yōu)解；若未達到，則返回步驟2，繼續(xù)執(zhí)行交叉、變異、合并、分層及個體選擇操作。

2.2 種群初始化

傳統(tǒng)遺傳算法常采用直接的二進制或整數(shù)編碼方式。針對這些編碼方法的局限性，本文進行了改進，設(shè)計了一種MSOS混合編碼方式 （圖2）。該編碼方式將工序序列、機器選擇和加工時間三者緊密結(jié)合，全面描述了調(diào)度方案的關(guān)鍵要素。它特別適用于柔性車間調(diào)度問題的特性，能夠有效應(yīng)對工序在多臺機器上加工、加工時間隨機器不同而變化的復(fù)雜情形。在本研究中，需對 MSOS 染色體的各部分分別進行解碼。解碼的關(guān)鍵在于將工序排序部分與機器選擇部分相結(jié)合，以生成相應(yīng)的活動調(diào)度。具體解碼步驟如下：①對機器選擇部分進行解碼。從左至右依次讀取機器選擇部分的編碼，并將其轉(zhuǎn)換成機器順序矩陣[JM]和時間順序矩陣[T]。在矩陣[JM]中，[JMj， ?]表示工件[Jj]的工序[O?]的機器號，[JMj，?]表示工件[Jj]的所有工序按優(yōu)先順序加工的各個機器號的排列；在矩陣T中，[Tj， ?]表示工件[Jj]的工序[O?]的加工時間。矩陣[JM]和[T]是從機器選擇部分提取的中間結(jié)果，用于后續(xù)解碼過程。②對工序排序部分的染色體進行解碼。從左到右依次讀取工序排序部分的編碼，并按照上一步得到的機器順序矩陣[JM]和時間順序矩陣T，依次確定每個工件工序的加工機器和加工時間。最后，根據(jù)這些信息排序得到最終的調(diào)度結(jié)果。

2.3 交叉操作

在遺傳算法中，交叉操作的目的是通過組合父代個體生成新個體，是遺傳算法中的核心操作。本文在機器選擇部分和工序排序部分分別使用了均勻交叉操作和部分順序交叉（POX）操作。針對工序排序部分，本文應(yīng)用了POX交叉方法，以保留父代中的優(yōu)良特征并傳遞給子代。具體步驟如下：①從工件集中隨機選取若干工件，形成集合[J1]和[J2]。②將父代染色體[P1]和[P2]中屬于[J1]或[J2]的工件基因直接復(fù)制到對應(yīng)的子代染色體 [C1]和[C2]中，并保持這些基因在原染色體中的位置不變。③將不屬于[J1]或[J2]的工件基因，按照它們在原染色體中的順序，依次填充到子代染色體的剩余空位上。

POX交叉操作示意圖見圖3， POX交叉操作流程圖見圖4。

對于機器選擇部分的均勻交叉操作，詳細步驟如下：①在區(qū)間[1，T0]內(nèi)隨機選取一個整數(shù)[r]，作為交換基因的數(shù)量。②隨機確定[r]個交換位置。③在選定的交換位置上，將父代染色體[P1]和[P2]的基因進行交換，從而生成子代染色體[C1]和[C2]。④對于父代染色體中未被選中進行交換的位置上的基因，保留其原始順序，并填充到對應(yīng)的子代染色體中。

2.4 改進種群補充策略

在多目標柔性車間調(diào)度問題的研究中，本文采用了基于精英保留策略的多目標優(yōu)化算法。該算法優(yōu)先保留種群中的精英個體，以提升解的質(zhì)量并維持種群多樣性。然而，在實際應(yīng)用中觀察到精英個體數(shù)量不足的問題。具體而言，在種群進化過程中執(zhí)行非支配排序時，可能出現(xiàn)以下情形：某一代中，非支配層級的個體總數(shù)不足以填充整個種群，即[i=1kFilt;N]。 此現(xiàn)象主要發(fā)生在種群規(guī)模偏大、問題解決空間相對較小或優(yōu)化目標之間沖突較弱的情況下。

此外，在參考點關(guān)聯(lián)和個體選擇過程中，可能因個體分布不均或計算異常而導(dǎo)致關(guān)聯(lián)度計算異常，進而嚴重影響了算法的穩(wěn)定性和解的多樣性。為解決這些問題，本文提出了一種改進的種群補充策略。當精英個體數(shù)量不足時，該策略從剩余個體中隨機選擇，確保種群規(guī)模保持恒定。在無法按常規(guī)環(huán)境選擇過程填充種群時，同樣從剩余未被選擇的個體中隨機選取所需數(shù)量的個體進行補充。改進種群補充策略的流程圖見圖5，具體步驟如下：①對種群[P]進行非支配排序，得到非支配前沿[F1]， [F2]，…， [Fk]?。②設(shè)定選擇集[Q=?]，層次索引[i=1]。③逐層添加非支配個體，若[Q+Fi≤N]，則 [Q=Q∪Fi]， [i=i+1]；否則，跳出循環(huán)。④若[Qlt;N]，則需從臨界層[Fi]中選擇[N?Q]個個體。首先嘗試按參考點關(guān)聯(lián)選擇，計算個體與參考點的關(guān)聯(lián)度，并選擇最適合的個體加入[Q]。若參考點關(guān)聯(lián)過程中發(fā)生異?；蛉詿o法選取足夠的個體，則從剩余個體中隨機選擇 [N?Q]個個體加入[Q]。⑤輸出選擇集[Q]作為下一代種群。

3 仿真實驗及分析

為驗證算法在解決多目標柔性作業(yè)車間調(diào)度問題上的性能，本文采用了改進后的NSGA-III算法，并選取了BRANDIMARTE［9］提出的10個標準測試算例中的中的 Mk01算例進行驗證。本文設(shè)定的3個目標函數(shù)分別為完工時間最小、最小化設(shè)備總能耗及最小化機器負荷。

仿真實驗在配置為64位Windows10操作系統(tǒng)、Intel（R）Core（TM）i5-5600 CPU@3.60GHz處理器及NVIDIA RTX2060 Super GPU的個人計算機上進行。實驗參數(shù)設(shè)置見表2。

在多次仿真實驗中，本文將改進后的算法與原始的NSGA-III算法和NSGA-II算法進行了對比。圖6和圖7分別展示了 NSGA-III算法和本文改進算法在完工時間、機器負荷變化和能耗變化方面的最大值、最小值和平均值。對比圖6和圖7，可以明顯看出，相較于原始的 NSGA-III算法，本文改進的NSGA-III算法具有更穩(wěn)定的收斂曲線。特別是在對比最大完工時間、最大機器負荷、最大能耗與最小完工時間、最小機器負荷、最小能耗的曲線時，本文算法的極差更小，平均值更穩(wěn)定，展現(xiàn)出更強的魯棒性。這對于解決復(fù)雜多變的多目標柔性作業(yè)車間調(diào)度問題尤為重要。隨后，在相同的參數(shù)和算例下，本文對改進后的算法、原始的NSGA-III算法和NSGA-II算法分別進行了 200 次仿真實驗，并選取了一組最優(yōu)結(jié)果進行對比（見表3）。從表 3 可以看出，在解決多目標優(yōu)化的柔性車間調(diào)度問題上，本文算法明顯更為有效。利用本文改進算法進行仿真實驗，得到的最優(yōu)調(diào)度甘特圖見圖 8 。

4 結(jié)語

針對多目標綠色柔性作業(yè)調(diào)度問題，本文提出了一種基于改進NSGA-III算法的求解策略。首先，構(gòu)建了旨在最小化最大完工時間、設(shè)備總能耗及設(shè)備總負荷的優(yōu)化模型。其次，通過與標準算例數(shù)據(jù)集上原始NSGA-III和NSGA-II算法的對比實驗，結(jié)果表明，改進后的NSGA-III算法在求解多目標柔性作業(yè)車間問題時展現(xiàn)出更高的求解效率。

盡管本文取得了一定的研究成果，但是仍存在不足之處。首先，實驗僅在標準算例數(shù)據(jù)集上進行，其規(guī)模和復(fù)雜度相對有限。在實際生產(chǎn)環(huán)境中，調(diào)度問題可能面臨更多約束條件，如工件動態(tài)到達、機器故障等，這些因素尚未納入本研究范疇。其次，模型中的綠色優(yōu)化目標主要集中于設(shè)備能耗，對工件運輸能耗及其他環(huán)境因素考慮不足，這可能影響算法在實際綠色生產(chǎn)環(huán)境中的適用性。未來的研究可以從以下幾個方向展開：①引入動態(tài)調(diào)度。針對車間中的動態(tài)事件（如工件臨時插單、設(shè)備故障）進行擴展性研究，以提升算法的實時適應(yīng)能力。②多樣化綠色目標。將優(yōu)化目標擴展至包括運輸能耗、工件排放等因素，構(gòu)建更全面的綠色調(diào)度優(yōu)化模型。③大規(guī)模問題求解。針對更大規(guī)模、復(fù)雜度更高的實際問題，研究如何提高算法的收斂速度及解的多樣性，例如結(jié)合元啟發(fā)式算法或分布式計算技術(shù)。

通過持續(xù)改進和擴展，期望本文提出的方法能在更復(fù)雜和多變的實際場景中展現(xiàn)更廣泛的應(yīng)用潛力，為綠色制造領(lǐng)域提供更高效的解決方案。

5 參考文獻

［1］RIFAI A P，NGUYEN H T，AOYAMA H，et al.Non-dominated sorting biogeography-based optimization for bi-objective reentrant flexible manufacturing system scheduling［J］. Applied Soft Computing，2018，62：187-202.

［2］GONZALO M，JORDI P.Multiobjective scheduling algorithm for flexible manufacturing systems with petri nets［J］.Journal of Manufacturing Systems，2020，54：272-284.

［3］谷鵬飛.基于改進遺傳算法的多目標柔性作業(yè)車間調(diào)度問題的研究［D］.長沙：湖南工業(yè)大學，2023.

［4］DEB K，JAIN H.An evolutionary many-objective optimization algorithm using referencepoint-based nondominated sorting approach， part I： solving problems with box constraints［J］.IEEE Transactions on Evolutionary Computation，2014，18（4）：577-601.

［5］楊草原，鄧永濱，孫孟珂.基于NSGA-Ⅲ算法的多目標柔性作業(yè)車間調(diào)度問題研究［J］.信息技術(shù)與信息化，2021（12）：121-123.

［6］宋存利，朱建偉，李金泰.基于NSGA-Ⅲ算法求解柔性作業(yè)車間調(diào)度問題［J］.機電工程技術(shù)，2024，53（5）：11-15，85.

［7］陳勇，張詠秋，王宸，等.基于改進NSGA-Ⅲ的商用車車廂底板生產(chǎn)批量調(diào)度［J］.組合機床與自動化加工技術(shù)，2024（8）：185-192.

［8］歐陽洪才，張桐瑞，吳定會.基于改進NSGA-Ⅲ算法的多目標柔性作業(yè)車間調(diào)度［J］.控制工程，2023，30（1）：105-112.

［9］BRANDIMARTE P.Routing and scheduling in a flexible job shop by tabu search［J］.Annals of Operations Research，1993，41（3）：157-183.

*湖南省研究生科研創(chuàng)新項目“柔性車間調(diào)度中動態(tài)調(diào)度的策略與算法研究”（QL20230260）。

【作者簡介】李長云，男，湖南耒陽人，博士，教授，研究方向：軟件自動化、物聯(lián)網(wǎng)應(yīng)用技術(shù)、計算機工業(yè)控制；肖鴻洲（通信作者），男，湖南長沙人，在讀碩士研究生，研究方向：車間調(diào)度；王志兵，男，湖南邵東人，碩士，副教授，研究方向：可信軟件、知識圖譜；李霆譽，男，四川成都人，碩士，研究方向：車間調(diào)度。

【引用本文】李長云，肖鴻洲，王志兵，等.基于改進的NSGA-III算法求解綠色柔性作業(yè)車間調(diào)度問題［J］.企業(yè)科技與發(fā)展，2024（12）：97-102.