用于分布式置換流水變速車間的雙種群算法

摘要針對加工速度可變的分布式置換流水車間調度問題，以最大完工時間和機器總能量消耗為優化目標，提出了一種雙種群算法．首先，采用混合四種策略的初始化方法來生成高質量的初始種群．其次，針對兩個種群的特點分別設計了特定的進化方式，并引入了動態引導因子調整種群的進化方式．同時，提出調速節能策略，進一步優化能量消耗．最后，提出動態種群策略用于平衡兩個種群的資源．通過仿真實驗證明了各個策略的有效性，并與其他算法進行了對比，結果表明所提出的算法具有明顯的優越性．

關鍵詞置換流水車間;雙種群算法;分布式;變速車間;多目標優化

中圖分類號TP18

文獻標志碼A

0 引言

在制造業中，合理的調度能夠大幅地提高生產效率、提高資源利用率，減少浪費．置換流水車間調度問題（Permutation Flowshop Scheduling Problem，PFSP）作為一種典型調度問題，在大規模制造生產中得到廣泛應用．通過將生產過程分為多個步驟，并有序地安排在專門設計的生產線上，PFSP顯著提高了生產效率．然而，當機器的數量大于3個時，該問題已經被證明是NP難問題［1］．目前，設計有效的元啟發式算法是求解PFSP的主流方法．

隨著工業技術和全球貿易的不斷發展，企業訂單數量急劇上升，生產商意識到分布式生產模式的多工廠協同才能滿足市場和客戶需求，適應不斷變化的生產環境［2］．分布式調度可讓多個工廠協同生產，其關鍵優勢在于其較高的生產效率和資源利用率［3］．Naderi等［4］首先提出了分布式置換流水車間調度問題（Distributed Permutation Flowshop Scheduling Problem，DPFSP）．DPFSP需要將作業分配給工廠，并確定每個工廠內作業的加工順序，相較于PFSP更加復雜．為了解決DPFSP，Li等［5］提出一種改進的人工蜂群算法，設計了基于工作量平衡的初始化方法和局部搜索策略，通過實驗測試，證明了算法搜索的高效性;此外，Zhao等［6］改進了水波算法并設計了4種局部搜索方法，在優化具有阻塞的DPFSP時表現出優異性．

然而，針對DPFSP的相關研究顯示，許多學者并沒有考慮到加工速度對調度的影響，或者假設速度是恒定的．實際生產中，制造業的智能化發展加速，機器的加工速度靈活化成為了滿足多種材料特性和工藝需求的必要條件．可變加工速度的DPFSP（Distributed Permutation Flowshop Scheduling Problem with Variable Processing Speed，DPFSP-VPS）可根據實時情況進行動態調度，從而提高生產效率并降低成本，有效地減少制造過程中的等待時間和排隊時間［7］，展現出了巨大的應用潛力．如今，學者們逐漸意識到DPFSP-VPS 研究的重要性，例如：Huang等［8］指出數控機床變速加工的重要性，并提出一種雙角色協同進化算法，設計了針對機器速度的多種局部搜索策略，實驗結果表明了算法的優越性;Wang等［9］提出一種基于知識的協同進化算法，設計了多個協同搜索策略，并采用了基于關鍵路徑的方法來進一步提高算法性能;Wang等［10］提出一種針對DPFSP-VPS的改進多目標鯨魚群算法，能夠在不影響生產效率的情況下提高能源效率，并針對完工時間和機器速度提出了更新利用機制．

同時，隨著資源的過度消耗和全球變暖形勢的日益嚴峻，提高環境的可持續性已成為一個迫切的問題，環保組織已開始提倡各種制造領域的節能降耗［11］．在此背景下，企業在調度中考慮能耗已經成為轉型升級的必然趨勢．不僅在PFSP［12］中，在混合車間［13］和柔性作業車間［14］等領域，節能調度也得到了廣泛的研究．本文的研究主要聚焦于同時考慮最大完工時間和總能量消耗兩個目標的DPFSP-VPS．兩個目標的優化帶來額外的困難，如何在算法中設計優秀的種群更新方式和有效策略成為研究的重點．

