張 英，郭勁添

（武漢理工大學 物流工程學院，武漢430063）

我國部分造船企業(yè)早在20世紀80年代初就開始陸續(xù)應(yīng)用CAD、CAPP、CAM、GT等技術(shù)進行船舶設(shè)計和建造，90年代后，造船的先進制造技術(shù)和裝備也得到了大量引進和使用。然而造船生產(chǎn)的效果較差、競爭力低［1］，與世界造船先進水平相比，差距最大的是船舶生產(chǎn)組織和生產(chǎn)過程控制等方面［2］。

生產(chǎn)計劃是將產(chǎn)品按時段進行分解，計算得出零部件在各階段的時間節(jié)點，而零件的具體加工安排是借助車間作業(yè)調(diào)度來完成的。因此車間作業(yè)調(diào)度問題JSSP（job-shop scheduling problem）是實際生產(chǎn)計劃問題的關(guān)鍵，也是產(chǎn)品全生命周期管理中的一個關(guān)鍵環(huán)節(jié)，直接關(guān)系到造船企業(yè)的生產(chǎn)效率和成本。

目前有關(guān)JSSP的研究［3］在理論上探索較多，對于小規(guī)模的調(diào)度效果較好，但對于設(shè)備與零件數(shù)量都較多的實際問題，運算時間過長，工程應(yīng)用不太理想。

船舶制造的生產(chǎn)組織形式屬于典型的大型單件小批生產(chǎn)類型，生產(chǎn)過程復雜，沒有可供借鑒的實用模式，所以，研究這類生產(chǎn)計劃與調(diào)度模式，對提高我國整體造船水平具有現(xiàn)實意義。

1 造船生產(chǎn)特點與車間作業(yè)調(diào)度

現(xiàn)代船舶生產(chǎn)具有以下特征：①船舶制造屬于工程項目型的單件小批量生產(chǎn)類型，建造周期長，占用資金大，成本高；②是勞動密集型與技術(shù)密集型并存的、綜合性的大型組裝工業(yè)，工種、專業(yè)繁多，生產(chǎn)過程復雜，設(shè)備利用率低；③高空、立體交叉作業(yè)多，拼焊裝配的工件大、重，且形狀不一，移動困難，勞動生產(chǎn)率低，工作環(huán)境差；④配套企業(yè)多，配套產(chǎn)品復雜。

以上特征帶來船舶主要產(chǎn)品（如大型柴油機）的加工制造具有以下特點：①產(chǎn)品品種多、規(guī)格多變，加工設(shè)備多、設(shè)備柔性強；②生產(chǎn)管理難度大、生產(chǎn)周期長；③產(chǎn)品各部件之間的時序約束關(guān)系和成套性要求嚴格，約束條件復雜多變；④受多資源約束，諸如緊急件插入、設(shè)備故障、工作日程變更和組合件加工等問題［4］。

在現(xiàn)代造船模式下，合理地安排眾多的任務(wù)包的生產(chǎn)，滿足資源約束要求，并做到資源利用的均衡，是生產(chǎn)計劃的基本要求。面對復雜的造船生產(chǎn)，僅靠計劃制訂者個人的經(jīng)驗很難制訂出合理的生產(chǎn)計劃。

根據(jù)研究對象的復雜性，車間調(diào)度問題分為單機調(diào)度、并行機床調(diào)度、流水車間調(diào)度和作業(yè)車間調(diào)度問題JSSP，其中JSSP是指加工系統(tǒng)中有一組功能不同的機床，待加工的零件包括多道工序，每道工序在一臺機床上加工，零件的加工路線互不相同。車間作業(yè)調(diào)度問題是一個典型的NP難題，是最困難的組合優(yōu)化問題之一。由于調(diào)度問題涉及的因素很多，目前還沒有一個方法能夠?qū)囬g調(diào)度問題進行全面而有效的求解［5］。尤其是對于車間調(diào)度問題中的高度動態(tài)性和復雜性還缺乏有效的研究方法。

遺傳算法以其內(nèi)在的隱并行性和較好的全局尋優(yōu)能力，在JSSP問題求解中得到了較好的應(yīng)用，而且隨著遺傳結(jié)構(gòu)的不斷改進，它的有效性也在不斷提高［6］。然而，遺傳算法并不能較好地處理JSSP問題的高度動態(tài)性和隨機性問題。為此，對JSSP問題先采用遺傳算法尋優(yōu)，然后利用EXTEND仿真軟件進行建模和仿真，有效地彌補了遺傳算法的不足。

2 JSSP問題的數(shù)學模型及特征

2.1 JSSP問題的數(shù)學模型

