王家海，馬云雷，肖睿恒

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

0 引言

隨著科學(xué)技術(shù)的發(fā)展，生產(chǎn)規(guī)模越來越大，復(fù)雜性越來越高，市場競爭越來越激烈，對企業(yè)的管理和生產(chǎn)過程的控制都提出了越來越高的要求。為了獲得最大的經(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è)管理者面臨的大問題。

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

1 問題描述及建模

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

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

1.2 模型的建立

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

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

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

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

表1 工件加工工序

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

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

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

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

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

在四臺機(jī)器上的加工時間(分鐘)：

表2 各工件加工時間

模型如圖5所示。

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

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

圖5 JSP模型

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

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

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

總的加工時間是1:32:55。

2.2 模型的優(yōu)化

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

交叉概率：0.8

變異概率：0.1

代數(shù)：20

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

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

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

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

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

3 結(jié)束語

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

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

[2] Tecnomatix Plant Simulation Help.

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

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