引自：《生產(chǎn)系統(tǒng)建模與仿真》（作者：朱海平）

?

「?1.?概述?」

在傳統(tǒng)的車間計(jì)劃安排中，計(jì)劃方案的制定一般是由相關(guān)工作人員依靠經(jīng)驗(yàn)進(jìn)行安排，缺乏對(duì)整體計(jì)劃安排的考慮和科學(xué)的定量分析。隨著計(jì)算和運(yùn)籌學(xué)的發(fā)展，出現(xiàn)了對(duì)各種類型的車間引入數(shù)學(xué)模型通過(guò)智能優(yōu)化方法進(jìn)行求解的方法。而簡(jiǎn)單抽象和忽略細(xì)節(jié)因素的數(shù)學(xué)模型往往不能對(duì)復(fù)雜車間進(jìn)行準(zhǔn)確的描述，對(duì)復(fù)雜車間投產(chǎn)計(jì)劃優(yōu)化效果甚微。結(jié)合生產(chǎn)系統(tǒng)仿真的優(yōu)化技術(shù)與傳統(tǒng)優(yōu)化技術(shù)相比，其最大的優(yōu)點(diǎn)是能夠?qū)Υ嬖谖锪?、人力資源調(diào)度和隨機(jī)因素的復(fù)雜車間進(jìn)行準(zhǔn)確描述，對(duì)各種生產(chǎn)排程方案進(jìn)行準(zhǔn)確且更貼近現(xiàn)實(shí)的比較、評(píng)價(jià)。生產(chǎn)系統(tǒng)仿真軟件中，與算法相結(jié)合的生產(chǎn)計(jì)劃仿真優(yōu)化一般流程如下：

（1）創(chuàng)建仿真模型。

（2）定義優(yōu)化目標(biāo)

：生產(chǎn)系統(tǒng)仿真優(yōu)化目標(biāo)可以涉及車間各個(gè)方面，如計(jì)劃調(diào)度、物流效率優(yōu)化、設(shè)施布局優(yōu)化、資源調(diào)度優(yōu)化等。以生產(chǎn)計(jì)劃的優(yōu)化為例，生產(chǎn)計(jì)劃的性能指標(biāo)可以分為最大能力指標(biāo)、成本指標(biāo)、客戶滿意度指標(biāo)三類。涉及到生產(chǎn)效率與周期的指標(biāo)一般可歸為最大能力指標(biāo)，涉及庫(kù)存、利潤(rùn)、費(fèi)用等內(nèi)容的指標(biāo)一般可歸為成本指標(biāo)，涉及到生產(chǎn)延遲、交貨期等內(nèi)容的指標(biāo)一般可歸為客戶滿意度指標(biāo)。常用的指標(biāo)包括最大完工時(shí)間、交貨期滿意度等。

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

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

（4）定義輸入?yún)?shù)以及編碼形式

：基于所采用的智能優(yōu)化算法，將生產(chǎn)系統(tǒng)仿真模型中的參數(shù)，轉(zhuǎn)化為智能優(yōu)化方法的編碼形式，編碼形式包含了對(duì)所優(yōu)化問(wèn)題約束的體現(xiàn)，需要結(jié)合具體問(wèn)題考慮采用不同編碼方式。例如，對(duì)于流水車間調(diào)度問(wèn)題一般采用正整數(shù)編碼，對(duì)于柔性作業(yè)車間調(diào)度問(wèn)題，一般采用MSOS兩段式整數(shù)編碼的方式。

（5）定義仿真試驗(yàn)初始化方法

：該方法在每次試驗(yàn)的每次觀察仿真前自動(dòng)執(zhí)行，主要是對(duì)優(yōu)化方法輸出編碼的解碼過(guò)程。例如，對(duì)于流水車間調(diào)度問(wèn)題，將正整數(shù)編碼解碼為投產(chǎn)的順序，作為仿真模型的輸入?yún)?shù)。

（6）定義算法的參數(shù)

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

（7）定義仿真結(jié)束前方法

：該方法在每次試驗(yàn)的每次觀察仿真結(jié)束前自動(dòng)執(zhí)行，主要作用是根據(jù)仿真結(jié)果來(lái)計(jì)算算法的優(yōu)化評(píng)價(jià)結(jié)果，例如計(jì)算遺傳算法中適應(yīng)度函數(shù)值。

（8）仿真優(yōu)化的自動(dòng)運(yùn)行。

（9）優(yōu)化結(jié)果保存、輸出與分析。

「 2.?生產(chǎn)計(jì)劃單目標(biāo)仿真優(yōu)化?」

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

（1）A、B、C、D、E各投入5個(gè)，共25個(gè)，在0時(shí)刻同時(shí)投產(chǎn)；

（2）5類工件在每臺(tái)設(shè)備上加工的時(shí)間均不相同，加工時(shí)間如表1所示。

?

?

圖1?生產(chǎn)計(jì)劃單目標(biāo)優(yōu)化模型示例

表1 產(chǎn)品加工時(shí)間表

?

不同的產(chǎn)品投產(chǎn)順序，產(chǎn)品總完工時(shí)間不同，25個(gè)產(chǎn)品投產(chǎn)順序的組合數(shù)為25!個(gè)，無(wú)法通過(guò)仿真試驗(yàn)設(shè)計(jì)得到最佳的批次投產(chǎn)順序，下面通過(guò)智能優(yōu)化算法結(jié)合仿真進(jìn)行優(yōu)化。

