楊岱浩　王波

摘要：針對Job shop型生產調度問題，構建一個小型智能加工中心，采用Extendsim軟件建立仿真模型，并多次運用遺傳算法實現(xiàn)優(yōu)化設計，得到符合條件的滿意解。提出可以將Job shop型生產調度問題轉化為前期優(yōu)化設計問題，通過工藝改善，將大型Job shop型生產調度車間轉化為許多類似于所構建的小型智能加工中心，使其具有Flow shop型生產加工的特點，從而提高生產率，快速滿足市場需求。

關鍵詞：仿真建模；Extendsim；優(yōu)化設計；遺傳算法；車間調度

DOIDOI：10.11907/rjdk.151475

中圖分類號：TP319

文獻標識碼：A 文章編號文章編號：16727800（2015）008013203

0 引言

由于市場需求的多樣化，企業(yè)在生產制造時通常面臨高度的任務多樣性和混雜的流程流向等復雜的加工調度問題。為了解決此類難題，企業(yè)通常需要改善加工流程，改進現(xiàn)有設備。為了降低設計成本，規(guī)避設計風險，在最短時間內以較優(yōu)的方案投產或改建一個制造系統(tǒng)，面向制造過程的虛擬仿真技術得以普遍應用[12]。

Extendsim是Extend 的升級版，是唯一采用物件流和信息流可以同時在模塊圖標上動態(tài)表達的仿真軟件，具有較高的靈活性和可擴展性。作為通用仿真軟件，Extendsim可用于離散事件系統(tǒng)和連續(xù)系統(tǒng)的仿真，提供多種復雜數(shù)據(jù)傳遞方式[35]，適合大型復雜系統(tǒng)的建模與仿真。

Job shop是加工多品種小批量產品時采用的一種生產調度方式，目前大多數(shù)文獻中都是采用啟發(fā)式算法解決問題[69]。本文以一個小型智能加工中心的仿真優(yōu)化設計[1011]為例，提出將車間生產調度問題轉化為前期優(yōu)化設計問題，從而降低問題的復雜性。由于3個加工站的車間調度問題即為NP難題，因而本文考慮的加工中心僅有3個加工站。

1 加工中心構建

一個小型的智能制造中心由一個庫存區(qū)和3個加工站組成，如圖1所示。同一加工站中所有機器均相同，不同加工站的機器不同，各加工站及庫存區(qū)之間通過一個agv小車聯(lián)系起來。工件到達庫存區(qū)的時間間隔為服從均值為5min的指數(shù)分布，每次到達一個。制造中心共有3種作業(yè)類型，序號分別為1、2、3。3種類型按照經驗分布出現(xiàn)，概率依次為0.3、0.5、0.2。每項作業(yè)從庫存原料區(qū)開始，經過一定的路徑加工完成后，回到庫存成品區(qū)。不同作業(yè)類型的加工路徑如表1所示。

圖1 制造中心組成

agv小車在不同站點之間以5ft/s勻速運送工件，每次一個，運送到達某站點時，小車與工件分離。此時如果3個工作站和庫存區(qū)都沒有工件請求運輸，小車將停留在原地；如果有多個不同站點的工件等待運輸，小車將根據(jù)最小距離優(yōu)先原則處理申請。各工作站之間的距離如表2所示。

當工件到達工作站等待加工或者同一個工作站的工件加工完成后等待小車運輸時，都按照先到先服務的原則排隊。在某臺機器上加工工件的時間服從形狀參數(shù)為2的伽瑪分布，均值依賴于作業(yè)類型和該機器所在的工作站。各作業(yè)類型和每步操作平均加工時間的關系如表3所示。

假定庫存空間充足，設備不出現(xiàn)故障，每天工作8h，合理安排各工作站設備的數(shù)量，可使每天的產出最大。

2 基于Extendsim的仿真建模與分析

2.1 Extendsim建模原理

