丁小麗，朱 軍，劉 昶

DING Xiao-li1,2, ZHU Jun1, LIU Chang1

（1.中國科學(xué)院沈陽自動(dòng)化研究所，沈陽 110016；2.中國科學(xué)院大學(xué)，北京 100049）

0 引言

混合流水車間調(diào)度問題（Hybrid Flow-shop Scheduling Problem, HFSP）是由Salvador于1973年首先提出來的。HFSP是一類復(fù)雜的組合優(yōu)化問題，它是標(biāo)準(zhǔn)的flow-shop調(diào)度和并行機(jī)調(diào)度問題的綜合，相當(dāng)普遍地存在于化工、鋼鐵、制藥等流程工業(yè)中[1]。

等待時(shí)間受限的混合流水車間調(diào)度問題廣泛存在于鋼鐵生產(chǎn)，玻璃加工和塑料等行業(yè)，它的形成是由于生產(chǎn)過程中的高溫連續(xù)性，要求工件在相鄰兩個(gè)階段之間保持一定的溫度，例如在鋼鐵生產(chǎn)過程中的煉鋼-連鑄-熱軋過程中，連鑄機(jī)對(duì)溫度有嚴(yán)格的要求，為避免溫度降低影響鋼水質(zhì)量，不允許鋼水在工序間有過長的等待時(shí)間。因此，可將兩階段之間的溫度要求轉(zhuǎn)換為對(duì)等待時(shí)間的要求，從而形成了等待時(shí)間受限的混合流水車間調(diào)度問題。

目前，關(guān)于等待時(shí)間受限的HFS調(diào)度問題的研究較少。文獻(xiàn)[2]研究了具有零緩沖能力和有限等待時(shí)間的多處理器HFS問題，以總加權(quán)拖期最小為目標(biāo)，基于離散時(shí)間和混合整數(shù)線性規(guī)劃提出了一種精確求解算法。文獻(xiàn)[3]研究了以最小化makspan為目標(biāo)的等待時(shí)間受限的HFSP，提出了一種啟發(fā)式-禁忌算法來求解。文獻(xiàn)[4]針對(duì)考慮交貨期和等待時(shí)間受限的HFS調(diào)度問題，提出了一種結(jié)合回溯和鄰域搜索的混合算法來進(jìn)行求解。文獻(xiàn)[5]研究了以最小化生產(chǎn)等待時(shí)間為目標(biāo)的帶工件和工位等待時(shí)間的混合流水車間調(diào)度問題，提出運(yùn)用差分進(jìn)化算法來進(jìn)行求解。文獻(xiàn)[6]研究了以最小化各工件的提前/拖期懲罰和為目標(biāo)的帶交貨期和釋放期的等待時(shí)間受限的HFS調(diào)度問題，采用約束滿足優(yōu)化算法和指派規(guī)則的混合算法來進(jìn)行求解。

Gupta J N D[7]已經(jīng)證明即使只有兩個(gè)階段且其中只有一個(gè)階段包含多臺(tái)并行機(jī)的HFSP是NP難問題，因此，本文要研究的更為復(fù)雜的HFSP也是典型的NP難問題。拉格朗日松弛算法[8,9]是解決生產(chǎn)調(diào)度問題的有效方法之一，可用于NP難問題的求解，它通過將復(fù)雜約束引入到目標(biāo)函數(shù)，可將原問題分解為多個(gè)簡(jiǎn)單的容易求解的子問題，大大降低了問題的求解難度，可以獲得問題的近優(yōu)解。目前對(duì)于等待時(shí)間受限的混合流水車間調(diào)度問題的求解在算法方面集中于精確求解算法或者智能優(yōu)化類的近似算法。因此本文創(chuàng)新性的將拉格朗日松弛算法用于等待時(shí)間受限的混合流水車間調(diào)度問題研究中，拓展了拉格朗日松弛算法的應(yīng)用范圍和混合流水車間[10,11]調(diào)度理論。

本文針對(duì)等待時(shí)間受限的混合流水車間調(diào)度問題，首先建立了以最小化加權(quán)完成時(shí)間為目標(biāo)的HFSP模型，然后在此基礎(chǔ)上設(shè)計(jì)相關(guān)的拉格朗日松弛算法來進(jìn)行求解，最后通過實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證算法的可行性和有效性。

1 HFSP問題描述及建模

