基于多目標生物地理學優化算法的模糊節能分布式流水車間調度

摘要： 研究了模糊節能分布式置換流水車間多目標調度問題（Fuzzy Energy EfficientDistributed Permutation Flow Shop Problem，FEEDPFSP），針對最小化模糊完工時間和模糊能耗兩個優化目標， 提出了一種基于生物地理學的多目標優化算法（Multiple-ObjectiveBiogeography-Based Optimization，MOBBO）。在MOBBO 中，設計了一種有效的初始解生成規則，并根據兩個優化目標之間的關系，設計了4 種速度操作方法用于遷移過程和變異過程，并且引入快速非支配排序以及擁擠距離方法，保證每次迭代的種群質量。對比兩個先進算法在480 個不同規模實例下的表現，驗證了所提出的MOBBO 算法在解決FEEDPFSP 問題的有效性。

關鍵詞：分布式流水車間調度；生物地理學優化；模糊規劃；節能；多目標優化

中圖分類號：TB497; TP18 文獻標志碼：A

當今世界正面臨兩大嚴峻挑戰：全球變暖和能源危機[1]。據估計，從2010 年到2040 年，全球能源消耗將以56% 的速度不斷增長，其中工業制造將占據50% 的能源消耗[2]。在此背景下，節能調度逐漸成為調度領域研究的熱點。

Mouzon 等[3] 試圖通過生產調度降低能耗，他們采用機器的啟動/關閉調度框架，成功地降低了整體能耗。在進一步的研究中，Mouzon和Yildirim[4] 提出了一種貪婪隨機自適應搜索算法，以求解多目標優化調度。近年來，針對節能調度問題，采用“開-關”策略平衡最大完工時間和總能耗[5]。然而，頻繁的開關機會在一定程度上減少機器的使用壽命[6]，因此這種策略存在一定的局限性。針對制造過程中機器不能完全關閉的情形，一種速度縮放策略被廣泛應用，該策略假定機器的能量消耗與其運行速度成正比。Wang 等[7] 提出的基于知識的協作算法通過對關鍵路徑上的工件進行加速和非關鍵路徑上的工件進行減速，以期實現最大完工時間和總能耗的同時優化。

置換流水車間調度問題是一個具有廣泛應用背景的典型調度難題，當機器數大于3 時，已被證明是NP-hard 問題[8]。隨著社會工業的發展，分布式置換流水車間調度問題（DPFSP）引起了越來越多研究者的關注。對于DPFSP 問題的研究最初由Naderi 和Ruiz[9] 展開。此后，越來越多的學者參與研究DPFSP及其變體，并提出了許多高性能算法。在單目標方面，Wang 等[10] 提出了一種有效的分布估計算法解決DPFSP，該算法建立了概率模型描述解空間的概率分布，并提供一種機制更新概率模型與上級個體。黃佳琳等[11] 提出了一種改進的生物地理學優化算法，以最小化最大完工時間為目標，求解分布式裝配置換流水車間調度問題。在多目標方面，Deng 等[12]提出了一種競爭模因算法，解決具有完工時間和總拖期準則的多目標DPFSP。

上述相關文獻都是在工件加工時間確定的前提下進行研究，然而在實際的制造過程中存在各種不確定因素，包括模型固有的不確定性（如動力學常數）、過程固有的不確定性（如加工時間）、外部不確定性（如產品需求）以及離散不確定性（如機器故障等）[13]。因此，研究不確定環境下的生產調度問題具有重要意義。Zheng 等[14] 將分布估計算法和迭代貪婪搜索巧妙結合，提出了一種針對具有模糊加工時間和模糊到期時間的多目標分布式混合流水車間調度問題的協同進化算法。Behnamian 等[15] 考察了具有模糊任務操作時間、到期日期和順序相關設置時間的雙目標混合流水作業調度問題，并提出了一種雙層算法，旨在同時最小化完工時間和總提前/拖期。總的來說，在模糊操作時間的前提下，節能多目標調度領域的研究相對有限，尋找有效的調度方法仍然是值得深入研究的方向。

