基于Plant Simulation 的混合流水線車間調度仿真

高珂婷

（天津工業大學計算機科學與技術學院，天津 300380）

0 引言

混合流水線車間調度問題（Hybrid Flow shop Schedul?ing Problem，HFSP）是一個典型的NP-hard 難題，其結合了傳統的Flow shop 調度問題和多機并行分配問題，故其解決方案更加復雜。

遺傳算法（Genetic Algorithm，GA）作為一種自組織、自適應、自學習的全局搜索算法［1］，具有很強的魯棒性和并行搜索能力，可以防止陷入局部最優。利用仿真軟件通過構建仿真模型計算調度問題的目標函數值可以免去構建復雜的數學模型，直觀地觀察到車間流水線最優的調度路線，實現最小化最大完工時間與總生產成本等目標。

近年來，學者們對混線排序問題的研究不斷深入。一部分文獻利用仿真軟件對該問題進行優化，如文獻［2］利用仿真軟件建立混流裝配線的物料配送系統仿真模型，對物料系統進行優化；文獻［3］針對某軍工車間的生產任務進行排產仿真，得到合理的作業規劃；文獻［4］參考企業提供的實際參數及條件，在不同優化目標下利用仿真軟件進行對比分析，提出最佳措施；文獻［5］針對供應鏈庫存管理提出一種仿真優化方法作為過程控制策略。還有一部分文獻結合相關算法對該問題進行優化，如文獻［6］提出最優家族遺傳算法解決了超大規模車間調度效率低的問題；文獻［7］針對實時生產系統提出一種調度算法和啟發式方法，使生產線上的零件使用率保持恒定；文獻［8］用GA 求解混流裝配線排序問題，在求解速度方面表現良好；文獻［9］將GA 與局部優化程序相結合，用于生成針對流水線平衡問題的多種解決方案，提高了執行速度；文獻［10］采用改進粒子群優化生成系統中的管理參數，并借助仿真軟件很好地解決了裝配線平衡問題。

綜上所述，對于車間調度問題的求解可以結合仿真方法和遺傳算法，該方法具有很好的通用性［11］。針對HFSP這一復雜問題，本文以Plant Simulation 作為仿真建模工具，建立實例中的車間流水線調度模型，再用遺傳算法（GA）結合SPT 規則進行仿真優化，調度目標是最小化Makespan（最大加工完成時間），最后通過Plant Simulation仿真平臺上的優化結果驗證其有效性［12］。

1 問題描述

混合流水線車間調度問題可描述為：n 個工件在一臺或多臺機床上通過m 道工序完成加工，各道工序的加工時間已知［13］，如圖1 所示。

Fig.1 HFSP scheduling problem圖1 HFSP 調度問題

一般混合流水線車間調度問題有如下假設：①在加工過程中，所有工件只能在一臺機器上加工；②下一道工序必須在上一道工序結束后才能開始進行；③各工序的加工設備可獨立完成全部工件的加工；④每個工件必須完成該工序的操作后才能開始下一道工序；⑤工件位置按一定優先級排列，位置越靠前越早開始加工；⑥若遇到工件的同一道工序恰好需要在同一臺機器上完成，則后一個工件必須等前一個工件加工完成后再進行加工［14］。

2 遺傳算法

2.1 染色體編碼

通常古典生產車間調度問題共有8 種染色體編碼方式，本文采用基于矩陣的實數編碼方式作為染色體編碼方式。對于n 個工件、m 臺機器的問題，可構造M×N 矩陣［15］：

其中j=1，2，…，m，i=1，2，…，n，aji表示第i個工件的第j道工序，該實數取值區間為［1，M(j)+1］［16］，M(j) 為第j道工序包含的機器數，整數部分表示所在工序的機器號，小數部分表示加工優先級。如a21=3.1，a22=3.8，a24=3.4，表示工件1、2、4 的M2工序均使用編號為3 的機器，而由于3.1＜3.4＜3.8，故加工次序為工件1/工件4/工件2。除第一道工序按上述編碼規則對工件進行排序外，后面的工序應加入一定的優先規則，本文采取最短作業時間（Shortest Process?ing Time，SPT）規則。

2.2 適應度函數

遺傳算法基因被選擇遺傳的機會取決于所組成的染色體適應度大?。?7］，如何使適應度函數與求解對象有效匹配是檢驗遺傳算法有效性的關鍵。對于HFSP 問題，求解目標為Makespan 的最小值，所以采用Cmax的倒數作為適應度函數。n 個工件經過m 道工序，其中染色體pop｛i｝在每道工序上花費的時間為Cmax=max1≤i≤n{ }Ci，則適應度函數表示為：