針對上述問題，本文提出一種雙種群算法（Dual-Population Algorithm，DPA）來求解雙目標的DPFSP-VPS．盡管雙種群概念已在多個領域有相關研究，但在DPFSP-VPS領域的應用極少．與以往研究不同的是，本文提出的DPA首先針對每個種群的特性設計了不同的進化方式;其次，完全舍棄了其他算法中固定的交叉變異概率，通過引入動態引導因子來指導算法的進化方向;同時，兩個種群在更新的過程中種群數量也在動態變化，這種靈活性能夠平衡兩種群的計算資源;最后，設計了變速節能策略來降低調度中能量消耗．實驗結果表明，本文所提算法在解決DPFSP-VPS問題上高效可行，相較于其他算法具有較大的競爭性．

1 分布式置換流水變速車間調度問題

1.1 問題描述

DPFSP-VPS 可描述為n個工件，在F個工廠加工．每個工廠都是一個包含m個機器的置換流水車間問題，即每個工件都包含m道工序．在DPFSP-VPS中，首先為每個作業分配工廠，確定工廠內作業的處理順序，然后還需要為每個操作選擇機器的處理速度．每道工序Oi，j在每個機器上均有一個標準的處理時間ti，j，若Oi，j的處理速度為Vv，則其真實的處理時間為pi，j=ti，j／Vv，其加工能耗與pi，j和V2v成正比．因此，加工速度越大，加工時間越短，但加工能耗越大．

關于DPFSP-VPS的假設如下：

1）所有機器可在零時刻開始加工;

2）每個工件可在任一工廠加工，但標準加工時間不同，具有異構性;

3）每個工件選定工廠后，則其所有工序均在此工廠加工完成;

4）一個作業的任何操作必須完成其前面的操作后才能進行;

5）不考慮工件加工過程中發生中斷，不考慮機器發生故障．

1.2 數學模型

為了便于描述，對研究中所使用的符號進行了如下定義：

1）索引

j：機器索引，j ∈ ｛1，…，m｝;

f：工廠索引，f ∈ ｛1，…，F｝;

v：速度索引，v ∈ ｛1，…，s｝;

i：工件索引，i ∈ ｛1，…，n｝．

2）參數

n：工件的數量;

m：每個工廠的機器數量;

F：工廠數量;

s：加工速度的數量;

l：按順序排列的工件位置;

Vv：第v個處理速度;

Oi，j：第i個工件的第j道工序．

3）決策變量

ti，j：Oi，j的標準處理時間;

pi，j：Oi，j的真實處理時間;

PPf，j，v：工廠f中以速度v運行的機器j的單位能耗;

SPf，j：工廠f中機器j單位時間的待機能耗;

PECf，j：工廠f中機器j的加工能耗;

SECf，j：工廠f中機器j的空閑能耗;

TEC：總能耗;

Cmax：調度的最大完工時間;

Cl，j，f：工廠f中機器j上位置l的完成時間;

C（f）：工廠f的最大完工時間;

xi，l，f：二進制變量，如果作業i占用工廠f的位置l，則值為1，否則為0;

zi，j，v：二進制變量，如果作業i在機器j上以速度v處理，則值為1，否則為0．

DPFSP-VPS包括最大完工時間（Makespan）和總能量消耗（TEC）兩個目標．Makespan和TEC是兩個矛盾的目標，更小的Makespan意味更大的加工速度．但是，更大的加工速度會帶來更大的加工能耗．因此，為了更好地平衡兩個目標，需要有優秀的調度方案，以及合適的速度選擇．

第一個目標Makespan如式（1）所示：

第二個目標TEC計算方法見式（2）．TEC包括每個工廠中所有機器的加工能耗（PEC）和空閑能（SEC），PEC和SEC的計算方法分別如式（3）和式（4）所示．

根據上文的假設和實際的生產情況，DPFSP-VPS的約束如下：

