基于遺傳算法的混合流水車間調度的研究

摘要為了提高企業生產調度過程中的物料流程混亂、設備負荷不均衡的問題，研究了如何將遺傳算法應用到實際的混合流水調度問題當中。并通過某汽車發動機廠的混合流水調度例子進行了詳細的闡述。

關鍵詞生產調度物料流程遺傳算法混合流水調度

中圖分類號:TH18文獻標識碼:A

1 引言

隨著生產規模逐漸擴大、復雜性越來越高、對資源的需求量急劇上升、市場競爭也越來越激烈，對企業的管理和生產過程的監控都提出了更高的要求。許多企業的機械加工車間在生產調度與管理的手段上，仍停留在人工管理階段，為了保證生產高效穩定運行，以獲得最大的經濟效益，需將遺傳算法這類先進的優化技術引入到生產過程監控當中。

2 混合流水調度

2.1 問題模型

混合流水調度(hybrid flow-shop scheduling problem，HFSP)是傳統流水車間調度(Flow Shop Scheduling Problem，FSP)問題的一種推廣。該問題可描述如下②:n個工件在流水線上進行m個階段的加工，每一階段至少有一臺機器且至少有一個階段存在多臺機器，并且同一階段上各機器的處理性能相同，在每一階段各工件均要完成一道工序，各工件的每道工序可以在相應階段上的任意一臺機器上加工，已知工件各道工序的處理時間，要求確定所有工件的排序以及每一階段上機器的分配情況，使得調度指標最小。

2.2 問題實例

某汽車發動機廠加工車間要加工12個工件，每個工件有車、刨、磨3個工序，現有3個車床(M1、M2、M3完成工序1)，2個刨床(M4、M5完成工序2)，4臺磨床(M6、M7、M8、M9完成工序3)，每臺機床的加工能力不同，具體加工時間如表1所示。

3 遺傳算法的編碼設計

對于HFSP調度問題，每一階段均要解決工件的排序以及并行機的分配。③④本文應用了一種簡單易行的編碼方式，可由m個子排列聯合構成染色體，其中每個子排列為所有工件的一個隨機完全排列，并且由個分隔符“*”將其分成段，每一子段表示該階段上某一臺并行機上的工件加工順序。顯然，多次重復上述染色體生成過程可產生多個不同的調度方案，進而構成遺傳算法的種群。

例如可將汽車發動機廠的HFSP問題可由染色體[ 1 3 7 11* 5 10 9 12* 4 6 2 8** 1 5 7 4 3 10 11 *6 8 2 9 12** 1 5 7 11 * 4 3 *6 12* 8 9 2 10 ]表示，所代表的含義為:機器1依次加工工件1，3，7，11;機器2依次加工工件5，10，9，12;機器3依次加工工件4，6，2，8;機器4依次加工工件1，5，7，4，3，10，11;機器5依次加工工件6，8，2，9，12;機器6依次加工工件1，5，7，11;機器7依次加工工件4，3;機器8依次加工工件6，12;機器9依次加工工件8，9，2，10。

4 實驗結果

實驗主要參數如表2所示，通過該參數對以上舉例的調度進行遺傳算法運算，得到表3所示的實驗結果，該結果為10次運算得到最優解時所用的迭代代數和迭代時間。另外還得到最優染色體[9 10 6 3 * 11 5 1 * 7 2 4 12 8 ** 9 7 5 2 1 6 3 * 11 10 4 12 8 **7 5 10 6 8 * 4 * 9 2 12 * 11 1 3]，根據該染色體得到最優調度時間為29。圖1為汽車發動機廠加工車間調度最優甘特圖。⑤

5 結論

通過某汽車發動機廠的混合流水調度例子，驗證了遺傳算法可以在幾秒時間內得到該問題的最優調度解。因此在企業的實際生產中應用該方法可以大大提高生產調度過程中資源配置和加工時間。