本文研究了具有模糊加工時間的多目標分布式置換流水車間調度問題，兩個優化目標分別為模糊完工時間以及模糊總能耗。為了解決這一問題，首先引入了三角模糊數表征模糊加工時間；其次，為了得到Pareto 解集，提出了一種基于生物地理學的多目標優化算法（MOBBO），通過數值比較實驗驗證了所提出的MOBBO 算法的有效性。

1 模糊節能分布式置換流水車間調度問題

引入三角模糊數描述加工時間與能耗不確定性。對于一個三角模糊數T? = （t1， t2， t3），t1 lt; t2 lt; t3。

T?的期望值分別為：（1）E1（T? ） = （t1 +2t2 +t3）／4；（2）E2（T? ） = t2；（3）E3（T? ） = t3 -t1。判斷兩個三角模糊數的大小：（1） 若E1（?A） gt; E1（?B），則?Agt;?B；（2） 若E1（?A） = E1（?B）、E2（?A） gt; E2（?B），則?Agt;?B；（3） 若E1（?A） = E1（?B）、E2（?A） = E2（?B）、E3（?A） gt; E3（?B），則?Agt;?B。

設有F個相同的工廠，每個工廠都擁有m臺機器。共有n個工件需要進行加工，每個工件可以分配至任意工廠。工件i（i = 1，2，…，n）必須按照機器1 ～ m的順序依次進行加工， 其工序為｛Oi，1，Oi，2，…，Oi，m｝。對于每臺機器， 有s（v = 1，2，…， s）個不同等級的運行狀態，Vv表示機器在等級v下的加工速度。機器在加工過程中速度不能發生改變。工件i在每臺機器j（ j = 1，2，…，m）上的標準加工時間為ti， j，其中t1 lt; t2 lt; t3。如果工序Oi， j以速度等級v進行加工，則Oi， j的實際加工時間為?pi， j = ?ti， j／Vv，單位運行能耗為PPj，v。如果機器 j上沒有工件需要處理， 則該機器處在待機模式， 其單位能耗為SPj。πf = ｛πf （1），πf （2），…πf （nf ）｝表示工廠f 的加工序列，?Ci， j表示工件i 在機器j 上的模糊完工時間，～PECf， j和～SECf， j分別表示工廠f 中機器j 的運行能耗與待機能耗，則最大模糊完工時間?Cmax和總能耗～TEC計算如下：

2 MOBBO 算法

生物地理學優化算法（Biogeography-BasedOptimization， BBO）由Simon 在2008 年提出[16]。在BBO 中，每個棲息地被視為一個個體，通過棲息地適宜度指數描述該棲息地的質量。基于BBO 的優越性，越來越多的學者采用該算法解決各種優化問題，如Zhang 等[17-18] 利用BBO 算法解決大規模調度問題等。本節將詳細介紹MOBBO 算法的編碼和解碼方法、速度調整策略、種群初始化、遷移過程以及變異過程。

2.1 編碼與解碼

在本算法中，一個完整的解可以分為兩部分，一部分是工件編碼π，另一部分是速度編碼V。π采用vector數據結構表示，其包含兩點信息：工件的工廠分配和工件加工順序。V是n×m階矩陣，表示工件在對應機器的加工速度。因此，一個完整的解可表示為П = （π，V）。

為了更好地解釋本文算法采用的編碼方式，以2 工廠6 工件為例，假設每個工廠有3 臺機器，且機器有3 種不同的加工速度，則每個工件在每臺機器上的標準時間以及每臺機器在不同速度下的運行能耗以及待機能耗分別如表1、表2 所示。

步驟4：判斷當前工件在當前機器的模糊完工時間是否大于前一個工件在下一臺機器上的模糊完工時間，若大于則加速，直至加速到滿足條件或者最大值為止；

