引自：《生產系統建模與仿真》（作者：朱海平）

?

「?1.?概述?」

在傳統的車間計劃安排中，計劃方案的制定一般是由相關工作人員依靠經驗進行安排，缺乏對整體計劃安排的考慮和科學的定量分析。隨著計算和運籌學的發展，出現了對各種類型的車間引入數學模型通過智能優化方法進行求解的方法。而簡單抽象和忽略細節因素的數學模型往往不能對復雜車間進行準確的描述，對復雜車間投產計劃優化效果甚微。結合生產系統仿真的優化技術與傳統優化技術相比，其最大的優點是能夠對存在物流、人力資源調度和隨機因素的復雜車間進行準確描述，對各種生產排程方案進行準確且更貼近現實的比較、評價。生產系統仿真軟件中，與算法相結合的生產計劃仿真優化一般流程如下：

（1）創建仿真模型。

（2）定義優化目標

：生產系統仿真優化目標可以涉及車間各個方面，如計劃調度、物流效率優化、設施布局優化、資源調度優化等。以生產計劃的優化為例，生產計劃的性能指標可以分為最大能力指標、成本指標、客戶滿意度指標三類。涉及到生產效率與周期的指標一般可歸為最大能力指標，涉及庫存、利潤、費用等內容的指標一般可歸為成本指標，涉及到生產延遲、交貨期等內容的指標一般可歸為客戶滿意度指標。常用的指標包括最大完工時間、交貨期滿意度等。

（3）定義所選用的算法框架

：常用的算法有遺傳算法、粒子群算法、禁忌搜索算法、模擬退火算法等。

（4）定義輸入參數以及編碼形式

：基于所采用的智能優化算法，將生產系統仿真模型中的參數，轉化為智能優化方法的編碼形式，編碼形式包含了對所優化問題約束的體現，需要結合具體問題考慮采用不同編碼方式。例如，對于流水車間調度問題一般采用正整數編碼，對于柔性作業車間調度問題，一般采用MSOS兩段式整數編碼的方式。

（5）定義仿真試驗初始化方法

：該方法在每次試驗的每次觀察仿真前自動執行，主要是對優化方法輸出編碼的解碼過程。例如，對于流水車間調度問題，將正整數編碼解碼為投產的順序，作為仿真模型的輸入參數。

（6）定義算法的參數

：針對所選擇的優化算法，初始化參數，以遺傳算法為例，其參數包括種群數、優化代數、交叉算子、變異算子以及交叉變異概率等。

（7）定義仿真結束前方法

：該方法在每次試驗的每次觀察仿真結束前自動執行，主要作用是根據仿真結果來計算算法的優化評價結果，例如計算遺傳算法中適應度函數值。

（8）仿真優化的自動運行。

（9）優化結果保存、輸出與分析。

「 2.?生產計劃單目標仿真優化?」

圖1是一個并行流水車間的案例，“入口”處產生5類工件A、B、C、D、E，均需經過3到工序的加工。工序1可以在M001或M002上進行加工，工序2可以在M003或M004上進行加工，工序3可以在M005或M006上進行加工，加工完畢成品進入“出口”。相關基礎數據如下：

（1）A、B、C、D、E各投入5個，共25個，在0時刻同時投產；

（2）5類工件在每臺設備上加工的時間均不相同，加工時間如表1所示。

?

?

圖1?生產計劃單目標優化模型示例

表1 產品加工時間表

?

不同的產品投產順序，產品總完工時間不同，25個產品投產順序的組合數為25!個，無法通過仿真試驗設計得到最佳的批次投產順序，下面通過智能優化算法結合仿真進行優化。

?

（1）創建仿真優化對象的仿真模型。

?

（2）優化目標：最小化最大完工時間。

?

（3）定義算法框架：選擇遺傳算法框架，其流程如圖2所示。

?

?

圖2?基于遺傳算法的仿真優化流程圖

?

（4）定義輸入參數以及編碼形式：輸入參數為25個產品的投產順序，采用正整數編碼的方式對染色體進行編碼。

?

（5）定義解碼方法：對染色體進行解碼，編碼1~5位代表A，編碼6~10位代表B，編碼11~15位代表C，編碼16~20位代表D，編碼21~25位代表E，染色體長度為25。解碼后的順序作為新的投產順序輸入仿真模型。
?

?

（6）定義算法的參數

