引自:《生產系統(tǒng)建模與仿真》(作者:朱海平)
?
「?1.?概述?」
在傳統(tǒng)的車間計劃安排中,計劃方案的制定一般是由相關工作人員依靠經驗進行安排,缺乏對整體計劃安排的考慮和科學的定量分析。隨著計算和運籌學的發(fā)展,出現(xiàn)了對各種類型的車間引入數(shù)學模型通過智能優(yōu)化方法進行求解的方法。而簡單抽象和忽略細節(jié)因素的數(shù)學模型往往不能對復雜車間進行準確的描述,對復雜車間投產計劃優(yōu)化效果甚微。結合生產系統(tǒng)仿真的優(yōu)化技術與傳統(tǒng)優(yōu)化技術相比,其最大的優(yōu)點是能夠對存在物流、人力資源調度和隨機因素的復雜車間進行準確描述,對各種生產排程方案進行準確且更貼近現(xiàn)實的比較、評價。生產系統(tǒng)仿真軟件中,與算法相結合的生產計劃仿真優(yōu)化一般流程如下:
(1)創(chuàng)建仿真模型。
(2)定義優(yōu)化目標
:生產系統(tǒng)仿真優(yōu)化目標可以涉及車間各個方面,如計劃調度、物流效率優(yōu)化、設施布局優(yōu)化、資源調度優(yōu)化等。以生產計劃的優(yōu)化為例,生產計劃的性能指標可以分為最大能力指標、成本指標、客戶滿意度指標三類。涉及到生產效率與周期的指標一般可歸為最大能力指標,涉及庫存、利潤、費用等內容的指標一般可歸為成本指標,涉及到生產延遲、交貨期等內容的指標一般可歸為客戶滿意度指標。常用的指標包括最大完工時間、交貨期滿意度等。
(3)定義所選用的算法框架
:常用的算法有遺傳算法、粒子群算法、禁忌搜索算法、模擬退火算法等。
(4)定義輸入參數(shù)以及編碼形式
:基于所采用的智能優(yōu)化算法,將生產系統(tǒng)仿真模型中的參數(shù),轉化為智能優(yōu)化方法的編碼形式,編碼形式包含了對所優(yōu)化問題約束的體現(xiàn),需要結合具體問題考慮采用不同編碼方式。例如,對于流水車間調度問題一般采用正整數(shù)編碼,對于柔性作業(yè)車間調度問題,一般采用MSOS兩段式整數(shù)編碼的方式。
(5)定義仿真試驗初始化方法
:該方法在每次試驗的每次觀察仿真前自動執(zhí)行,主要是對優(yōu)化方法輸出編碼的解碼過程。例如,對于流水車間調度問題,將正整數(shù)編碼解碼為投產的順序,作為仿真模型的輸入參數(shù)。
(6)定義算法的參數(shù)
:針對所選擇的優(yōu)化算法,初始化參數(shù),以遺傳算法為例,其參數(shù)包括種群數(shù)、優(yōu)化代數(shù)、交叉算子、變異算子以及交叉變異概率等。
(7)定義仿真結束前方法
:該方法在每次試驗的每次觀察仿真結束前自動執(zhí)行,主要作用是根據仿真結果來計算算法的優(yōu)化評價結果,例如計算遺傳算法中適應度函數(shù)值。
(8)仿真優(yōu)化的自動運行。
(9)優(yōu)化結果保存、輸出與分析。
「 2.?生產計劃單目標仿真優(yōu)化?」
圖1是一個并行流水車間的案例,“入口”處產生5類工件A、B、C、D、E,均需經過3到工序的加工。工序1可以在M001或M002上進行加工,工序2可以在M003或M004上進行加工,工序3可以在M005或M006上進行加工,加工完畢成品進入“出口”。相關基礎數(shù)據如下:
(1)A、B、C、D、E各投入5個,共25個,在0時刻同時投產;
(2)5類工件在每臺設備上加工的時間均不相同,加工時間如表1所示。
?
?

圖1?生產計劃單目標優(yōu)化模型示例
表1 產品加工時間表
產品 |
工序1 |
工序2 |
工序3 |
|||
M001 |
M002 |
M003 |
M004 |
M005 |
M006 |
|
A |
5:0 |
15:0 |
8:0 |
17:0 |
35:0 |
12:0 |
B |
18:0 |
28:0 |
12:0 |
8:0 |
15:0 |
15:0 |
C |
11:0 |
35:0 |
16:0 |
36:0 |
6:0 |
21:0 |
D |
8:0 |
22:0 |
25:0 |
46:0 |
7:0 |
36:0 |
E |
20:0 |
11:0 |
38:0 |
38:0 |
13:0 |
16:0 |
?
不同的產品投產順序,產品總完工時間不同,25個產品投產順序的組合數(shù)為25!個,無法通過仿真試驗設計得到最佳的批次投產順序,下面通過智能優(yōu)化算法結合仿真進行優(yōu)化。
?
(1)創(chuàng)建仿真優(yōu)化對象的仿真模型。
?
(2)優(yōu)化目標:最小化最大完工時間。
?
(3)定義算法框架:選擇遺傳算法框架,其流程如圖2所示。
?
?