步驟5：隨機設置每個工件在最后一臺機器上的加工速度，得到速度矩陣V。

2.4 遷移過程

遷移操作的目的就是在不同的解之間進行信息分享。在本算法中，對當前種群Pt中所有解進行快速非支配排序[19] 得到各個解的等級（rank），HSI 計算如下：

HSIi =1／ranki（9）

采用余弦遷移模型，遷入率（ λi ）和遷出率（ λi ）的計算公式如下：

其中，I 表示最大遷入率，E 表示最大遷出率。

在MOBBO 算法中，對于滿足條件rand（0， 1） lt; λi的解作為遷入解πi，并從rank = 1的解中隨機挑選一個作為遷出解πe 進行遷移操作，具體步驟如下：

步驟1：確定遷入解πi和遷出解πe，計算兩者rank之差d = ranki -ranke；

步驟2：隨機選擇某一工廠f，并從πe的f 工廠中隨機選擇 個連續工件；

步驟 3：將 d 個工件遷移到 πi的相同位置。存在3 種情況，對于在索引范圍內的工件進行交換操作，對于超出索引范圍的工件進行插入操作；

步驟 4：遷移完成后對 πi 中所有工廠執行Accelerate2 或Decelerate2 操作，保留較優解。

對于不滿足 rand（0，1） lt; λi條件的解，設計以下4 種自提升策略（self-improvement）改善解的質量：

（1） SI1：從工廠Fc中隨機選擇工件J*，從另一個工廠k中隨機選擇工件Jk，然后交換J*和Jk的位置。

（2） SI2：從工廠Fc中隨機刪除一個工件，并將其隨機插入到另一個工廠中隨機位置。

（3） SI3：從工廠 Fc中隨機選擇兩個工件并交換它們的位置。

（4） SI4：從工廠Fc中隨機選擇一個作業，并將其插入到Fc中原位置外隨機位置。

其中：Fc代表關鍵工廠，若執行加速操作，Fc為模糊完工時間最大工廠Fm·；若執行減速操作，Fc為模糊能耗最大工廠Fe。隨機執行其中一種操作后，對所有工廠執行Accelerate1操作或Decelerate1操作，保留較優解。

2.5 變異過程

本算法設計了mu1、mu2 兩種變異算子，介紹如下： （1） mu1：隨機從關鍵工廠Fc中選擇一個工件Jc，隨機選擇一個工廠k，將Jc與該工廠內所有工件依次進行交換操作，交換完成后對進行操作的工廠執行Accelerate1 操作（Fc = Fm）或者Decelerate1 操作（Fc = Fe），保留最優解。（2）mu2：隨機從關鍵工廠Fc中選擇一個工件Jc，隨機選擇一個工廠k，將Jc依次插入到該工廠所有位置，插入完成后對進行操作的工廠執行Accelerate1操作（Fc = Fm）或者Decelerate1操作（Fc = Fe），保留最優解。

2.6 MOBBO 總流程

首先，利用半規則半隨機方法生成初始種群；其次，對當前種群進行快速非支配排序并生成非支配解集；之后，執行遷移和變異操作，速度調整策略包含在該過程當中；最后，對新種群進行快速非支配排序以及計算擁擠距離，保留前Popsize 個最優解進入下一次迭代，并更新非支配解集。具體偽代碼如下：

1 Initialize the population， half using SS rule and half randomly generated;

2 Fast non-dominated sort and initialize AS;" "Nondominated solution set

3 For i = 1 ～ Popsize" "Execute twice， Accelerate1 and Decelerate1

4 If rand（0，1）lt; λi

5 Pt（i） perform migration operation;

6 Else

7 Pt（i） perform SI1～ SI4 randomly;

8 End if

9 End for

10 For i = 1 ～ 2 × Popsize

11 If i lt; Popsize

12 Qt（i） = Pt（i） ;

