熊福力，嚴洪森

（1. 東南大學 自動化學院，南京 210096；2. 復雜工程系統(tǒng)測量與控制教育部重點實驗室，南京 210096）

基于交替迭代遺傳算法的成批車間生產計劃與調度的集成優(yōu)化

熊福力1,2，嚴洪森1,2

（1. 東南大學 自動化學院，南京 210096；2. 復雜工程系統(tǒng)測量與控制教育部重點實驗室，南京 210096）

研究了一類零部件混批生產車間需要加工準備的多周期成批生產計劃與調度的集成優(yōu)化問題，建立了生產計劃和調度集成優(yōu)化的非線性混合整數規(guī)劃模型。并提出了一種交替式混合遺傳協調優(yōu)化算法求解該集成優(yōu)化問題。其主要思想是給定計劃用一混合遺傳算法求調度，反過來給定已求調度用另一混合遺傳算法求取新計劃，如此不斷交替使用兩個混合遺傳算法實現計劃與調度的同時優(yōu)化。仿真結果證明了該方法的可行性和有效性。

批量；作業(yè)車間調度；集成優(yōu)化；交替迭代方法；遺傳算法

0 引言

生產計劃與調度問題一直是生產運作與管理領域的研究熱點，通常生產計劃層和調度層是緊密聯系的，處在不同層次的生產計劃和調度都必須進行有效地溝通。生產計劃與調度集成優(yōu)化問題的求解方法目前主要有以下幾類：

1）采用遞階方法分層求解，即將生產計劃遞階分解為一系列不同的層次，然后采用一種自頂向下的方法由高層到低層依次作出決策[1]。這種遞階生產計劃在過去一段時間內曾被認為是求解大型復雜計劃問題的有效途徑。但是由于忽略了實際調度操作過程中的具體的能力約束而使得遞階分解的結果在實際生產過程中變得不可行。

2）采用集成模型優(yōu)化的方法，同時考慮不同層次的約束條件，建立整體優(yōu)化模型。在進行問題的求解時，有兩種主要的求解方法：一種是整體法[2-4]，對不同層次的所有決策同時進行處理。另一種是集成法[5,6]，同樣針對整體的優(yōu)化模型，先對不同層次的生產計劃分層求解，然后對不同層次的優(yōu)化結果進行協調和傳遞。

上述研究在求解集成優(yōu)化問題的時候，往往很難較快地得到滿意解，模型往往過于簡單，沒有充分考慮詳細的工序約束關系或者考慮的集成優(yōu)化目標過少，因此難以應用于實際，鑒于此，本文針對有準備時間的多周期成批jobshop車間生產計劃與調度的集成優(yōu)化問題，給出了批量連續(xù)生產的工序約束關系，為了解決求解時收斂速度較慢的問題，提出了一種交替迭代遺傳算法來求解改模型。

1 成批jobshop車間生產計劃和調度的集成優(yōu)化模型

本文研究的成批job-shop車間生產計劃與調度的集成優(yōu)化問題可描述如下：在車間中有M臺設備，需要生產N種零件，每種零件i包含ni道工序，每道工序必須在特定的一臺機器上加工，零件的加工工藝路線互不相同，該車間所生產的產品具有種類多、數量大的特點，采用成批生產，零件批量生產過程是連續(xù)不間斷的。生產過程中更換生產品種時需要不可忽略的準備時間。

綜合考慮零部件生產費用、零部件庫存費用和欠產懲罰費用、設備上加工任務的提前費用、加班費用以及零部件加工準備工作費用。集成優(yōu)化目標函數可以表示成如下形式：

生產平衡約束考慮產品庫存量、產品需求量和計劃生產量之間的平衡關系

同時有非負約束：

由于零件在做好準備工作之后才能開始加工,有

要保證批量為連續(xù)生產，應該滿足下述工序約束：

1）當pi,j+1＞pi,j時

2) 當pi,j+1＜pij時

同時有工件加工順序約束：

利用調度約束來細化設備負荷約束有：

2 模型算法及算例

