在eM-Plant環(huán)境下基于遺傳算法的JSP仿真優(yōu)化

王家海，馬云雷，肖睿恒

（同濟(jì)大學(xué) 機(jī)械工程學(xué)院，上海 201804）

0 引言

隨著科學(xué)技術(shù)的發(fā)展，生產(chǎn)規(guī)模越來(lái)越大，復(fù)雜性越來(lái)越高，市場(chǎng)競(jìng)爭(zhēng)越來(lái)越激烈，對(duì)企業(yè)的管理和生產(chǎn)過(guò)程的控制都提出了越來(lái)越高的要求。為了獲得最大的經(jīng)濟(jì)利益，傳統(tǒng)的，以經(jīng)驗(yàn)為基礎(chǔ)的生產(chǎn)調(diào)度方法已經(jīng)不能滿足現(xiàn)代生產(chǎn)的需求，如何科學(xué)有效的進(jìn)行生產(chǎn)調(diào)度成為企業(yè)管理者面臨的大問(wèn)題。

生產(chǎn)調(diào)度問(wèn)題是非常復(fù)雜的問(wèn)題。通常是多約束、多目標(biāo)、隨機(jī)不確定優(yōu)化問(wèn)題。求解過(guò)程的計(jì)算量隨問(wèn)題的規(guī)模呈指數(shù)增長(zhǎng)，已經(jīng)被證明是NP完全問(wèn)題[1]。其中作業(yè)車間調(diào)度問(wèn)題（jobshop scheduling problem,JSP）問(wèn)題是最困難的組合優(yōu)化問(wèn)題之一。本文正是想通過(guò)運(yùn)用軟件eM-Plant內(nèi)置的GA（遺傳算法）模塊，對(duì)JSP問(wèn)題進(jìn)行初步的仿真和優(yōu)化。

1 問(wèn)題描述及建模

1.1 JSP問(wèn)題數(shù)學(xué)描述[1]

設(shè)生產(chǎn)系統(tǒng)生產(chǎn)n個(gè)產(chǎn)品，表示為集合N={1,2,……,n}，生產(chǎn)系統(tǒng)內(nèi)有m臺(tái)機(jī)器，表示為集合M={1,2,……,m}，每個(gè)工件需要經(jīng)過(guò)若干道工序加工完成，Oikq表示第i個(gè)工件的第k道工序在第q臺(tái)機(jī)器上加工，其開(kāi)始加工的時(shí)間和需要加工的時(shí)間為Sikq和Tikq；工件i的最后一道工序的開(kāi)始加工時(shí)間和需要加工的時(shí)間記為Sieiq和Tieiq，工件i的投料時(shí)間和交貨期是ri和di；Pi是工件的有序工序?qū)Oikp,Oikq]的集合，其中Oikp優(yōu)于Oikq，Rq是使用機(jī)器q的所有工序Oikq的集合。如果目標(biāo)函數(shù)為最小化最大完工時(shí)間，或者是最小完工周期，則JSP問(wèn)題可以描述為：

1.2 模型的建立

在筆者建立的作為演示的模型中，各項(xiàng)具體參數(shù)如下：

十種零件：J1,,J2,J3,J4,J5,J6,J7,J8,J9,J10。

四臺(tái)機(jī)器：M1,M2,M3,M4

各零件的工序如表1所示。

表1 工件加工工序

各機(jī)器在加工各零件的準(zhǔn)備時(shí)間(秒)：

圖1 M1的準(zhǔn)備時(shí)間

圖2 M2的準(zhǔn)備時(shí)間

圖3 M3的準(zhǔn)備時(shí)間

圖4 M4的準(zhǔn)備時(shí)間

在四臺(tái)機(jī)器上的加工時(shí)間(分鐘)：

表2 各工件加工時(shí)間

模型如圖5所示。

其中Delivery表式用來(lái)記錄工件的加工順序，SOP表是用來(lái)記錄各個(gè)工件的工序，ProTime表用來(lái)記錄各個(gè)機(jī)器加工各工件的時(shí)間，setTime表用來(lái)記錄各機(jī)器在切換零件時(shí)的準(zhǔn)備時(shí)間。

2 模型的仿真及優(yōu)化

圖5 JSP模型

2.1 模型的仿真結(jié)果

在模型建立完畢之后，筆者對(duì)此模型進(jìn)行了仿真，工件進(jìn)入系統(tǒng)的順序是J1,J2,J3,J4,J5,J6,J7,J8,J9,10甘特圖如6所示。

圖6 未優(yōu)化時(shí)的甘特圖

總的加工時(shí)間是1:32:55。

2.2 模型的優(yōu)化

eM-Plant為我們提供了GA模塊進(jìn)行對(duì)模型的優(yōu)化，優(yōu)化目標(biāo)是使得仿真時(shí)間最短。JSP優(yōu)化問(wèn)題是典型的順序優(yōu)化問(wèn)題，我們可以選擇系統(tǒng)自帶的GASequence工具和GAWizard結(jié)合來(lái)進(jìn)行優(yōu)化。鑒于系統(tǒng)幫助文檔的參數(shù)值推薦，各參數(shù)設(shè)置如下[2]：

交叉概率：0.8

變異概率：0.1

代數(shù)：20

每代個(gè)體數(shù)量：10

優(yōu)化后，零件進(jìn)入系統(tǒng)的順序是J10,J4,J6,J5,J8,J3,J9,J7,J1,J2，甘特圖如7所示。

由優(yōu)化后的統(tǒng)計(jì)圖能看出，該問(wèn)題由第一代時(shí)，平均的適應(yīng)值為5820左右，經(jīng)過(guò)十三代的遺傳變異，適應(yīng)值逐漸收斂，最后穩(wěn)定在了4600左右，由此可見(jiàn)，該方法確實(shí)能有效的解決此類的問(wèn)題。在優(yōu)化之后，總的加工時(shí)間是1:17:20，比之前提高了15.5分鐘，效率提高16.70%。

圖7 優(yōu)化后的甘特圖

圖8 優(yōu)化結(jié)果

3 結(jié)束語(yǔ)

eM-Plant的GA模塊簡(jiǎn)單易用，能初步的解決JSP問(wèn)題，提高生產(chǎn)效率，但該模塊也有明顯的缺點(diǎn)：作為遺傳編碼的設(shè)計(jì)的重點(diǎn)，遺傳編碼的設(shè)計(jì)，在eM-Plant中是集成在GASequence中的，而eM-Plant中規(guī)定[2]，其編碼序列中中不能出現(xiàn)相同的基因，這就意味著，在處理多零件且每種零件不止一個(gè)的加工時(shí)，需要對(duì)同種零件的不同個(gè)體采用不同的表示方法，這顯然增加了許多不必要的工作量。因此，筆者認(rèn)為，在解決實(shí)際生產(chǎn)問(wèn)題是，用外部代碼進(jìn)行遺傳算法優(yōu)化（比如C或者M(jìn)atlab），只用eM-Plant的強(qiáng)大的仿真功能提供適應(yīng)度函數(shù)的結(jié)果是更好的選擇。

[1] 王萬(wàn)良,吳啟迪.生產(chǎn)調(diào)度智能算法及應(yīng)用[M].科學(xué)出版社,2007.

[2] Tecnomatix Plant Simulation Help.

[3] 刑文訓(xùn),謝金星.現(xiàn)代優(yōu)化計(jì)算方法[M].清華大學(xué)出版社,1999.

[4] 高瑋瑋.基于eM_Plant注塑模具制造過(guò)程的優(yōu)化與仿真.蘇州大學(xué),2007.