優化遺傳算法求解柔性流水車間調度問題

摘要：為提高生產效率和企業競爭力，需制定合理的調度方案以優化資源分配。文章針對柔性流水車間調度問題，提出一種改進的遺傳算法，通過分析柔性流水車間調度問題的特點，對遺傳算法進行改進，主要包括兩個方面：一是采用新的編碼方式，將工序、機器和時間信息融入編碼，提高編碼效率；二是引入自適應交叉和變異操作，加快算法搜索速度，更快找到優解，實驗結果表明，改進后的遺傳算法具有良好的性能。

關鍵詞：柔性流水車間調度問題；遺傳算法；最優化算法；單目標優化

中圖分類號：TP311 文獻標識碼：A

文章編號：1009-3044（2025）02-0015-04 開放科學（資源服務） 標識碼（OSID） ：

0 引言

柔性流水線車間調度問題（Flexible Flow ShopScheduling Problem， 簡稱FFSP） 作為一種經典的組合優化難題[1]，已被確認屬于NP難問題范疇。隨著全球市場競爭的白熱化，制造業企業正承受著減少成本及提升生產效率的雙重壓力[2]。因此，探索高效的調度策略對于促進先進制造技術的發展具有深遠的理論價值與實際意義[3]。盡管FFSP已受到長期研究，但在構建系統的理論框架和方法論方面尚存空白，理論實踐的融合亟待加強。目前，相關研究側重工件調度層面，而資源分配的深入探討略顯不足，兩者的整合研究成為新的趨勢。鑒于車間調度問題固有的復雜性[4]，學者們通常采納啟發式算法、搜索算法等高效策略來應對挑戰。其中，遺傳算法作為一種模擬自然界選擇與進化的計算模型，憑借其并發性、隨機探索及自我適應等特點，在處理復雜度高、非線性問題時展現出獨特優勢[5]，尤其在傳統算法難以突破的領域內效果顯著[6]。有證據表明，在面對作業車間調度難題時，遺傳算法相較于經典啟發式方法展示出更優越的性能與更廣泛的適用性[7]。本研究旨在通過引入遺傳算法來優化流水線車間調度方案，核心目標在于實現總完成時間的最優化。

1 柔性流水車間調度問題

1.1 流水車間調度問題

流水車間通常用于批量生產同種或相似的產品，例如汽車制造、電子產品制造等領域。在流水車間調度問題中，加工系統有一組功能不同的機床，待加工的工件包含多道工序[8]。

流水車間調度問題是一種典型的多機器調度問題。在該問題中，需要對工件進行排序和分配，以最小化完成所有作業所需的總時間[9]。工件需要按照特定的順序流經各個機器進行加工，因此：

1） 每個工件在每臺機器上只能運行一次；2） 一臺機器在同一時刻僅能處理一個工件；3） 每個工件在某一時刻僅能在一臺機器上處理；4） 工件不可被搶占；5） 工件在機器上的處理時間不會隨調度序列改變而改變；6） 機器的使用順序是固定的。

1.3 解決柔性流水車間調度問題的求解方案

常見的啟發式算法包括基于遺傳算法、模擬退火算法、禁忌搜索算法等的進化算法，以及基于鄰域搜索、動態規劃等的局部搜索算法[10]。數學模型通常采用線性規劃、整數規劃、圖論等方法進行建模和求解[11]。解決流水車間調度問題可以提高車間的生產效率，減少生產成本，提高產品的質量和產量[12]。因此，在實際生產中，流水車間調度問題具有重要的應用價值。

2 FFSP 問題數學模型

2.1 問題描述

共有i項工件歷經生產線的T個加工環節進行處理，這些工件按照某種既定序列S1，S2，…，St 反復接受加工操作。每一單項工件i需在特定環節Hi重復加工，累計需經歷Hi×T個工藝步驟方能完成加工流程。在每一個加工環節t，配置有5臺并發設備，工件在抵達環節t時可被靈活指派至該環節內的任一可用設備上，其具體加工時長由負責處理該工件的設備性能決定。工件i依據其釋放時間進入生產體系，而各加工環節之間的轉運時長則依據兩環節之間的物理距離來估算。加工期間，所有設備維持持續運作狀態，且單臺設備每次僅能處理一件工件。調度任務的核心，在于優化每個加工環節內工件至設備的分配策略及同設備上工件的作業排序，旨在實現總體加權完成時間的最小化。

2.2 定義參數和變量

定義參數與變量符號如表1所示。

利用上述符號，將遺傳算法建模如下所示。

目標函數：

1） 計算總時間；2） 總工件數量；3） 在此機器上某個工件加工完成所需要的時間；4） 開工時間和完工時間；5） 機器開工時間的總和，其中包含所有工件；6） 機器的開工時間和完工時間之和；7） 計算工件在運輸過程以及加工過程時間的總和；8） 工件完工時的總時間；9） 判斷某個工件是否在此機器加工過；10） 判斷是否有工件沒有加工。

2.3 算法流程

算法流程如圖1所示。