2.3 選擇算子

采用遺傳算法將適應度值高的個體遺傳到下一代，即對種群進行優勝劣汰。本文選擇輪盤賭，其基本思想是：每個個體被選中的概率與其適應度值成正比，即值越大，被選擇的概率越高，反之亦然。染色體i被選中遺傳到下一代的概率為：

其中，i=（1，2，…，n），n為種群大小，Fi為染色體i的適應度值。

2.4 交叉算子

對于HFSP 問題，由于排序在編碼中的唯一性，如果采用簡單交叉方法，會出現非法解，故這里使用部分映射交叉法（Partially Mapping Crossover，PMX）以避免該問題的產生，從而使解更有效。具體步驟描述為：①隨機產生兩個交叉點，在兩個染色體中的兩點之間交換基因；②若交換后的片段與交叉點外的基因不沖突，保留；③若存在沖突，則在交換基因集合中利用部分映射尋找替換基因，產生新個體。

PMX 具體過程如圖2 所示。

Fig.2 PMX specific process圖2 PMX 具體過程

2.5 變異算子

在序號編碼方式下，基因有兩種突變方式：一種是互聯變異，即在序列中隨機選擇兩個基因，交換其在染色體上的位置后形成新的后代個體，如個體［1，2，3，4，5，6，7，8，9］，隨機選擇2、8，交換后的個體為［1，8，3，4，5，6，7，2，9］。另一種是逆轉變異，即將在染色體中隨機選擇的兩點間基因段進行逆轉，如個體［1，2，3，4，5，6，7，8，9］，隨機選擇2、5，逆轉后的個體為［1，2，5，4，3，6，7，8，9］。本文選擇互聯變異方式［18］。

3 案例仿真分析

3.1 Plant Simulation

Plant Simulation 平臺是Siemens 公司研發的一款仿真軟件，可用于優化生產線及生產物流過程。其特點主要體現在面向對象的動態系統建模過程、模塊化和多層次的建模單元、圖形化和對象化的并行仿真環境、多類型接口、多種工具集成等方面［19］。

3.2 仿真模型

在本案例中，整個車間由9 臺設備（M1，M2，…，M9）加工12 個工件（J1，J2，…，J12），所有工件所需加工時間如表1所示［20］。

Table 1 All workpiece processing time表1 所有工件加工時間單位：h

在Plant Simulation 平臺中模擬建立本案例的車間制造模型，如圖3 所示。仿真部分包括區域1、3、4，GA 模塊位于區域2，其中區域1 中的Start 對象自動生成區域4 中的模型，Jobs 對象存放由GA 模塊產生的某個體；區域3 中SUB_FSP 數據子層存放機床M1-M9對各個工件的加工時間，Result_Table 表存放個體仿真結果；區域2 中GAWizard和GASequence 為軟件自帶的遺傳算法優化工具。

在GAWizard 模塊中設置種群規模為20，種群大小為15，在GASequence 模塊中設置交叉概率為0.8，變異概率為0.1。在Start 方法中，全局變量AssignRule 為2，通過GA 運算優化排程，得到優化結果如圖4 所示（彩圖掃OSID 碼可見）。

Fig.3 Workshop manufacturing simulation model圖3 車間制造仿真模型

Fig.4 GA+SPT ranking results圖4 GA+SPT 排優結果

Fig.5 GA+FIFS ranking results圖5 GA+FIFS 排優結果

從圖4（橫坐標代表種群代數，縱坐標代表適應值）可以看出，隨著遺傳代數的增加，運算結果逐漸趨于最優化，紅線代表每次進化過程中種群的最優排程方案，藍線代表最差排程方案，綠線是二者的平均值。采用SPT 調度規則在第12 代種群之后收斂到最佳個體，實現最優的排序方式，工件加工順序為4-11-2-1-7-12-5-9-3-6-10-8，得到最優適應度值25。與圖5 中GA 結合FIFS 規則的結果相比，改進算法可以更快地找到最優方案，再運行MyGantt 方法得到最優排序結果甘特圖，如圖6 所示（彩圖掃描OSID碼可見），得到Makespan=25min，相比文獻［20］的最優結果縮短了4min。

Fig.6 Optimal ranking result Gantt chart圖6 最優排序結果甘特圖

4 結語

本文提出一種改進遺傳算法，結合調度規則，使用Plant Simulation 仿真工具對流水線車間調度問題進行優化仿真，并結合示例說明其可行性，對企業生產可起到一定的指導作用。但由于車間調度的復雜性，要想更接近車間的實際生產情況，還需進一步完善仿真模型，使其可擴展到其它生產調度多目標優化問題上。