13 Qt（i） execute mu1 or mu2 randomly， then performing Accelerae1 operation;

14 Else

15 Qt（i） = Pt（iPopsize） ;

16 Qt（i） execute mu1 or mu2 randomly， then performing Decelerate1 operation;

17 End if

18 End for

19 Fast non-dominated sort and calculate the crowding distance;

20 Update the AS;

21 Keep the top Popsize optimal solutions and enter the next iteration

3 數值結果和比較

為了測試MOBBO 在求解FEEDPFSP 時的性能， 使用480 個算例進行實驗。其中n = ｛20，40，60，80｝，m = ｛4，8，16｝，F = ｛2，3，4，5｝，對于｛n，m，F｝每個組合，隨機生成10 個算例。每個工件的標準處理時間為ti， j = （t1， t2， t3），其中最有可能時間t2在[5，50]范圍內隨機生成， 最樂觀值t1 = 0.85t2，最悲觀值t3 = 1.3t2[20-21]。機器加工速度V為{1，1.3，1.55，1.75，2.1}，v = ｛1，2，3，4，5｝[7]。能耗與速度的關系：（1）單位運行能耗與速度的關系：PPf， j，v = 4×Vv×Vv；（2）單位待機能耗：SPf， j = 1。MOBBO 算法基于VisualStudio 2021 C++ 編碼實現，所有實驗實例均在PC 上進行計算，PC 配置為Microsoft Windows 11， Intel（R）Core（TM） i5-9300H CPU @ 2.40GHz /8GB RAM。

本文對比Knowledge-Based Cooperative Algorithm（KCA）[7] 和Non-dominated Sorting Genetic Algorithm-II（NSGA-II）[19] 兩個算法。NSGA-II 作為求解多目標問題的經典優化算法其性能早已被相關學者證明，而KCA 算法在解決節能分布式調度問題上的優越性也在文獻[7] 中得到驗證。為了進行公平比較，在數值測試中，使用0.5×nCPU 時間（單位：s）作為算法的停止標準。由于FEEDPFSP 是一個模糊多目標優化問題，利用式E1（T? ） = （t1 +2t2 +t3）／4將實驗結果由三角模糊數轉化為浮點數進行對比以及繪制Pareto 前沿，并采用以下兩個標準[22] 評價所獲得的Pareto 解集的質量：

（1） Overall Nondominated Vector Generation（ONVG）：計算所獲得的Pareto 集合PF中的非支配解的數量，表示為｜PF｜。

（2）C-metric：測量兩個Pareto 集合PF1和PF2中的解之間的支配關系。C（PF1，PF2）計算如式（12）所示，它反映了PF2中的解被PF1中的解支配或與PF1中的解相同的百分比：

當C（PF1， PF2）gt;C（PF2， PF1） 時，說明PF2 受PF1 支配的解多于PF1 受PF2 支配的解， 即Pareto 集合PF1 優于PF2。

3.1 參數設置

MOBBO 算法包含一個重要參數： 種群大小Popsize。為了研究其對MOBBO 性能的影響，將其設置為4 個不同水平{50，100，150，200}進行實驗分析。同時為了防止過擬合， 隨機生成校正算例：n = ｛20，40，60，80｝，m = ｛4，8，16｝，F = ｛2，3，4｝共36種不同組合。采用貢獻度CON[7] 作為衡量在不同參數水平下Pareto 解集質量的指標，CON 值越大說明解的質量越好。在測試所有實例之后，計算每個水平下的平均CON 作為響應變量值（RV） ， 計算后得到4 個水平下的RV 值為{0.245 824， 0.256 858，0.251 954，0.245 364}，可以看出當Popsize 為100 時效果最好，其中黑體數值表示計算結果對比最優值。

3.2 消融實驗