所研究的等待時(shí)間受限的HFSP可描述如下： n個(gè)工件在流水線上經(jīng)過相同的s個(gè)階段的加工，每個(gè)階段上有Mj臺(tái)同構(gòu)并行機(jī)，每個(gè)工件可以在階段j的任意一臺(tái)機(jī)器上進(jìn)行加工，已知工件i在階段j的加工時(shí)間為pij，同時(shí)工件i在相鄰階段j和j+1之間的等待時(shí)間不超過一定的時(shí)間上限aj。其中，每臺(tái)機(jī)器一次最多加工一個(gè)工件，每一個(gè)工件在任意時(shí)刻最多只能在一臺(tái)機(jī)器上進(jìn)行加工，且加工過程是連續(xù)的，不允許發(fā)生中斷。調(diào)度問題就是確定各個(gè)工件在各階段的加工完成時(shí)間Cij，從而使得總加權(quán)完成時(shí)間達(dá)到最小。

上述模型中目標(biāo)函數(shù)(1)為所有工件的總加權(quán)完成時(shí)間。約束(2)表示機(jī)器容量約束，即同一時(shí)刻在同一階段進(jìn)行加工的工件數(shù)不超過該階段的機(jī)器數(shù)；約束(3)表示同一工件在同一時(shí)刻最多只能在加工過程中的一個(gè)階段進(jìn)行加工；約束(4)為工件的時(shí)間優(yōu)先級(jí)約束，表示工件只有在完成上一階段的加工之后才能進(jìn)入下一階段的加工；約束(5)表示工件在相鄰階段之間的等待時(shí)間不超過一定的上限；約束(6)～(8)表示機(jī)器占用約束；約束(9)和約束(10)為相關(guān)變量的取值范圍定義。

等待時(shí)間受限的HFSP調(diào)度問題模型就是在滿足約束(2)～(10)的條件下將工件安排到各階段的機(jī)器上進(jìn)行加工，使得所有工件的總加權(quán)完成時(shí)間達(dá)到最小。

2 算法設(shè)計(jì)

拉格朗日松弛（LR）算法是解決生產(chǎn)調(diào)度問題的有效方法之一，可用于NP難問題的求解，它通過將復(fù)雜約束引入到目標(biāo)函數(shù)，可將原問題分解為多個(gè)簡(jiǎn)單的容易求解的子問題，大大降低了問題的求解難度，可以獲得問題的近優(yōu)解。整個(gè)求解過程如下：首先通過引入一組拉格朗日乘子將復(fù)雜約束松弛到目標(biāo)函數(shù)中，形成拉格朗日松弛問題；然后將得到的LR問題分解為一系列簡(jiǎn)單的子問題進(jìn)行求解，最后對(duì)于松弛問題的解一般需要通過可行化來構(gòu)造原問題的可行解；重復(fù)上述過程直至達(dá)到停止準(zhǔn)則?？尚薪獾哪繕?biāo)函數(shù)值提供了一個(gè)最優(yōu)解的上界，而對(duì)偶目標(biāo)函數(shù)值為最優(yōu)解的一個(gè)下界，這樣拉格朗日松弛算法同時(shí)也為衡量解的質(zhì)量提供了一個(gè)標(biāo)準(zhǔn)，解的質(zhì)量可以通過兩者之間的對(duì)偶間隙來進(jìn)行衡量（對(duì)偶間隙=[可行解的目標(biāo)值-對(duì)偶目標(biāo)值]/對(duì)偶目標(biāo)值）。

從上節(jié)所建立的模型中可以看出，約束(3)～(5)都耦合了不同的階段，如果要基于階段進(jìn)行分解需要將這三個(gè)約束都進(jìn)行松弛，松弛的約束越多，所得到的對(duì)偶目標(biāo)值就越松，而只有約束(2)耦合了不同的工件，因此，本文所設(shè)計(jì)的拉格朗日松弛算法采用基于工件進(jìn)行分解的策略，下面將詳細(xì)的介紹拉格朗日松弛過程、子問題的求解、乘子的更新以及可行解的構(gòu)造過程。

2.1 拉格朗日松弛

引入拉格朗日乘子向量 將約束(2)松弛到目標(biāo)函數(shù)(1)中，形成下面的拉格朗日松弛問題：

滿足約束(3)～(10)和：

通過不斷的逼近對(duì)偶問題的上界得到拉格朗日對(duì)偶問題：

滿足約束(3)～(10)和(12)。