式（5）確保每個工件只能分配給一個工廠;式（6）確保每個機器同一時刻只加工一個工件;式（7）確保每道工序只能在一個速度下進行加工;式（8）表示Oi，j的實際處理時間;式（9）表示工廠中第一臺機器從零時刻開始加工;式（10）確保Oi，j在Oi，j-1完工后才可加工;式（11）確保每臺機器不能同時加工多個工序;式（12）和（13）表示每個工廠的加工時間約束．

2 雙種群算法求解DPFSP-VPS

2.1 編碼解碼

對于DPFSP-VPS，包括3個子問題：1）確定每個工件加工的工廠;2）確定每個工廠內工件的處理順序;3）確定每道工序在每個機器上的處理速度．本研究根據3個子問題的特點采用三段式編碼，即工件編碼（JS）、工廠編碼（FS）、速度編碼（VS）．表1給出了一個7個工件、2個工廠和3種速度的DPFSP-VPS示例．根據JS和FS可知：有4個工件在工廠1處理，加工順序為｛1，5，3，7｝;有3個工件在工廠2處理，加工順序為｛6，2，4｝．每一個工件有3道工序，對應每個工廠內的3臺機器，根據VS可知每道工序的加工速度．假設每道工序的ti，j均為3 h，則根據表1生成的調度甘特圖如圖1所示．

解碼時，首先根據FS將所有工件分配給各個工廠，然后依照JS中的工件加工順序安排每個工廠內的工序加工序列，最后根據VS確定每道工序的加工速度．通過標準處理時間除以加工速度，可以得到真實的處理時間，并根據加工能耗與速度的平方正相關原則計算出總能耗．

2.2 混合種群初始化

有效的初始化方法能夠顯著提高初始種群的質量，不僅有利于算法的快速收斂，還會提高最終解的質量．本文根據不同的優化目標提出了4種初始化策略，最終由每種策略各生成1／4個體組成混合種群．

1）DNEH原則：DNEH（Distributed Nawaz Enscore Ham）［15］是在NEH基礎上針對最小化流經時間的DPFSP提出的．本文對其進行改進，應用于多目標DPFSP．首先將所有工件的加工時間降序排列，假設為｛3，2，4，1｝．若有2個工廠，則將加工時間最長的工件3和工件2分別分配給2個工廠，保證每個工廠均有工件．至于工件4和工件1則逐一插入到任何可能的位置，并進行非支配排序，最后保留最好的方案．

2）完工時間優先原則：首先隨機初始化JS和FS，然后將所有操作的VS設為最大．此操作能夠使完工時間最小化．

3）加工能耗優先原則：執行速度選擇時與策略2）相反，所有操作的VS被設為最小，以最小化加工能耗．

4）隨機初始化：初始種群的多樣性同樣對最終的解方案至關重要［16］．因此，本研究的一部分個體采用隨機初始化策略，即隨機初始化JS、FS和VS，這將有利于豐富種群的多樣性．

2.3 雙種群進化

本文提出的算法將所有個體分為2個種群，分別命名為精英種群（Elite Population，EP）和普通種群（Normal Population，NP）．在種群初始化完成后，根據非支配解集和擁擠度進行排序，初始時精英種群包含排名前50％的個體，剩余個體歸為普通種群．算法中針對不同種群設計了不同的進化方式．

2.3.1 EP進化

EP的進化方式有2種，如式（14）所示．其中，GF為引導因子，可對個體的進化方式進行引導．

EP中均是擁有優良基因的個體，因此，對其執行自我進化有利于優良基因的融合交叉，從而加速收斂過程．對于EP中的某個個體EP1，其自我進化方式為隨機選取另一個體EP2進行交叉進化．每個個體均包含3段編碼的信息，在進化過程中，針對JS采用部分匹配交叉（Partial Match Crossover，PMX）．圖2a給出了一個PMX的示例．首先，對2個個體隨機選擇2個不同的點并交換2點之間的排列生成2個后代;然后，對個體內存在的非法解進行映射，通過映射將重復的非法解替換成另一個體相同位置的工件，若映射后仍存在非法解，則再次進行映射．由于每個工件的工廠分配和速度設定不存在相關性，速度也不存在排列約束，因此，針對FS和VS采用統一交叉（Uniform Crossover，UX）．UX即隨機選取2個個體的對應的編碼進行交換，圖2b給出了一個關于FS的UX交叉的示意圖．最終通過EP1和EP2的自我進化，產生2個新個體EPnew1和EPnew2．