1）開始：初始化算法。

2）初始化：設置代數GEN=0 。

3）生成初始種群：創建算法的初始種群。

4）檢查停止條件：判斷是否滿足停止條件。

如果滿足，進入步驟9。

如果不滿足，繼續執行。

5）計算適應度：計算種群中每個個體的適應度。

6）初始化計數器：設置計數器i=0。

7） 檢查迭代條件：判斷i是否等于M（最大迭代次數） 。

如果是，增加代數 GEN=GEN+1，然后返回步驟4。

如果不是，繼續執行。

8）選擇操作：根據概率選擇遺傳操作（復制、交叉或變異） 。

復制：選擇一個個體，執行復制，生成新種群。

交叉：選擇兩個個體，執行交叉，生成兩個后代，并將后代插入新種群。

變異：選擇一個個體，執行變異，插入新種群。

9）更新計數器：增加計數器 i=i+1 ，然后返回步驟7。

10）指定結果：當滿足停止條件時，指定最終結果。

11） 結束：算法結束。

2.4 對代碼優化的改進

main 函數：這是主要的函數，用于處理單個實例。首先，設置時間單位為1，并根據給定的實例名稱獲取相應的數據。然后，使用Utils.string2data_jsp_fsp 函數將數據轉換為所需格式。接下來，根據轉換后的數據創建調度問題，并初始化遺傳算法的參數。最后，將遺傳算法和問題設置為調度模板GaTemplate 的參數，以進行求解。

exp 函數：這是用于處理所有實例的函數。它通過將INSTANCE_LIST_FSP 字符串拆分成多個實例名稱，并依次調用main 函數來處理每個實例。

if __name__ == '__main__'：這是 Python 的入口點。在這里，調用 exp 函數開始執行程序。

通過對代碼進行優化，可以使代碼更加規范、易讀和易維護。將不同的功能封裝到函數中，提高了代碼的可重用性。同時，通過合理命名變量和函數，使代碼更加清晰易懂。

2.5 代碼優化解釋

1） 引入模塊時使用了from src import *語句，這種方式不夠明確且容易造成命名沖突。更好的做法是明確導入需要使用的模塊或函數，例如 from src im?port GaFspHfsp， Crossover， Mutation， Selection， Utils，Objective， Fsp， GaTemplate， fsp_benchmark， INSTANCE_LIST_FSP。

2） 將獲取實例數據的代碼行a = fsp_benchmark.instance[instance]修改為更具描述性的變量名in?stance_data = fsp_benchmark.instance[instance]。

3） 將數據轉換的代碼行n， m， p， tech， proc = Utils.string2data_jsp_fsp（a， int， time_unit）修改為使用更具描述性的變量名，并將instance_data作為參數傳遞。

4） 在創建遺傳算法對象GA時，將參數設置移到一個單獨的行，以提高代碼的可讀性。

5） 設置遺傳算法的交叉操作、變異操作和選擇操作時，使用具體的操作類名替代字符串名稱，以提高代碼的可讀性。

6） 將遺傳算法的禁忌參數和卸載參數的設置移到單獨的行，以提高代碼的可讀性。

7） 將主函數的判斷條件修改為if __name__ == '__main__'：，以確保只有在直接運行腳本時才執行實例處理。

8） 添加注釋和解釋來描述代碼的功能和作用。

2.6 代碼優化后結果

1） 刪除了用于初始化填充的重復代碼，并用使用“pop[0]”和“pop”的更有效的方法替換它。

2） 更改方法“decode”以接受先前作為全局變量傳遞的附加參數“mac”“route”和“wok”。這使得代碼更加模塊化，更易于理解。

3） 刪除了不必要的“self.record”變量，并將其替換為“self.record[0]”和“self.Records”，以存儲每一代的初始和最終時間戳。

4） 將方法“do_crossover”更改為使用“pop[0][i]”對象中的“ga_crossover_sequence_termutation”方法，而不是在類中再次實現它。

5） 將方法“do_mutation”更改為使用“pop[0][i]”對象中的“ga_mutation_sequence_termutation”方法，而不是在類中再次實現它。

6） 將方法“do_tabu_search”更改為使用“pop[0][i]”對象中的“ts_sequence_permutation_based”方法，而不是在類中再次實現它。

3 遺傳算法

3.1 遺傳算法基本介紹

遺傳算法作為一種模擬自然界的優化策略，借鑒了自然選擇及遺傳學原理[13]。該算法通常采用二進制字符串來編碼，這些字符串并不代表直接的解決方案。算法初始化階段涉及隨機生成一組染色體構成原始種群，其中染色體的數量定義了種群的規模或大小[14]。接下來，依據預設的適應度函數，評估種群中各個個體的適宜度，此函數體現了個體適應環境的能力，即解的質量高低。隨后，那些展示出較高適應度的個體將得到優選，這一過程映射了自然界中適應性強的生物更易存活繁衍的現象。為了探索種群多樣性和規避局部最優陷阱，實施交叉與變異操作至關重要。這些操作后產生的新一代染色體即為子代。在每一代迭代中，子代將取代父代成為新的種群，此循環往復直至預設終止條件達成，最終甄選出最優染色體作為問題的最優化解。