Extendsim采用交互式建模方式，提供多種復雜數(shù)據(jù)傳遞方式，支持分層結構和命名連接，模塊之間采用基于消息的傳遞機制。Extendsim仿真離散系統(tǒng)采取最短時間的事件步長法[1213]，即仿真在執(zhí)行過程中，必須跟蹤未來仿真時間假定發(fā)生的各種事件，離初始時點最近的對應事件就是下一個要發(fā)生的事件。某些情況下，有些事件同時發(fā)生，但仿真軟件仍然要為它們的執(zhí)行安排一個先后順序[3]，這種順序往往對結果產生不同的影響。

2.2 仿真模型建立

模型建立之前，根據(jù)問題需要先建立3個全局數(shù)組：加工路徑、不同工作站之間的距離、平均加工時間。為了便于研究，將模型分為四大部分：工件到達、小車調度、工件與小車結合及路徑選擇、工件運輸及加工。

2.2.1 工件到達仿真

仿真開始時，如圖2所示，模塊1按照設定的指數(shù)分布產生工件；模塊2為工件設置屬性：type—作業(yè)類型，step—加工步驟，processtime—加工時間；模塊3依照設定的經驗分布產生不同的作業(yè)類型；模塊4根據(jù)到達工件的“type”屬性，從全局數(shù)組中讀取相應的平均加工時間，通過randomcalculate 函數(shù)將其轉化為工件的實際加工時間，并賦予到工件“processtime”屬性中；工件在模塊5等待小車運輸。

2.2.2 小車調度仿真

如圖3所示，小車最初由模塊2產生，具有位置屬性為truck_location。當有工件等待運輸時，模塊3輸出“1”，觸發(fā)模塊4打開“門”。模塊5用于比較小車與等待工件之間的距離，根據(jù)距離最小優(yōu)先原則選擇路徑，計算出運輸時間。小車通過模塊6的時間延遲后，由模塊7到達與工件的結合處。模塊1實現(xiàn)小車返回時路徑的合流。

2.2.3 工件與小車結合及路徑選擇仿真

如圖4所示，工件和小車通過模塊1的結合后，由模塊3通過gagetreal函數(shù)，根據(jù)工件的類型和加工步驟，從全局數(shù)組中讀取相應的加工路徑，經過模塊4通向目標加工站。模塊2實現(xiàn)路徑的合流。

圖4 工件與小車結合及路徑選擇仿真模型

2.2.4 運輸及加工工件仿真

以工作站1為例，闡述工件的運輸和加工過程。如圖5所示，工件和小車結合之后，由模塊1計算出運輸時間，通過模塊2的時間延遲后，到達目標工作站，經過模塊3實現(xiàn)小車與工件分離。小車經過模塊9更新位置屬性—truck_location，回到圖3的模塊2中，此過程不消耗時間。工件進入模塊4等待加工（如果工件此時處于成品庫存區(qū)，則直接離開系統(tǒng)），模塊5為加工模塊。工件經加工之后，通過模塊6更新屬性“step”和“processtime”，進入模塊7等待小車運輸。工件和小車經過模塊8的結合之后回到圖4中模塊2的路徑合流處。模塊10計算出工作站的庫存數(shù)量。

3 仿真結果與分析

通過仿真穩(wěn)定狀態(tài)分析后，預熱期設為20天，運行時長60天。Extendsim仿真軟件的優(yōu)化模塊內置遺傳算法，將多次運行結果的平均值作為種群的適應度函數(shù)值，通過交叉、變異的方式改變參數(shù)，不斷對適應度函數(shù)值進行比較，最終得到優(yōu)化解[1415]。由于隨機因素和算法本身的缺陷，本文通過多次使用遺傳算法，并結合實際運行后的結果，最終得出工作站1、2、3的設備數(shù)目分別為7、2、8。仿真運行100次后得到的結果如表4所示。