在進化過程中，EP會逐漸靠近帕累托前沿，可能會陷入局部最優．因此，本文針對EP設計了4種針對關鍵工廠的局部搜索．關鍵工廠即完工時間最長的工廠，關鍵路徑則為從開始到結束歷時最長的加工路徑．對關鍵路徑中的關鍵操作進行優化，將有利于跳出局部最優，找到更優解．4種局部搜索如下所示：

1）LS1：關鍵工廠內插入．在關鍵工廠內，隨機選擇一個關鍵操作，將其插入其他可能的位置．

2）LS2：關鍵工廠內交換．在關鍵工廠內，隨機選擇兩個關鍵操作，交換它們的位置．

3）LS3：關鍵工廠外插入．從關鍵工廠內，隨機選擇一個關鍵操作，將其插入到其他工廠可能的位置．

4）LS4：關鍵工廠內加速．隨機選擇一個關鍵操作，增大其處理速度．這將有利于降低Makespan．

2.3.2 NP進化

NP的進化方式也有兩種，如式（15）所示：

NP中為普通個體，為了加快其收斂速度，將NP與EP進行協同進化．具體而言，NP中的個體會隨機選擇EP中的一個個體作為進化引導對象．進化方法仍是對JS使用PMX，對FS和VS使用UX．通過這種協同進化，可以避免算法盲目搜索，加快搜索過程．

變異是增加種群多樣性的重要方式，NP中本就是較差的個體，對其進行變異會有更大的概率搜索到更優解．根據三段式編碼的特點，設計了相應的變異方式．對于JS，變異是隨機交換兩個位置的工件．對于FS，變異是隨機選擇一個工件重新分配給另一個工廠．對于VS，變異是隨機選擇一個操作并改變其處理速度．

2.4 動態引導因子

EP和NP的進化方式均受到引導因子GF的影響．為了在種群迭代的過程中動態調整2個種群的進化方式，對GF的大小進行動態調整，如式（16）所示：

其中：GFmin和GFmax分別為GF的最小值和最大值，本文設置GFmin=0.2，GFmax=0.8;Iter和MaxIter分別為當前迭代次數和最大迭代次數．在迭代的前期，GF較小，2個種群將進行充分的自我進化和協同進化，此階段是算法的快速收斂階段．迭代過程中，GF不斷增大，2個種群將更傾向于進行局部搜索和變異搜索．后期較大的GF可使 EP通過局部策略進行精細搜索，跳出局部最優，而NP則可通過變異增加種群多樣性．

通過GF的動態引導，可調節2個種群的分工，讓算法在不同階段利用不同的優化策略．同時，算法能夠在不同迭代階段更加靈活地進行搜索，從而提高算法的性能和收斂速度．

2.5 調速節能策略

總能耗是DPFSP-VPS的另一個重要目標，如何設計有效的節能技術是節能調度的關鍵．在DPFSP-VPS中，加工速度是造成Makespan和TEC兩個子目標相互沖突的關鍵因素．因此，本文設計了兩種針對空閑時間的調速節能策略．這兩種策略能夠調整機器的加工速度，可以在不影響Makespan的情況下降低能耗．

1）減速策略：當同一臺機器上的某個操作的開始時間大于上一個操作的結束時間時，就會產生空閑時間段．因此，可以降低空閑時間段前操作的加工速度，這樣在減少空閑時間的同時還能降低加工能耗．如圖3所示，將f1中O5，2，O5，3，O3，3加工速度變慢一檔，空閑時間T1和T2消失，T3減少一半．為了不影響Makespan，此操作只在非關鍵路徑上進行．