為了驗證各改進策略的有效性， 本節對比MOBBO 算法和3 種算法變體的性能指標。3 種算法變體分別為去除遷移策略（B1） 、去除變異策略（B2）和去除速度調整策略（B3）。表3～表5 分別示出了 B1、B2、B3 與 MOBBO 的 C-metric 指標對比（表中加黑數據為對比較優結果）。從表中可以看出，當分別去除遷移、變異和速度調整策略后，算法的性能普遍下降，表明3 種策略對MOBBO 算法均起到了重要作用。圖2 示出了MOBBO算法與去掉遷移、變異和速度調整策略后在不同算例上的Pareto 前沿對比，其中，“I-80-8-5”中“80”代表工件數量，“8”代表機器數量，“5”代表工廠數，其他同理。

3.3 MOBBO 算法與其他算法比較

將MOBBO 與KCA、NSGA2 進行比較，所有算0：5 nC-metric法都以 CPU 時間（單位：s）作為停止準則。為了對3 種算法進行全面比較，計算各個算法在不同實例下的Pareto 集合，并根據評價指標計算得到平均ONVG（Overall Nondominated Vector Generation）以及值，實驗結果分別如表6 和表7 所示。

從表6 中可以看出， MOBBO 算法的ONVG值在每個（n，m） 組合上都大于KCA 和NSGA2 的ONVG值，表明在相同時間內， MOBBO 算法能夠獲得比KCA 和NSGA2 更多的非支配解。這是由于Accelerate2（f） 和Decelerate2（f） 兩種速度調整策略增強了算法在某一目標上的搜索能力，有效地擴大了算法的搜索范圍。由表7 可知，幾乎在所有的（n，m）組合上，C（MOBBO， KCA）≈1，C（KCA， MOBBO）≈0，這意味著幾乎所有的KCA 算法得到的非支配解都被MOBBO得到的非支配解支配。對比MOBBO 和NSGA2，除了在工廠數F=2、（n，m） 為（20，4） 和（20，8）兩種組合下，MOBBO 結果略差于NSGA2，其余規模下C（MOBBO， NSGA2）gt;C（NSGA2， MOBBO）。由于變異過程擴大算法搜索深度，并結合4 種速度調整策略，有效提高了算法搜索效率，使得算法在規定時間內表現更好。

4 結束語

為了解決以最小化最大完工時間以及最小化總能耗為優化目標的模糊節能分布式置換流水車間調度問題（FEEDPFSP） ， 提出了一種有效的MOBBO算法。通過大量的數值實驗，驗證了所提出的MOBBO算法在解的質量和多樣性方面相較于現有算法表現更為出色。這表明該算法在解決FEEDPFSP問題時具有更好的性能，并能夠產生更優質和多樣性的解決方案。未來的工作將聚焦更多目標下的模糊節能分布式置換流水車間調度問題，包括帶有拖期約束或者機器準備時間約束等情形，致力于設計更加高效的模糊分布式流水車間調度算法。此外，將所研究的算法應用于真實的工業問題也將成為我們未來研究的重要方向。

參考文獻：

[ 1 ]ZHAO F Q， HE X， WANG L. A two-stage cooperativeevolutionary algorithm with problem-specific knowledgefor energy-efficient scheduling of no-wait flow-shopproblem[J]. IEEE Transactions on Cybernetics， 2020，51（11）： 5291-5303.

[ 2 ]WANG G C， LI X Y， GAO L， et al. Energy-efficientdistributed heterogeneous welding flow shop schedulingproblem using a modified MOEA/D[J]. Swarm and EvolutionaryComputation， 2021， 62： 100858.

[ 3 ]MOUZON G， YILDIRIM M B， TWOMEY J. Operationalmethods for minimization of energy consumption of manufacturingequipment[J]. International Journal of ProductionResearch， 2007， 45（18/19）： 4247-4271.

[ 4 ]MOUZON G， YILDIRIM M B. A framework to minimisetotal energy consumption and total tardiness on a singlemachine[J]. International Journal of Sustainable Engineer-ing， 2008， 1（2）： 105-116.