由于每種作業(yè)都要經過工作站1，因而工作站1中加工隊長的變化，可以反映出加工過程相關情況。加工隊長有時不斷增加，但很快都開始減少，說明設備的加工能力可行。小車的利用率為0.72，證明一個小車是合適的。工作站的利用率都為0.85以下，可以應對一些偶然發(fā)生的故障。

本文討論的優(yōu)化問題中，工件到達的時間間隔是服從均值為5min的指數(shù)分布，具有一定的隨機性。當實際中對投入物料的時間間隔經過統(tǒng)計檢驗后可以近似為某種概率分布時，本文構建的小型智能加工中心就可以擴充為一個小型的企業(yè)生產車間，或作為車間生產的一部分，也可以作為一條生產流水線的一部分，將生產加工工藝中不能流程化的部分融入到流水作業(yè)中。

4 結語

本文采用Extendsim仿真軟件對一個小型的智能加工中心進行優(yōu)化設計，仿真思路清晰，方法簡單，對于解決一些復雜的生產調度問題，具有一定的參考價值。Job shop 型生產調度問題來源于實際生產，往往是NP完全問題，具有相當?shù)膹碗s性。如果可以將此問題轉變?yōu)樽畛醯能囬g設計問題，問題將會變得簡單。

參考文獻：

[1] 肖杰華，陳立平，郭宇，等.面向生產制造過程的虛擬仿真系統(tǒng)建模研究[J].計算機工程，2002，28（6）：4446.

[2] 王國新，寧汝新，王愛，等.仿真優(yōu)化在制造系統(tǒng)中的應用現(xiàn)狀及發(fā)展趨勢[J].系統(tǒng)仿真學報，2008，20（1）：16.

[3] 秦天保，王巖峰.面向應用的仿真建模與分析：使用ExtendSim [M].北京：清華大學出版社，2011.

[4] DAVID KRAHL.The extend simulation environment[C].The 2000 Winter Simulation Conference，2000：280289.

[5] E KOPYTOV，L GREENGLAZ，A MURAVYOV.Modelling of the multiproduct inventory problem[J].Analytical Management，2008，12（3）：4754.

[6] 熊銳，吳澄.車間生產調度問題的技術現(xiàn)狀與發(fā)展趨勢[J].清華大學學報：自然科學版，1998，38（10）：5560.

[7] LIJI SHEN，UDO BUSCHER.Solving the serial batching problem in job shop manufacturing systems[J].European Journal of Operational Research，2012，221（6）：1426.

[8] 王鳳，林杰.設備組合加工的生產調度問題研究[J].計算機工程與應用，2009，45（11）：2629.

[9] LARS MONCH，RENE SCHABACKER，DETLEF PABST，et al.Genetic algorithmbased subproblem solution procedures for a modi？ed shifting bottleneck heuristic for complex job shops[J].European Journal of Operational Research，2007，177（5）：21002118.

[10] CHRISTOS KOULAMAS，GEORGE J KYPARISIS.The threemachine proportionate open shop and mixed shop minimum makespan problems[J].European Journal of Operational Research，2014（4）：15.

[11] AVERILL M.LAW.仿真建模與分析[M].肖田元，范文慧，譯.北京：清華大學出版社，2012.

[12] EUGENE KOPYTOV，AIVARS MURAVJOVS.Simulation of inventory control system for supply chain“producer-wholesalerclient” in extendsim environment [C].25th European Conference on Modelling and Simulation，2011.

[13] 陳沖，張瑩.基于EXTEND的大型露天礦卡車調度系統(tǒng)仿真[J].系統(tǒng)仿真學報，2007，19（4）：914917.

[14] H ALLAOUI，A ARTIBA.Integrating simulation and optimization to schedule a hybrid flow shop with maintenance constraints[J].Computers & Industrial Engineering，2004，47（3）：431450.

[15] M MARSEGUERRA，E ZIO.Optimizing maintenance and repair policies via a combination of genetic algorithms and Monte Carlo simulation[J].Reliability Engineering and System Safety，2000，68（3）：6983.

（責任編輯：孫 娟）