為了有效地求解上述集成優(yōu)化模型, 本文研究了一種交替式迭代遺傳算法（AIHGA）。該算法的工作流程如下：

步驟 1：采用混合遺傳算法求解粗計劃模型得到初始生產計劃。

步驟 2：以初始生產計劃作為約束，采用另一混合遺傳算法尋找集成優(yōu)化模型的一個可行調度排序，作為初始調度。

步驟 3：以上一步得到的調度順序作為約束，采用生產計劃層混合遺傳算法來優(yōu)化生產計劃。

步驟 4：以上一步得到的生產計劃作為約束，采用調度層遺傳算法來優(yōu)化調度順序。

步驟 5：如果滿足算法終止條件，則停止，輸出結果；否則，轉步驟3。

上述混合交替迭代遺傳算法已經用Matlab7.0實現， 為了說明該算法的計算效果，這里給出一種計劃調度同時優(yōu)化遺傳算法（MOHGA）做比較，其基本思想是將計劃解和調度解編碼到同一染色體上，采用選擇，交叉和變異等操作同時優(yōu)化生產計劃和調度。表1是不同算例情況下本文提出的AIHGA算法和MOHGA算法的性能比較，所有算例都由軟件采用隨機的方式自動生成。為方便比較，2種算法中所用遺傳算法的交叉率均取為0.9，變異率均取為0.1。以設定的最大運行時間為終止條件。

實驗結果中可以看出，在相同運行時間下，從ITERGA獲得的目標函數值平均比CONTGA 的要小15.4%，同時也說明本文提出的集成優(yōu)化方法能夠較快地收斂到一個滿意解。

表1 ITERGA和CONTGA計算性能的比較

3 結論

本文研究了一類零件加工有準備時間且為批量生產的job shop車間多周期生產計劃和調度的集成優(yōu)化問題，建立了該類問題的非線性混合整數規(guī)劃模型，并給出了一個交替式迭代集成優(yōu)化方法。由于該模型的復雜性并考慮到遺傳算法在求解大規(guī)模復雜組合優(yōu)化問題時表現出的優(yōu)越性，文中提出了一種混合交替迭代遺傳算法(ITERGA)用以求解該類問題。這相當于在在生產計劃和調度求解兩個過程之間加一個循環(huán)迭代過程，將遞階算法構成一個閉環(huán)系統(tǒng)，提高了求解速度，文中給出的大量算例的數值實驗中，ITERGA方法所獲得的平均目標值比CONTGA的要小15.4%，具有較快的求解速度和精度。

[1] Bowers M R, Jarvis J P.A hierarchical production planning and scheduling model[J].Decision Sciences, 1992, 23(1)： 144-159.

[2] Karimi B, Fatemi G.The capacitated lot sizing problem： a review of model algorithms[J].The International Journal of Management Science, 2003, 31： 365-378.

[3] 張曉東, 嚴洪森. 一類Job-Shop 車間生產計劃與調度的集成優(yōu)化[J] . 控制與決策, 2003, 18(5) ： 581-584.

[4] 何霆, 劉文煌, 梁力平. MES的計劃、調度集成問題研究[J]. 制造業(yè)自動化, 2003, 25(3)： 24-26.

[5] Lasserre J B. An integrated model for job-shop planning and scheduling [J]. Management Science, 1992, 38(8)： 1201-1211.

[6] 尚文利, 范玉順. 成批生產計劃調度的集成建模與優(yōu)化[J]. 計算機集成制造系統(tǒng), 2005, 11(12)： 1163-1167.

Alternant iterative method based on genetic algorithm for integrated batch production planning and scheduling of a kind of jobshop

XIONG Fu-li1,2, YAN Hong-sen1,2

TB491

A

1009-0134(2011)5(下)-0095-02

10.3969/j.issn.1009-0134.2011.5(下).28

2011-01-07

國家863計劃現代制造集成技術專題資助項目(2007AA04Z112)；國家自然科學基金資助項目(60934008, 50875046)

熊福力（1974－），男，黑龍江肇東人，博士生，主要從事制造系統(tǒng)的生產計劃與調度建模和智能優(yōu)化算法等研究工作。