2）加速策略：某個工件的上一道工序加工時間過長同樣會產生空閑時間段．例如圖1中f2的O2，1加工時間過長造成O2，2的開始時間晚于O6，2的結束時間，產生了一段空閑時間．因此，適當地增大O2，1的加工速度，縮短其加工時間，即可提前O2，2的開始時間，減少空閑時間．如圖4所示，增大O2，1加工速度后既減少了空閑時間還降低了Makespan．在加速后會降低空閑能耗，但也會造成加工能耗增加，所以，此方法調速后需要判斷新解是否支配舊解．若新解支配舊解，則保留新解，否則舊解被保留．

減速策略能延長空閑時間段前一道工序的完工時間，加速策略能提前空閑時間段后一個工序的開始加工時間．兩種方式均可降低TEC，且不會增大 Makespan．對于以上兩種策略，設定各自隨機選取概率為0.5．另外，為避免復雜的運算，規定只有迭代超過總迭代次數的90％時才執行調速策略．

2.6 動態種群

兩個種群進化后，它們都會生成新的個體．這些新個體將與前一代的個體一同進行評價，根據擁擠度進行非支配排序．為保持種群數量的穩定，排名靠后的個體被淘汰，其余個體被選擇并進入下一次迭代．

在雙種群機制中，如何為兩個種群分配合適的個體資源很重要．因此，本文設計了一種正反饋動態種群分配機制，如式（17）所示：

其中：|POPnew|為某個種群本代進化后被選擇的個體數量;|POP|為該種群的個體總數．某個種群進化后，新生成個體被選擇的比例越大，DP越大．通過計算兩個種群的DP值，為取得較大DP值的種群在進入下一次進化時，額外分配5％的個體．通過計算兩個種群的子代存活率，可以判斷出當前哪個種群的進化效果更好．基于正反饋機制，為進化效果好的種群分配更多的個體，從而讓其獲得更多的資源，能夠進一步提高算法的性能．

2.7 算法框架

本文提出了一種解決DPFSP-VPS的雙種群算法，并為每個種群設計了不同的進化方式，算法的整體流程框架如圖5所示．

3 實驗結果與分析

3.1 實驗介紹

目前尚未有關于DPFSP-VPS的開源基準．本研究參考文獻［8］和［9］，基于Taillard基準生成了16個不同規模的實例，以n_m_F方式命名，具體的實例參數如表2所示．在異構工廠中，每個操作在不同工廠中的處理時間不同，工序的標準處理時間符合均勻分布U（1，99）．種群數量和迭代次數根據以往研究中的主流選擇，分別設置為100和200．所有代碼使用Matlab2019b編程，軟件的運行環境為：CPU：Intel（R） Core（TM） i9-9900K @3.60 GHz;RAM：64 GB，Win10．

由于真實的帕累托前沿未知，本文采用超體積度量（Hypervolume，HV）［17］作為評價指標．HV可以同時評價解的多樣性和收斂性，HV值越大說明算法的綜合性能越好．本文對每個問題均獨立運算20次，以確保結果的可靠性．

3.2 策略有效性驗證

表3展示了不同算法所擁有的策略．為了驗證各個策略對算法性能的影響，將這些算法進行對比測試．表4展示了算法20次運行求得的平均HV值，加粗體為最優值．可以看出，隨著策略的增加，算法的性能逐步提升．包含所有策略的DPA取得了最多的最優值，證實了各個策略對算法的性能均有提升．

3.3 對比實驗

為了進一步驗證DPA求解DPFSP-VPS的有效性，將其與主流的多目標進化算法進行對比，包括NSGA-Ⅱ、MOEA／D、SPEA2和專門用于DPFSP-VPS的新穎算法：BRCE［8］．表5展示了所有算法的平均HV值（Ave）和相對標準誤差（Dev），Dev為標準差與平均值的比值，表中加粗體為最優值．