JSSP問題的一種簡單情形可描述為，有m個任務(wù)（產(chǎn)品）需要分配給n個工序（機器）去完成，每個任務(wù)只能分配給1個工序處理，并且每個工序只能處理1個任務(wù)，不同的分配將會花費不同的代價。JSSP問題要求找到1種分配方案使所花費的總代價最小。

若第i個工序完成第j項任務(wù)的代價Cij≥0，則可以構(gòu)成代價矩陣Cn×m。在求解如何把任務(wù)分配給各個加工工序的條件下，使得所花費的總代價為最小。假設(shè)

則排產(chǎn)問題可以轉(zhuǎn)化為求解排產(chǎn)矩陣Rn×m，其約束條件如下：

因此所求目標函數(shù)為：

4.防治方法。徹底清塘，有機肥要充分發(fā)酵后再使用，保持優(yōu)良的水質(zhì)，加強管理，科學投餌，提高魚體免疫能力，有寄生蟲時及時殺蟲。發(fā)病季節(jié)定期潑灑生石灰或漂白粉，防止此病發(fā)生。

其中，Cij∈Cn×m，Rij∈Rn×m。

2.2 JSSP問題的特征

對于實際的JSSP問題，如多個工作中心處理一系列不同的作業(yè)，這種問題屬于NP-hard問題。其中，如果有m個任務(wù)要經(jīng)過n個加工工序進行加工，并且所有的任務(wù)都要經(jīng)過所有的加工工序，那么就有（m?。┓N可選的作業(yè)排序。因此，即使是小規(guī)模的生產(chǎn)排產(chǎn)也會有大量的排產(chǎn)方案，如果僅僅使用數(shù)學方法來進行求解往往是比較困難的，此時有必要結(jié)合其他的優(yōu)化算法（如遺傳算法）來縮小解空間并求解出較佳的排產(chǎn)方案。

在進行排產(chǎn)問題的研究時，對方案的衡量標準通常應(yīng)具有以下四個方面［7］：

1）滿足顧客交貨日期或者下游操作要求；

2）流程時間（工件在整個流程中的時間）最短；

3）在制品庫存最?。?/p>

4）機器或者勞動力空閑時間最小。

3 JSSP問題建模與仿真優(yōu)化

現(xiàn)實的車間作業(yè)調(diào)度系統(tǒng)都是離散事件動態(tài)系統(tǒng)（DEDS），任務(wù)的到達具有隨機性及不確定性。EXTEND，為了方便用戶解決DEDS的優(yōu)化問題，專門開發(fā)了遺傳算法優(yōu)化模塊。另外，EXTEND軟件中所有模塊的源代碼都是公開的，用戶只需要熟悉C語言，就可以輕松地嵌入自己改進的遺傳算法程序。

3.1 問題描述

某船廠加工車間有4個產(chǎn)品要進行生產(chǎn)，而每個產(chǎn)品必須依次經(jīng)過4個加工工序進行加工，各個產(chǎn)品在各個工序中消耗的時間見表1。現(xiàn)要求以總生產(chǎn)時間最短為目標，通過EXTEND軟件建立仿真模型，然后求出最佳的排產(chǎn)方案。

表1 各產(chǎn)品在各工序間的生產(chǎn)時間

3.2 EXTEND建模

建立排產(chǎn)模型的最終目標是求解出產(chǎn)品生產(chǎn)時間最短的產(chǎn)品生產(chǎn)順序，因此在建模的時候，可以把各個產(chǎn)品設(shè)置一個初始的優(yōu)先權(quán)，然后通過仿真模型并結(jié)合遺傳算法優(yōu)化模塊求解出各個產(chǎn)品的最佳生產(chǎn)優(yōu)先權(quán)，然后再按照所求的優(yōu)先權(quán)順序進行排產(chǎn)生產(chǎn)就可以得到所有產(chǎn)品生產(chǎn)的最佳生產(chǎn)時間。根據(jù)實際生產(chǎn)布局以及相關(guān)的數(shù)據(jù)，通過EXTEND軟件建模，見圖1。

圖1 排產(chǎn)仿真模型

在這個仿真模型中，首先給各個產(chǎn)品設(shè)定一個初始的加工優(yōu)先權(quán)，產(chǎn)品1、產(chǎn)品2、產(chǎn)品3和產(chǎn)品4按照優(yōu)先順序在緩沖器進行排隊，然后再依次進入各個工序（工序1、工序2、工序3和工序4）進行加工。當4個產(chǎn)品全部加工完畢后，處理時間統(tǒng)計模塊對這4個產(chǎn)品所需要的總時間進行匯總統(tǒng)計。