當(dāng)乘子給定時(shí)，式(11)中的前半部分是一個(gè)常數(shù)，將后半部分基于工件進(jìn)行分解，得到多個(gè)工件級(jí)子問題，工件i 的工件級(jí)子問題可表示為：

滿足約束(3)～(10)和(12)。整理后得到：

因此， ( )LR λ 可歸結(jié)為：

滿足式(3)～(10)和(12)。

2.2 子問題的求解

利用反向動(dòng)態(tài)規(guī)劃來求解工件級(jí)子問題。當(dāng)給定工件i和一組乘子時(shí)，利用以下遞推公式來計(jì)算出工件i在各個(gè)階段的累積函數(shù)值：

2.3 構(gòu)造可行解

由于松弛了機(jī)器容量約束(2)，得到的松弛問題的解往往是不可行的，需要進(jìn)行可行化，構(gòu)造可行解的過程如下：首先根據(jù)得到的工件的完成時(shí)間計(jì)算出工件在各個(gè)階段的開始加工時(shí)間表。在每個(gè)加工階段，按照工件在該階段的開始加工時(shí)間的增序進(jìn)行排列，依次將工件安排在可利用的機(jī)器上；然后檢查各個(gè)工件相鄰階段之間的等待時(shí)間是否滿足要求，如果某工件在相鄰兩階段之間的等待時(shí)間超過了給定的時(shí)間上限，則將該工件在前一階段的開始加工時(shí)間后移，與后一個(gè)工件進(jìn)行兩兩交換，直到前后兩個(gè)階段之間的等待時(shí)間滿足要求為止。

2.4 更新拉格朗日乘子

采用次梯度算法來對(duì)拉格朗日乘子進(jìn)行更新。主要步驟如下：

STEP1：迭代次數(shù) 1n= 時(shí)，初始化拉格朗日乘子及相關(guān)參數(shù)。

STEP3：更新乘子。根據(jù)下列式子更新拉格朗日乘子：

其中nπ 是n次迭代步長，nπ 通過下式計(jì)算得到：

上式中GU是當(dāng)前得到的最優(yōu)的可行目標(biāo)值的上界；Gn是n次迭代的 ( )LR λ 值；ε初始值設(shè)為1，Gn上升時(shí)保持不變，當(dāng)Gn在若干次迭代中未發(fā)生變化時(shí)則取其一半。

STEP4：判斷是否滿足停止條件。若對(duì)偶間隙小于一個(gè)很小的數(shù)或達(dá)到了最大迭代次數(shù)，程序停止；否則返回STEP2進(jìn)行下一次迭代。

圖1為拉格朗日松弛算法流程圖。

圖1 拉格朗日松弛算法流程圖

3 仿真結(jié)果及分析

為了對(duì)所提出的拉格朗日松弛算法進(jìn)行可行性和有效性的驗(yàn)證，采用MATLAB對(duì)上述拉格朗日松弛算法進(jìn)行編程，并在Intel(R) Core(TM) CPU 3.2GHz的計(jì)算機(jī)上運(yùn)行。

分析表1～表3中的數(shù)據(jù)可以看出：

1）對(duì)于同一問題規(guī)模（當(dāng)工件數(shù)和階段數(shù)一定時(shí)），隨著并行機(jī)器數(shù)的增加，可利用的機(jī)器資源增加，運(yùn)行時(shí)間有所減少，對(duì)偶間隙也得到了改善；

2）對(duì)于同一規(guī)模問題，隨著相鄰階段之間的等待時(shí)間的增大，算法的運(yùn)行時(shí)間相應(yīng)加長，得到的解質(zhì)量略有下降（對(duì)偶間隙略有增加）。即和對(duì)解的質(zhì)量（對(duì)偶間隙）的影響很小，由此說明所設(shè)計(jì)的拉格朗日松弛算法對(duì)于不同的等待時(shí)間均能得到較好的近優(yōu)解。

3）對(duì)于不同規(guī)模問題而言，時(shí)算法的運(yùn)行時(shí)間隨之增加。且當(dāng)由5增加到10時(shí)，運(yùn)行時(shí)間有較大幅度的增加。

圖2為不同工件數(shù)在加工階段數(shù)為5，各個(gè)階段的機(jī)器數(shù)為4，等待時(shí)間為10的情況下對(duì)偶間隙隨迭代次數(shù)變化趨勢(shì)圖，三條曲線分別反應(yīng)了工件數(shù)為10，20和40時(shí)的對(duì)偶間隙變化，從圖中可以看出：