：種群大小設置為100，進化代數設置為100，交叉變異概率分別取0.8和0.1。交叉算子采用部分映射交叉法（Partial Mapped Crossover, PMX）的方式。PMX的例子如圖3所示，首先選取父代基因的起止位置，交換這兩組基因；其次，進行沖突檢測，子代沖突部分，經過映射關系變換為正常的子代染色體。變異算子采用互換變異，即在序列中隨機選擇兩個基因，交換其在染色體上的位置后形成新的后代個體。?

?

圖3?PMX交叉算子

（7）定義適應度計算方法：通過仿真模型運行結果，獲取仿真完工時間，作為遺傳算法的適應度值。

（8）仿真優化自動運行。

（9）優化結果

：最優生產順序為AECDCAAEBDBDECCEDCBEABABD。仿真初始結果為14天22時，優化后結果為12時7分，適應度收斂曲線如圖4所示。?

?

圖4 適應度收斂曲線

「?3.?生產計劃多目標仿真優化?」

下面通過一個復雜車間生產計劃優化實例來介紹多目標仿真優化方法。圖5所示為某焊接車間仿真模型。

?

圖5?焊接車間仿真優化模型實例

（1）車間布局如圖5所示，面積約1.6萬m2，生產運載火箭貯箱等大型復雜結構零件，車間在使用的設備或區域共12個，包括無損檢測設備2臺、XX-4/5/6總對接設備各1臺、緩沖區和工裝停放區域、數控懸臂式攪拌摩擦焊設備1臺、立式縱縫攪拌摩擦焊設備1臺、銑邊機1臺、數控立車1臺、試驗區包含試驗設備1臺、箱底空間曲線攪拌摩擦焊設備1臺。?

（2）車間生產XX-4、XX-5和XX-6三類貯箱產品，產品的生產工藝大致相同，若干壁板、瓜瓣、頂蓋和型材框加工成筒段、短殼和單底，再由若干筒段、短殼和單底經過總對接焊接成最后的產品貯箱。產品BOM見圖6，工藝流程見圖7。?

?

圖6?產品BOM

?

?

圖7?工藝路線圖

?

（3）該車間某年XX-4/5/6貯箱的生產量分別為13、8、5個，產品之間的投產間隔為4天，3種產品所需關鍵零件種類及個數如表2所示。

?

表2?產品訂單表

?

（4）該車間采用小車的物流運輸方式，物流路線如圖5中粗線條所示，車間共有2輛物流小車。

?

（5）每道工序都需要多名工人進行操作，工人行走路線和車輛運行路線基本相同。

?

（6）該車間設備加工時間存在一定隨機性，在仿真模型中設定加工時間服從截尾正態分布。

?

（7）單底零件經過無損檢測工序時，存在一定的返工幾率，不合格的單底返回立車工序重新加工。

?

通過多目標智能優化算法結合仿真進行優化，同時考慮多個優化目標，更符合實際生產過程中的需求，優化過程如下：

?

（1）創建仿真優化對象的仿真模型。

?

（2）優化目標：最小化最大完工時間、最小化設備等待時間。

?

（3）定義算法：NSGA-Ⅱ（帶精英策略的非支配排序的遺傳算法），與仿真結合的流程與GA算法大致相同，但不同點是基于采用擁擠度和擁擠度比較算子、引入精英策略提出快速非支配排序算法。NSGA-Ⅱ算法流程如圖8所示。?

?

圖8?NSGA-Ⅱ算法流程圖

（4）定義輸入參數以及編碼形式：輸入參數為26套產品的投產順序，采用正整數編碼的方式對染色體進行編碼。

（5）定義仿真模型運行初始化方法（每次試驗的每次觀察仿真前自動執行并初始化）：對染色體進行解碼，編碼1~13代表XX-4，編碼14~21代表XX-5，編碼22~26代表XX-6，染色體長度為26。解碼后獲得新的投產順序，按投產順序將產品按照BOM分解為相應的零件，最后輸入仿真模型。

?

（6）定義算法的參數：種群大小設置為50，進化代數設置為20，交叉變異概率分別取0.8和0.1。交叉算子采用部分映射交叉法（PMX）的方式，如圖4-10所示，變異算子采用互換變異。

?

（7）定義適應度計算方法：通過仿真模型運行結果，獲取仿真完工時間，并統計每臺設備的等待時間，將兩個時間值作為適應度返回給算法。

?

（8）仿真優化自動運行。

?

（9）優化結果如表3所示，列出了3個非支配解（即Pareto解），可以看出，和優化前結果相比，兩個目標值都有大幅降低。

?

表3?多目標優化非支配解集