正如表5所示，DPA的平均HV值和相對標準誤差均顯著優于其他對比算法，這表明DPA性能最佳且最穩定．此外，通過觀察表中的數據，可以發現隨著工件數量和機器數量的增加，算法的Ave均有不同程度的下降，但DPA的下降幅度是最小的．這主要歸因于隨著計算難度的增大，搜索空間不斷膨脹，在有限的計算資源下更難找到高質量的解．而EP的自我進化能夠在一部分空間進行精細搜索，NP的協同進化實現了不同空間的信息交流，兩種群不同的進化方式使得DPA能夠對解空間進行充分的搜索．復雜的多目標問題通常具有更多的局部最優解，這使得算法更易陷入局部最優．但是，DPA中的局部搜索以及變異搜索可有效地幫助算法跳出局部最優，避免了像其他算法那樣性能大幅下降．

表6展示了所有算法的Friedman秩和檢驗結果，其中DPA排名第一．此外P值為5.440 2×10-12，說明所有算法求得的結果具有明顯差異．這進一步驗證了DPA算法在求解多目標DPFSP-VPS時的優越性．

圖6展示了在實例20_10_2上，所有算法得到的帕累托前沿．可以觀察到DPA相比其他算法在分布性和收斂性方面表現更優．盡管在中部區域少部分解的質量稍遜于NSGA-Ⅱ和BRCE，但這是可接受的，因為DPA在兩個目標的極值區域進行了更充分的探索．得益于調速節能策略的有效性，DPA找到了能耗更低的調度方案．在實際生產中，這意味著DPA給出的方案更有能耗優勢．在圖6中的A點（827.6，26 142）附近，DPA相比第二名NSGA-Ⅱ（827，26 376）能耗節省了0.9％，相比最后一名MOEA／D（840.9，28 412）能耗節省了8.7％，證明了DPA在節能方面的有效性和實用價值．

4 總結

本文提出了一種雙種群算法，用于求解加工速度可變的分布式置換流水車間調度問題，同時優化最大完工時間和能量總耗．為了提高初始種群的質量，提出一種針對不同目標的混合初始化策略．針對兩個種群的特點，設計了不同的進化方式，實現了對解空間的充分探索．同時，設計了動態引導因子，可在迭代過程中動態引導種群的進化方式．提出了一種新穎的調速節能策略，可在不影響最大完工時間的情況下降低能量消耗．最后，基于正反饋的動態種群機制，合理地分配了兩個種群的資源．通過實驗驗證了各個策略的有效性，與其他算法的對比結果，證明了本文所提出的算法具有優異的性能．

參考文獻References

［1］Garey M R，Johnson D S，Sethi R.The complexity of flowshop and jobshop scheduling［J］.Mathematics of Operations Research，1976，1（2）：117-129

［2］ 軒華，李文婷，李冰.混合離散人工蜂群算法求解含不相關并行機的分布式柔性流水線調度［J］.控制與決策，2023，38（3）：779-789

XUAN Hua，LI Wenting，LI Bing.Hybrid discrete artificial bee colony algorithm for distributed flexible flowline scheduling with unrelated parallel machines［J］.Control and Decision，2023，38（3）：779-789

［3］ 王思涵，李新宇，高亮，等.分布式車間調度研究綜述［J］.華中科技大學學報（自然科學版），2022，50（6）：1-10

WANG Sihan，LI Xinyu，GAO Liang，et al.A review of distributed shop scheduling problems［J］.Journal of Huazhong University of Science and Technology （Natural Science Edition），2022，50（6）：1-10

［4］ Naderi B，Ruiz R.The distributed permutation flowshop scheduling problem［J］.Computers ＆ Operations Research，2010，37（4）：754-768

［5］ Li J Q，Bai S C，Duan P Y，et al.An improved artificial bee colony algorithm for addressing distributed flow shop with distance coefficient in a prefabricated system［J］.International Journal of Production Research，2019，57（22）：6922-6942

［6］ Zhao F Q，Shao D Q，Wang L，et al.An effective water wave optimization algorithm with problem-specific knowledge for the distributed assembly blocking flow-shop scheduling problem［J］.Knowledge-Based Systems，2022，243：108471

［7］ Jiang J W，An Y J，Dong Y F，et al.Integrated optimization of non-permutation flow shop scheduling and maintenance planning with variable processing speed［J］.Reliability Engineering ＆ System Safety，2023，234：109143