圖1中，標注有產(chǎn)品1～4、工序1～4以及處理時間統(tǒng)計的模塊為層級模塊，它們都各自包含自己的層級。使用層級處理是為了使模型看上去更加簡潔、明了。產(chǎn)品1、工序1和處理時間統(tǒng)計層級塊及各自的層級結(jié)構(gòu)詳見圖2、3、4。產(chǎn)品2、產(chǎn)品3和產(chǎn)品4的層級塊的結(jié)構(gòu)與產(chǎn)品1類似，工序2、工序3和工序4的層級結(jié)構(gòu)與工序1類似。

圖2 產(chǎn)品1層級塊

在產(chǎn)品1的層級中，它所要實現(xiàn)的功能為：對產(chǎn)品1進行輸出，并設(shè)置其加工優(yōu)先權(quán)以及在各個工序的處理時間。

圖3 工序1層級

在工序1的層級中，工序1的加工機器能夠讀取前面各個產(chǎn)品在工序1的加工時間。

圖4 處理時間統(tǒng)計模塊的層級

在處理時間統(tǒng)計模塊的層級中，對產(chǎn)品輸出數(shù)量進行統(tǒng)計，當產(chǎn)品輸出數(shù)量為4時，模型就會自動停止對產(chǎn)品加工總時間的統(tǒng)計，并輸出4個產(chǎn)品加工所用的總時間。

3.3 仿真結(jié)果分析

首先，將決策的參數(shù)變量（各個產(chǎn)品加工的優(yōu)先權(quán)）以及目標函數(shù)（最短的加工總時間）在遺傳算法優(yōu)化模塊中進行設(shè)置，然后運行遺傳算法優(yōu)化模塊?？偣策M化了51次，并且種群最終100%收斂，見圖5。

圖5 遺傳算法優(yōu)化圖

從圖5中可以看到，優(yōu)化目標（最短總加工時間）很快收斂到最小值22，而種群也在迭代17次后100%收斂。

收斂后的結(jié)果見表2。

表2 遺傳算法優(yōu)化結(jié)果

從表2可以看到，產(chǎn)品1～4的優(yōu)先權(quán)從小到大的排列順序為產(chǎn)品3、產(chǎn)品2、產(chǎn)品4和產(chǎn)品1。在EXTEND仿真軟件中，優(yōu)先權(quán)越小，優(yōu)先級越大。因此這4種產(chǎn)品在流水線上的加工順序應(yīng)為：產(chǎn)品3、產(chǎn)品2、產(chǎn)品4和產(chǎn)品1。

4 結(jié)論

為了便于證明方法的可行性，本文僅對一典型排產(chǎn)過程進行了分析，而且只實現(xiàn)了作業(yè)時間這一種資源的最小化的優(yōu)化。但是從中可以看到，應(yīng)用EXTEND仿真軟件可以實現(xiàn)JSSP中的排產(chǎn)優(yōu)化。在實際應(yīng)用中，只需對作業(yè)對象以及相應(yīng)的資源約束作相應(yīng)的替換，就可以同樣應(yīng)用EXTEND軟件實現(xiàn)在多種資源約束的條件下，確定最佳的作業(yè)生產(chǎn)順序，制訂出合理的生產(chǎn)計劃。當實際生產(chǎn)過程中的情況發(fā)生變化時，應(yīng)用EXTEND仿真軟件，并通過計算機可以對生產(chǎn)作業(yè)及時地調(diào)整，使生產(chǎn)計劃符合生產(chǎn)實際，保證造船生產(chǎn)的高效進行。

［1］朱汝敬.入世對我國船舶工業(yè)的影響及應(yīng)對［J］.船舶經(jīng)濟貿(mào)易，2000（2）：10.

［2］徐學光.探索船舶工業(yè)的持續(xù)發(fā)展［J］.上海造船，1999（1）：15.

［3］何 霆，馬玉林，楊 海.車間生產(chǎn)調(diào)度問題的研究［J］.機械工程學報，2000，36（5）：97-102.

［4］周宏根，蔡 勇，景旭文，朱文彬.船舶柴油機大規(guī)模動態(tài)作業(yè)車間調(diào)度系統(tǒng)及其關(guān)鍵技術(shù)研究［J］.機械設(shè)計與制造，2006（4）：177-179.

［5］Dagli C.H，Sittisathanchai S.Genetic neuro-scheduler：A new approach for job-shop scheduling［J］.Production Economics，1995（41）：135-145.

［6］玄光男，程潤偉.遺傳算法與工程設(shè)計［M］.北京：科學出版社，2000.

［7］李錦飛，馬漢武，陳紀南.生產(chǎn)管理與調(diào)度［M］.北京：化學工業(yè)出版社，2005.