圖2?基于遺傳算法的仿真優(yōu)化流程圖
?
(4)定義輸入參數(shù)以及編碼形式:輸入參數(shù)為25個產品的投產順序,采用正整數(shù)編碼的方式對染色體進行編碼。
?
(5)定義解碼方法:對染色體進行解碼,編碼1~5位代表A,編碼6~10位代表B,編碼11~15位代表C,編碼16~20位代表D,編碼21~25位代表E,染色體長度為25。解碼后的順序作為新的投產順序輸入仿真模型。
?
?
(6)定義算法的參數(shù)
:種群大小設置為100,進化代數(shù)設置為100,交叉變異概率分別取0.8和0.1。交叉算子采用部分映射交叉法(Partial Mapped Crossover, PMX)的方式。PMX的例子如圖3所示,首先選取父代基因的起止位置,交換這兩組基因;其次,進行沖突檢測,子代沖突部分,經過映射關系變換為正常的子代染色體。變異算子采用互換變異,即在序列中隨機選擇兩個基因,交換其在染色體上的位置后形成新的后代個體。?
?

圖3?PMX交叉算子
(7)定義適應度計算方法:通過仿真模型運行結果,獲取仿真完工時間,作為遺傳算法的適應度值。
(8)仿真優(yōu)化自動運行。
(9)優(yōu)化結果
:最優(yōu)生產順序為AECDCAAEBDBDECCEDCBEABABD。仿真初始結果為14天22時,優(yōu)化后結果為12時7分,適應度收斂曲線如圖4所示。?
?

圖4 適應度收斂曲線
「?3.?生產計劃多目標仿真優(yōu)化?」
下面通過一個復雜車間生產計劃優(yōu)化實例來介紹多目標仿真優(yōu)化方法。圖5所示為某焊接車間仿真模型。
?

圖5?焊接車間仿真優(yōu)化模型實例
(1)車間布局如圖5所示,面積約1.6萬m2,生產運載火箭貯箱等大型復雜結構零件,車間在使用的設備或區(qū)域共12個,包括無損檢測設備2臺、XX-4/5/6總對接設備各1臺、緩沖區(qū)和工裝停放區(qū)域、數(shù)控懸臂式攪拌摩擦焊設備1臺、立式縱縫攪拌摩擦焊設備1臺、銑邊機1臺、數(shù)控立車1臺、試驗區(qū)包含試驗設備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種產品所需關鍵零件種類及個數(shù)如表2所示。
?
表2?產品訂單表
產品類型 |
年任務量/個 |
關鍵零件(個/貯箱) |
||
單底 |
短殼 |
筒段 |
||
XX-4貯箱 |
13 |
3 |
2 |
1 |
XX-5貯箱 |
8 |
2 |
2 |
5 |
XX-6貯箱 |
5 |
4 |
2 |
3 |
合計 |
26 |
75 |
52 |
68 |
?
(4)該車間采用小車的物流運輸方式,物流路線如圖5中粗線條所示,車間共有2輛物流小車。
?
(5)每道工序都需要多名工人進行操作,工人行走路線和車輛運行路線基本相同。
?
(6)該車間設備加工時間存在一定隨機性,在仿真模型中設定加工時間服從截尾正態(tài)分布。
?
(7)單底零件經過無損檢測工序時,存在一定的返工幾率,不合格的單底返回立車工序重新加工。
?
通過多目標智能優(yōu)化算法結合仿真進行優(yōu)化,同時考慮多個優(yōu)化目標,更符合實際生產過程中的需求,優(yōu)化過程如下:
?
(1)創(chuàng)建仿真優(yōu)化對象的仿真模型。
?
(2)優(yōu)化目標:最小化最大完工時間、最小化設備等待時間。
?
(3)定義算法:NSGA-Ⅱ(帶精英策略的非支配排序的遺傳算法),與仿真結合的流程與GA算法大致相同,但不同點是基于采用擁擠度和擁擠度比較算子、引入精英策略提出快速非支配排序算法。NSGA-Ⅱ算法流程如圖8所示。?
?

圖8?NSGA-Ⅱ算法流程圖
(4)定義輸入參數(shù)以及編碼形式:輸入參數(shù)為26套產品的投產順序,采用正整數(shù)編碼的方式對染色體進行編碼。
(5)定義仿真模型運行初始化方法(每次試驗的每次觀察仿真前自動執(zhí)行并初始化):對染色體進行解碼,編碼1~13代表XX-4,編碼14~21代表XX-5,編碼22~26代表XX-6,染色體長度為26。解碼后獲得新的投產順序,按投產順序將產品按照BOM分解為相應的零件,最后輸入仿真模型。
?
(6)定義算法的參數(shù):種群大小設置為50,進化代數(shù)設置為20,交叉變異概率分別取0.8和0.1。交叉算子采用部分映射交叉法(PMX)的方式,如圖4-10所示,變異算子采用互換變異。
?
(7)定義適應度計算方法:通過仿真模型運行結果,獲取仿真完工時間,并統(tǒng)計每臺設備的等待時間,將兩個時間值作為適應度返回給算法。
?
(8)仿真優(yōu)化自動運行。
?
(9)優(yōu)化結果如表3所示,列出了3個非支配解(即Pareto解),可以看出,和優(yōu)化前結果相比,兩個目標值都有大幅降低。
?
表3?多目標優(yōu)化非支配解集
序號 |
完工時間 |
設備等待時間 |
染色體編碼 |
優(yōu)化前 |
123:5:4:54.865 |
994:22:15:11.517 |
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26] |
優(yōu)化后 |
113:6:0:49.067 |
864:20:33:55.062 |
[21,5,1,20,26,23,19,12,11,22,6,8,3,14,2,7,4,25,16,9,18,17,24, 13,15,10] |
113:1:49:0 |
869:22:19:32.720 |
[26,6,20,8,22,21,1,5,2,19,17,7,15,23,12,4,13,25,18,3,24,11,14,10,9,16] |
|
113:1:6:32.480 |
869:21:30:7.620 |
[14,22,8,2,26,18,5,6,19,13,3,23,4,1,24,9,20,16,25,7,11,15,21,10,12,17] |
評論