［8］ Huang K H，Li R，Gong W Y，et al.BRCE：bi-roles co-evolution for energy-efficient distributed heterogeneous permutation flow shop scheduling with flexible machine speed［J］.Complex ＆ Intelligent Systems，2023，9（5）：4805-4816

［9］ Wang J J，Wang L.A knowledge-based cooperative algorithm for energy-efficient scheduling of distributed flow-shop［J］.IEEE Transactions on Systems，Man，and Cybernetics：Systems，2020，50（5）：1805-1819

［10］ Wang G C，Gao L，Li X Y，et al.Energy-efficient distributed permutation flow shop scheduling problem using a multi-objective whale swarm algorithm［J］.Swarm and Evolutionary Computation，2020，57：100716

［11］ 羅聰，龔文引.混合分解多目標進化算法求解綠色置換流水車間調度問題［J／OL］.控制與決策：1-9［2023-07-20］.https：／／doi.org／10.13195／j.kzyjc.2022.2145

LUO Cong，GONG Wenyin.A hybrid multi-objective evolutionary algorithm based on decomposition for green permutation flow shop-scheduling problem［J］.Control and Decision：1-9［2023-07-20］.https：／／doi.org／10.13195／j.kzyjc.2022.2145

［12］ Fathollahi-Fard A M，Woodward L，Akhrif O.Sustainable distributed permutation flow-shop scheduling model based on a triple bottom line concept［J］.Journal of Industrial Information Integration，2021，24：100233

［13］ 吳秀麗，閆曉燕.基于改進Q學習的可重入混合流水車間綠色動態調度［J］.機械工程學報，2023，59（13）：246-259

WU Xiuli，YAN Xiaoyan.An improved Q learning algorithm to optimize green dynamic scheduling problem in a reentrant hybrid flow shop［J］.Journal of Mechanical Engineering，2023，59（13）：246-259

［14］ 徐明，張劍銘，陳松航，等.柔性作業車間調度問題的多目標優化算法［J］.計算機與現代化，2021（12）：1-6

XU Ming，ZHANG Jianming，CHEN Songhang，et al.Multi-objective optimization algorithm for flexible job shop scheduling problem［J］.Computer and Modernization，2021（12）：1-6

［15］ Pan Q K，Gao L，Li X Y，et al.Effective constructive heuristics and meta-heuristics for the distributed assembly permutation flowshop scheduling problem［J］.Applied Soft Computing，2019，81：105492

［16］ 丁美芳，吳克晴，肖鵬.多策略融合的黃金正弦樽海鞘群算法［J］.南京信息工程大學學報（自然科學版），2023，15（6）：662-675

DING Meifang，WU Keqing，XIAO Peng.Golden sine salp swarm algorithm with multi-strategy［J］.Journal of Nanjing University of Information Science ＆ Technology （Natural Science Edition），2023，15（6）：662-675

［17］ 王秋蓮，段星皓.基于高維多目標候鳥優化算法的柔性作業車間調度［J］.中國機械工程，2022，33（21）：2601-2612

WANG Qiulian，DUAN Xinghao.Scheduling of flexible job shop based on high-dimension and multi-objective migrating bird optimization algorithm［J］.China Mechanical Engineering，2022，33（21）：2601-2612

Dual-population algorithm for distributed permutation flowshop

scheduling problem with variable processing speed

Abstract Aiming at the distributed permutation flowshop scheduling problem with variable processing speed，a dual-population algorithm is proposed to optimize the makespan and the total energy consumption of the machine.First，an initialization method that mixes four strategies is used to generate a high-quality initial population.Second，specific evolution methods are designed according to the characteristics of the two populations，and the dynamic guide factor is introduced to adjust the evolution mode of the populations.Meanwhile，an energy-saving strategy for speed regulation is proposed to further optimize energy consumption.Finally，a dynamic population strategy is proposed to balance the resources of the two populations.Simulation results verify the effectiveness of each strategy，and show that the proposed dual population algorithm outperforms current multi-objective evolutionary algorithms.

Key words permutation flowshop;dual-population algorithm;distributed;variable speed shop;multi-objective optimization