[ 5 ]DAI M， TANG D B， GIRET A， et al. Energy-efficientscheduling for a flexible flow shop using an improvedgenetic-simulated annealing algorithm[J]. Robotics andComputer-Integrated Manufacturing， 2013， 29（5）： 418-429.

[ 6 ]CHE A D， WU X Q， PENG J， et al. Energy-efficientbi-objective single-machine scheduling with power-downmechanism[J]. Computers amp; Operations Research， 2017，85： 172-183.

[ 7 ]WANG J J， WANG L. A knowledge-based cooperativealgorithm for energy-efficient scheduling of distributedflow-shop[J]. IEEE Transactions on Systems， Man， andCybernetics： Systems， 2018， 50（5）： 1805-1819.

[ 8 ]GAREY M R， JOHNSON D S， SETHI R. The complexityof flowshop and jobshop scheduling[J]. Mathematics ofOperations Research， 1976， 1（2）： 117-129.

[ 9 ]NADERI B， RUIZ R. The distributed permutation flowshopscheduling problem[J]. Computers amp; OperationsResearch， 2010， 37（4）： 754-768.

[10]WANG S Y， WANG L， LIU M， et al. An effectiveestimation of distribution algorithm for solving the distributedpermutation flow-shop scheduling problem[J]. InternationalJournal of Production Economics， 2013， 145（1）： 387-396.

[11]黃佳琳， 張丫丫， 顧幸生. 基于改進生物地理學優化算法的分布式裝配置換流水車間調度問題[J]. 華東理工大學學報（自然科學版）， 2020， 46（6）： 758-769.

[12]DENG J， WANG L. A competitive memetic algorithm formulti-objective distributed permutation flow shop schedulingproblem[J]. Swarm and Evolutionary Computation，2017， 32： 121-131.

[13]PISTIKOPOULOS E N. Uncertainty in process design andoperations[J]. Computers amp; Chemical Engineering， 1995，19： 553-563.

[14]ZHENG J， WANG L， WANG J J. A cooperativecoevolution algorithm for multi-objective fuzzy distributedhybrid flow shop[J]. Knowledge-Based Systems， 2020，194： 105536.

[15]BEHNAMIAN J， GHOMI S. Multi-objective fuzzy multiprocessorflowshop scheduling[J]. Applied Soft Computing，2014， 21： 139-148.

[16]SIMON D. Biogeography-based optimization[J]. IEEETransactions on Evolutionary Computation， 2008， 12（6）：702-713.

[17]ZHANG Y Y， GU X S. Biogeography-based optimizationalgorithm for large-scale multistage batch plantscheduling[J]. Expert Systems with Applications， 2020，162： 113776.

[18]ZHANG Y Y， GU X S. A biogeography-based optimizationalgorithm with modified migration operator for large-scale distributed scheduling with transportation time[J].Expert Systems with Applications， 2023， 231： 120732.

[19]DEB K， PRATAP A， AGARWAL S， et al. A fast and elitistmultiobjective genetic algorithm： NSGA-II[J]. IEEETransactions on Evolutionary Computation， 2002， 6（2）：182-197.

[20]SUN L， LIN L， GEN M， et al. A hybrid cooperative coevolutionalgorithm for fuzzy flexible job shopscheduling[J]. IEEE Transactions on Fuzzy Systems， 2019，27（5）： 1008-1022.。

[21]SHAO Z S， SHAO W S， PI D C. Effective heuristics andmetaheuristics for the distributed fuzzy blocking flow-shopscheduling problem[J]. Swarm and Evolutionary Computation，2020， 59： 100747.

[22]LI B B， WANG L， LIU B. An effective PSO-based hybridalgorithm for multiobjective permutation flow shopscheduling[J]. IEEE Transactions on Systems， Man， andCybernetics-Part A： Systems and Humans， 2008， 38（4）：818-831.

（責任編輯：李娟）

基金項目： 國家自然科學基金（61973120）