1）所設(shè)計(jì)的拉格朗日松弛算法在迭代前期有較好的收斂速度，隨著迭代次數(shù)的增加，收斂速度逐漸減緩并最終趨向于收斂。

2）在加工階段和機(jī)器數(shù)量相同時(shí)，在同一迭代次數(shù)下，規(guī)模較大的問題的對(duì)偶間隙比規(guī)模較小的問題的對(duì)偶間隙要相對(duì)大一些，即規(guī)模較小的問題所得到的解的質(zhì)量相對(duì)好一些。

表1 n=10的仿真結(jié)果

表2 n=20的仿真結(jié)果

表3 n=40的仿真結(jié)果

圖2 不同工件數(shù)時(shí)對(duì)偶間隙隨迭代次數(shù)變化趨勢(shì)

綜合上述分析可以看出，本文所設(shè)計(jì)的拉格朗日松弛算法能夠在較短的時(shí)間內(nèi)產(chǎn)生較好的近優(yōu)解，可以用于等待時(shí)間受限的混合流水車間調(diào)度問題中。

4 結(jié)束語

本文針對(duì)由于生產(chǎn)過程中的高溫連續(xù)性等要求而產(chǎn)生的等待時(shí)間受限的混合流水車間問題進(jìn)行問題建模和算法的研究。首先建立了等待時(shí)間受限的混合流水車間調(diào)度問題模型，然后在此基礎(chǔ)上設(shè)計(jì)相應(yīng)的拉格朗日松弛算法來進(jìn)行求解。該算法通過將機(jī)器容量約束松弛到目標(biāo)函數(shù)中，進(jìn)而將得到的松弛問題分解為一系列易于求解的工件級(jí)子問題來進(jìn)行求解，并利用動(dòng)態(tài)規(guī)劃算法來求解子問題，然后對(duì)得到的松弛問題的解利用一種啟發(fā)式算法來進(jìn)行可行化，并通過次梯度算法來不斷更新乘子。最后對(duì)設(shè)計(jì)的算法進(jìn)行仿真驗(yàn)證，測(cè)試結(jié)果表明所設(shè)計(jì)的拉格朗日松弛算法能夠在較短的時(shí)間內(nèi)產(chǎn)生較好的近優(yōu)解。

[1] 王凌,周剛,許燁,等.混合流水線調(diào)度研究進(jìn)展[J].化工自動(dòng)化及儀表,2011,38(1):1-8.

[2] Gicquel C,Hege L,Minoux M, et al. A discrete time exact solution approach for a complex hybrid flow-shop scheduling problem with limited-wait constraints[J].Computers & Operations Research, 2012,39(3):629-636.

[3] Liu S Y, Cui J S, Li Y. Heuristic-Tabu algorithm for hybrid flowshop scheduling with limited waiting time[A].Wuhan:Proceeding of the International Symposium on Computational Intelligence and Design[C].2008:233-237.

[4] 尹兆濤,李鐵克.考慮交貨期和等待時(shí)間受限的HFS調(diào)度問題的混合算法[J].工業(yè)工程,2009,12(1):79-83.

[5] 王長濤,劉春光,胡平東,等.混合流水車間等待時(shí)間優(yōu)化研究[J]. 沈陽建筑大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,28(2):368-374.

[6] 肖擁軍,李鐵克,尹兆濤.考慮特殊時(shí)間約束的混合流水車間調(diào)度[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(8):205-207,231.

[7] Gupta J N D. Two stage,hybrid flow-shop scheduling problem[J]. Journal of Operational Research Society,1988,39(1):359-364.

[8] 軒華,唐立新.實(shí)時(shí)無等待HFS調(diào)度的一種拉格朗日松弛算法[J]. 控制與決策,2006,21(4):376-380.

[9] 杜書魁.需準(zhǔn)備時(shí)間的FFS調(diào)度的一種拉格朗日松弛算法[J].科學(xué)技術(shù)與工程,2012,12(6):1272-1277.

[10] 張其亮,陳永生.帶有阻塞限制的混合流水車間調(diào)度問題的混合粒子群求解算法[J].信息與控制,2013,42(2):252-257.

[11] 屈國強(qiáng).瓶頸指向的啟發(fā)式算法求解混合流水車間調(diào)度問題[J]. 信息與控制,2012,41(4):514-521,528.