3.2 遺傳算法的優勢

遺傳算法相比已有算法具有一系列優勢：1） 全局搜索能力更強。2） 并行處理能力較短的時間找到最優解，提高算法效率。3） 遺傳算法的編碼方式和解碼方式相對靈活。4） 魯棒性，有一定的容錯能力。5） 在解決特定類型FFSP 問題上的效果提升、計算效率提升。

3.3 遺傳算法流程

1） 初始化種群：隨機生成一個由多個個體組成的種群，每個個體都代表一個可能的解。

2） 評估適應度：計算每個個體的適應度，適應度越高表示該個體越符合優化問題的要求。

3） 選擇操作：從種群中選擇一些個體，用于繁殖下一代。選擇操作基于適應度，通常選擇適應度較高的個體。

4） 交叉操作：將選擇的個體進行交叉操作，生成新的個體。交叉操作是將兩個個體的某些基因組合在一起，生成新的個體。

5） 變異操作：變異操作是將某個個體的某個基因進行隨機變換，生成新的個體。

6） 生成下一代：將新生成的個體加入種群中，生成下一代種群。

7） 重復執行選擇、交叉、變異操作，直到達到終止條件。

4 實驗結果與分析

數據分析如圖2所示。

工件7在所有運行中都首先完成，這可能表明它在調度中具有優先級或其處理時間較短。

工件5在大多數情況下都是最后完成的，這可能意味著它在調度中被賦予較低的優先級或其處理時間較長。

運行時間：從7 038秒到7 049秒不等，這表明不同工件完成順序對總運行時間有影響，但影響不大，因為時間差異較小。

最優順序：從運行時間來看，第7次運行的順序（7， 4， 2， 10， 6， 8， 3， 1， 0， 5， 9） 具有最短的運行時間7038秒，這可能是最優的調度順序，如表2所示。

5 結論

本文以作業車間生產調度為研究對象，提出一種改進的遺傳算法，并通過實驗驗證了其有效性。

本文的主要貢獻如下，提出一種改進的遺傳算法，設計了相應的遺傳算子、適應度函數和編碼方式.

本文主要研究了最小化總完工時間的車間調度問題，并采用了一種簡單的編碼方式。本文所研究車間調度問題主要針對多種工序可以在多臺不同機床上加工的情況，在以后的研究中，考慮工藝路線可變的情況，此類問題更復雜，但進一步集成了生產計劃與車間調度是一個值得研究的方向。

參考文獻：

[1] 陳世佳.改進Hopfield神經網絡算法求解柔性流水車間有限緩沖區排產問題[D].沈陽：沈陽建筑大學，2017.

[2] 潘帆，鄒澤宇，徐小路.基于雙基因遺傳算法的多工序變速機調度問題研究[J].現代商貿工業，2011，23（20）：261-263.

[3] 那光宇.車輛生產管理系統的設計與實現[D].長春：長春工業大學，2018.

[4] 張慧賢.帶惡化工件的車間調度模型及優化研究[D].鄭州：鄭州大學，2020.

[5] 佟昕，李大鵬，李寧.遺傳算法參數對估算低能耗建筑能量消耗的影響[J].建筑節能，2018，46（1）：108-111.

[6] 王科雷，周洲，許曉平，等.超臨界翼型低雷諾數流動分析及優化設計[J].航空學報，2015，36（10）：3275-3283.

[7] 王民生.禁忌搜索算法及其混合策略的應用研究[D].大連：大連交通大學，2005.

[8] 馬欣，朱雙東，楊斐.旅行商問題（TSP）的一種改進遺傳算法[J].計算機仿真，2003，20（4）：36-37.

[9] 軒華，李冰，羅書敏，等.基于總加權完成時間的可重入混合流水車間調度問題[J].控制與決策，2018，33（12）：2218-2226.

[10] 姚遠遠，葉春明，楊楓.雙目標可重入混合流水車間調度問題的離散灰狼優化算法[J]. 運籌與管理，2019，28（8）：190-199.

[11] 李俊青，潘全科，王法濤.求解混合流水線調度問題的離散人工蜂群算法[J].運籌與管理，2015，24（1）：157-163.

[12] 張維存，左天帥，張博涵.考慮有限緩存區的Job Shop加工與搬運集成調度[J].運籌與管理，2020，29（11）：213-222.

[13] 張維存，鄭丕諤，吳曉丹.蟻群遺傳算法求解能力約束的柔性作業車間調度問題[J].計算機集成制造系統，2007，13（2）：333-337，362.

[14] 曲媛，劉慶閣，唐曉彬，等. 基于改進遺傳算法對車間調度問題的研究[J].計算機與數字工程，2020，48（2）：350-355.

【通聯編輯：光文玲】

基金項目：甘肅省大學生創新創業訓練項目（S202310733046）；甘肅農業大學大學生創新創業訓練計劃項目（202316015）