?

（1）創(chuàng)建仿真優(yōu)化對(duì)象的仿真模型。

?

（2）優(yōu)化目標(biāo)：最小化最大完工時(shí)間。

?

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

?

?

圖2?基于遺傳算法的仿真優(yōu)化流程圖

?

（4）定義輸入?yún)?shù)以及編碼形式：輸入?yún)?shù)為25個(gè)產(chǎn)品的投產(chǎn)順序，采用正整數(shù)編碼的方式對(duì)染色體進(jìn)行編碼。

?

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

?

（6）定義算法的參數(shù)

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

?

圖3?PMX交叉算子

（7）定義適應(yīng)度計(jì)算方法：通過(guò)仿真模型運(yùn)行結(jié)果，獲取仿真完工時(shí)間，作為遺傳算法的適應(yīng)度值。

（8）仿真優(yōu)化自動(dòng)運(yùn)行。

（9）優(yōu)化結(jié)果

：最優(yōu)生產(chǎn)順序?yàn)锳ECDCAAEBDBDECCEDCBEABABD。仿真初始結(jié)果為14天22時(shí)，優(yōu)化后結(jié)果為12時(shí)7分，適應(yīng)度收斂曲線如圖4所示。?

?

圖4 適應(yīng)度收斂曲線

「?3.?生產(chǎn)計(jì)劃多目標(biāo)仿真優(yōu)化?」

下面通過(guò)一個(gè)復(fù)雜車間生產(chǎn)計(jì)劃優(yōu)化實(shí)例來(lái)介紹多目標(biāo)仿真優(yōu)化方法。圖5所示為某焊接車間仿真模型。

?

圖5?焊接車間仿真優(yōu)化模型實(shí)例

（1）車間布局如圖5所示，面積約1.6萬(wàn)m2，生產(chǎn)運(yùn)載火箭貯箱等大型復(fù)雜結(jié)構(gòu)零件，車間在使用的設(shè)備或區(qū)域共12個(gè)，包括無(wú)損檢測(cè)設(shè)備2臺(tái)、XX-4/5/6總對(duì)接設(shè)備各1臺(tái)、緩沖區(qū)和工裝停放區(qū)域、數(shù)控懸臂式攪拌摩擦焊設(shè)備1臺(tái)、立式縱縫攪拌摩擦焊設(shè)備1臺(tái)、銑邊機(jī)1臺(tái)、數(shù)控立車1臺(tái)、試驗(yàn)區(qū)包含試驗(yàn)設(shè)備1臺(tái)、箱底空間曲線攪拌摩擦焊設(shè)備1臺(tái)。?

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

?

圖6?產(chǎn)品BOM

?

?

圖7?工藝路線圖

?

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

?

表2?產(chǎn)品訂單表

?

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

?

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

?

（6）該車間設(shè)備加工時(shí)間存在一定隨機(jī)性，在仿真模型中設(shè)定加工時(shí)間服從截尾正態(tài)分布。

?

（7）單底零件經(jīng)過(guò)無(wú)損檢測(cè)工序時(shí)，存在一定的返工幾率，不合格的單底返回立車工序重新加工。

?

通過(guò)多目標(biāo)智能優(yōu)化算法結(jié)合仿真進(jìn)行優(yōu)化，同時(shí)考慮多個(gè)優(yōu)化目標(biāo)，更符合實(shí)際生產(chǎn)過(guò)程中的需求，優(yōu)化過(guò)程如下：

?

（1）創(chuàng)建仿真優(yōu)化對(duì)象的仿真模型。

?

（2）優(yōu)化目標(biāo)：最小化最大完工時(shí)間、最小化設(shè)備等待時(shí)間。

?

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

?

圖8?NSGA-Ⅱ算法流程圖

（4）定義輸入?yún)?shù)以及編碼形式：輸入?yún)?shù)為26套產(chǎn)品的投產(chǎn)順序，采用正整數(shù)編碼的方式對(duì)染色體進(jìn)行編碼。

（5）定義仿真模型運(yùn)行初始化方法（每次試驗(yàn)的每次觀察仿真前自動(dòng)執(zhí)行并初始化）：對(duì)染色體進(jìn)行解碼，編碼1~13代表XX-4，編碼14~21代表XX-5，編碼22~26代表XX-6，染色體長(zhǎng)度為26。解碼后獲得新的投產(chǎn)順序，按投產(chǎn)順序?qū)a(chǎn)品按照BOM分解為相應(yīng)的零件，最后輸入仿真模型。

?

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

?

（7）定義適應(yīng)度計(jì)算方法：通過(guò)仿真模型運(yùn)行結(jié)果，獲取仿真完工時(shí)間，并統(tǒng)計(jì)每臺(tái)設(shè)備的等待時(shí)間，將兩個(gè)時(shí)間值作為適應(yīng)度返回給算法。

?

（8）仿真優(yōu)化自動(dòng)運(yùn)行。

?

（9）優(yōu)化結(jié)果如表3所示，列出了3個(gè)非支配解（即Pareto解），可以看出，和優(yōu)化前結(jié)果相比，兩個(gè)目標(biāo)值都有大幅降低。

?

表3?多目標(biāo)優(yōu)化非支配解集