楊岱浩　王波

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

關(guān)鍵詞：仿真建模；Extendsim；優(yōu)化設(shè)計(jì)；遺傳算法；車間調(diào)度

DOIDOI：10.11907/rjdk.151475

中圖分類號(hào)：TP319

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)文章編號(hào)：16727800（2015）008013203

0 引言

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

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

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

1 加工中心構(gòu)建

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

圖1 制造中心組成

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

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

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

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

2.1 Extendsim建模原理

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

2.2 仿真模型建立

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

2.2.1 工件到達(dá)仿真

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

2.2.2 小車調(diào)度仿真

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

2.2.3 工件與小車結(jié)合及路徑選擇仿真

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

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

2.2.4 運(yùn)輸及加工工件仿真

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

3 仿真結(jié)果與分析

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

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

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

[3] 秦天保，王巖峰.面向應(yīng)用的仿真建模與分析：使用ExtendSim [M].北京：清華大學(xué)出版社，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] 熊銳，吳澄.車間生產(chǎn)調(diào)度問題的技術(shù)現(xiàn)狀與發(fā)展趨勢(shì)[J].清華大學(xué)學(xué)報(bào)：自然科學(xué)版，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] 王鳳，林杰.設(shè)備組合加工的生產(chǎn)調(diào)度問題研究[J].計(jì)算機(jī)工程與應(yīng)用，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].肖田元，范文慧，譯.北京：清華大學(xué)出版社，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的大型露天礦卡車調(diào)度系統(tǒng)仿真[J].系統(tǒng)仿真學(xué)報(bào)，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.

（責(zé)任編輯：孫 娟）