在eM-Plant環境下基于遺傳算法的JSP仿真優化

王家海，馬云雷，肖睿恒

（同濟大學 機械工程學院，上海 201804）

0 引言

隨著科學技術的發展，生產規模越來越大，復雜性越來越高，市場競爭越來越激烈，對企業的管理和生產過程的控制都提出了越來越高的要求。為了獲得最大的經濟利益，傳統的，以經驗為基礎的生產調度方法已經不能滿足現代生產的需求，如何科學有效的進行生產調度成為企業管理者面臨的大問題。

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

1 問題描述及建模

1.1 JSP問題數學描述[1]

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

1.2 模型的建立

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

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

四臺機器：M1,M2,M3,M4

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

表1 工件加工工序

各機器在加工各零件的準備時間(秒)：

圖1 M1的準備時間

圖2 M2的準備時間

圖3 M3的準備時間

圖4 M4的準備時間

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

表2 各工件加工時間

模型如圖5所示。

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

2 模型的仿真及優化

圖5 JSP模型

2.1 模型的仿真結果

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

圖6 未優化時的甘特圖

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

2.2 模型的優化

eM-Plant為我們提供了GA模塊進行對模型的優化，優化目標是使得仿真時間最短。JSP優化問題是典型的順序優化問題，我們可以選擇系統自帶的GASequence工具和GAWizard結合來進行優化。鑒于系統幫助文檔的參數值推薦，各參數設置如下[2]：

交叉概率：0.8

變異概率：0.1

代數：20

每代個體數量：10

優化后，零件進入系統的順序是J10,J4,J6,J5,J8,J3,J9,J7,J1,J2，甘特圖如7所示。

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

圖7 優化后的甘特圖

圖8 優化結果

3 結束語

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

[1] 王萬良,吳啟迪.生產調度智能算法及應用[M].科學出版社,2007.

[2] Tecnomatix Plant Simulation Help.

[3] 刑文訓,謝金星.現代優化計算方法[M].清華大學出版社,1999.

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