基于交替迭代遺傳算法的成批車間生產(chǎn)計(jì)劃與調(diào)度的集成優(yōu)化

熊福力，嚴(yán)洪森

（1. 東南大學(xué) 自動化學(xué)院，南京 210096；2. 復(fù)雜工程系統(tǒng)測量與控制教育部重點(diǎn)實(shí)驗(yàn)室，南京 210096）

基于交替迭代遺傳算法的成批車間生產(chǎn)計(jì)劃與調(diào)度的集成優(yōu)化

熊福力1,2，嚴(yán)洪森1,2

（1. 東南大學(xué) 自動化學(xué)院，南京 210096；2. 復(fù)雜工程系統(tǒng)測量與控制教育部重點(diǎn)實(shí)驗(yàn)室，南京 210096）

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

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

0 引言

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

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

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

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

1 成批jobshop車間生產(chǎn)計(jì)劃和調(diào)度的集成優(yōu)化模型

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

綜合考慮零部件生產(chǎn)費(fèi)用、零部件庫存費(fèi)用和欠產(chǎn)懲罰費(fèi)用、設(shè)備上加工任務(wù)的提前費(fèi)用、加班費(fèi)用以及零部件加工準(zhǔn)備工作費(fèi)用。集成優(yōu)化目標(biāo)函數(shù)可以表示成如下形式：

生產(chǎn)平衡約束考慮產(chǎn)品庫存量、產(chǎn)品需求量和計(jì)劃生產(chǎn)量之間的平衡關(guān)系

同時(shí)有非負(fù)約束：

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

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

1）當(dāng)pi,j+1＞pi,j時(shí)

2) 當(dāng)pi,j+1＜pij時(shí)

同時(shí)有工件加工順序約束：

利用調(diào)度約束來細(xì)化設(shè)備負(fù)荷約束有：

2 模型算法及算例

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

步驟 1：采用混合遺傳算法求解粗計(jì)劃模型得到初始生產(chǎn)計(jì)劃。

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

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

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

步驟 5：如果滿足算法終止條件，則停止，輸出結(jié)果；否則，轉(zhuǎn)步驟3。

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

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

表1 ITERGA和CONTGA計(jì)算性能的比較

3 結(jié)論

本文研究了一類零件加工有準(zhǔn)備時(shí)間且為批量生產(chǎn)的job shop車間多周期生產(chǎn)計(jì)劃和調(diào)度的集成優(yōu)化問題，建立了該類問題的非線性混合整數(shù)規(guī)劃模型，并給出了一個(gè)交替式迭代集成優(yōu)化方法。由于該模型的復(fù)雜性并考慮到遺傳算法在求解大規(guī)模復(fù)雜組合優(yōu)化問題時(shí)表現(xiàn)出的優(yōu)越性，文中提出了一種混合交替迭代遺傳算法(ITERGA)用以求解該類問題。這相當(dāng)于在在生產(chǎn)計(jì)劃和調(diào)度求解兩個(gè)過程之間加一個(gè)循環(huán)迭代過程，將遞階算法構(gòu)成一個(gè)閉環(huán)系統(tǒng)，提高了求解速度，文中給出的大量算例的數(shù)值實(shí)驗(yàn)中，ITERGA方法所獲得的平均目標(biāo)值比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] 張曉東, 嚴(yán)洪森. 一類Job-Shop 車間生產(chǎn)計(jì)劃與調(diào)度的集成優(yōu)化[J] . 控制與決策, 2003, 18(5) ： 581-584.

[4] 何霆, 劉文煌, 梁力平. MES的計(jì)劃、調(diào)度集成問題研究[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] 尚文利, 范玉順. 成批生產(chǎn)計(jì)劃調(diào)度的集成建模與優(yōu)化[J]. 計(jì)算機(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計(jì)劃現(xiàn)代制造集成技術(shù)專題資助項(xiàng)目(2007AA04Z112)；國家自然科學(xué)基金資助項(xiàng)目(60934008, 50875046)

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