運(yùn)輸能力有限混合流水車間調(diào)度的改進(jìn)拉格朗日松弛算法

軒 華

（鄭州大學(xué)管理工程學(xué)院，河南 鄭州 450001）

0 引言

在許多制造系統(tǒng)中，半成品要通過吊車或自動(dòng)引導(dǎo)車（Automatic Guided Vehicle，AGV）從一臺(tái)機(jī)器運(yùn)送至另一臺(tái)機(jī)器［1］。然而，很多傳統(tǒng)的調(diào)度模型都假設(shè)在任意兩個(gè)加工階段之間有足夠的運(yùn)輸機(jī)來完成運(yùn)輸任務(wù)，即工件j在完成階段i－1上的加工后可以馬上送到階段i上進(jìn)行加工。但在實(shí)際生產(chǎn)中，由于一個(gè)工件必須借助運(yùn)輸機(jī)完成相鄰兩個(gè)加工階段間的傳送，并且可利用的運(yùn)輸機(jī)及其運(yùn)輸能力都是有限的，上述假設(shè)并不成立。

本文研究了協(xié)調(diào)生產(chǎn)和運(yùn)輸?shù)幕旌狭魉囬g（Hybrid FlowShop，HFS）調(diào)度，其中假設(shè)工件具有動(dòng)態(tài)到達(dá)特性且運(yùn)輸機(jī)能力有限。流程工業(yè)中的HFS環(huán)境較為常見，如鋼鐵業(yè)、化工業(yè)和石化業(yè)等。例如鋼鐵業(yè)中的煉鋼—精煉生產(chǎn)過程［2］，煉鐵階段生產(chǎn)的鐵水通過魚雷車送到轉(zhuǎn)爐以煉制鋼水，然后由吊車將鋼水送至精煉階段進(jìn)行進(jìn)一步加工。如圖1所示，該過程可歸結(jié)為帶運(yùn)輸問題的HFS結(jié)構(gòu)。由于鋼鐵業(yè)中運(yùn)送的工件又大又重，假設(shè)每臺(tái)運(yùn)輸機(jī)的運(yùn)輸能力為1是合理的［3］。

很多學(xué)者對(duì)HFS調(diào)度進(jìn)行了研究，然而多數(shù)文獻(xiàn)都未考慮運(yùn)輸問題。Luo等［4］利用遺傳算法求解帶處理機(jī)和機(jī)器維修時(shí)間段的兩階段HFS調(diào)度，目標(biāo)是最小化最大完成時(shí)間makespan。Behnamian等［5］結(jié)合遺傳算法和變鄰域搜索算法提出一個(gè)混合算法求解帶順序有關(guān)調(diào)整時(shí)間的HFS調(diào)度，其中加工時(shí)間取決于機(jī)器和資源，目標(biāo)是最小化makespan和總資源分配費(fèi)用；Li等［6］利用兩階段啟發(fā)式算法求解了帶順序相關(guān)調(diào)整時(shí)間的HFS調(diào)度；Nishi等［7］提出結(jié)合列生成的拉格朗日松弛（Lagrangian Relaxation，LR）來求解HFS調(diào)度，以最小化總加權(quán)拖期；Fiqielske［8］提出啟發(fā)式算法求解帶并行異構(gòu)機(jī)和附加資源的兩階段HFS調(diào)度，以最小化makespan。

就所查文獻(xiàn)可知，考慮生產(chǎn)與運(yùn)輸協(xié)調(diào)的HFS調(diào)度的研究頗少。Naderi等［9］提出改進(jìn)的模擬退火算法求解帶順序有關(guān)調(diào)整時(shí)間的HFS調(diào)度，以使總完成時(shí)間和總拖期最小化，其中考慮了從階段t－1到階段t之間和從階段t到階段t－1的運(yùn)輸時(shí)間，以及工件等待運(yùn)輸機(jī)返回的時(shí)間；Naderi等［10］提出電磁算法求解帶順序有關(guān)調(diào)整時(shí)間和工件無關(guān)運(yùn)輸時(shí)間的HFS調(diào)度，目標(biāo)是最小化總加權(quán)拖期；Tang等［11］從實(shí)際煉鋼精煉生產(chǎn)過程中提煉出帶等待時(shí)間和運(yùn)輸?shù)膬呻A段HFS調(diào)度，利用禁忌搜索算法進(jìn)行求解，以使最大完成時(shí)間、空閑時(shí)間懲罰和等待時(shí)間懲罰之和最小化，或使最大完成時(shí)間、空閑時(shí)間懲罰和與等待時(shí)間有關(guān)的熱損懲罰之和最小化。

從上述文獻(xiàn)可以總結(jié)出，現(xiàn)有研究缺乏對(duì)求解帶運(yùn)輸考慮的HFS調(diào)度的LR算法和總加權(quán)完成時(shí)間問題的探討。本文的主要工作是對(duì)帶有限運(yùn)輸能力的動(dòng)態(tài)HFS調(diào)度問題建立數(shù)學(xué)模型，進(jìn)而設(shè)計(jì)基于階段分解的LR來求解；設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法來求解分解后的工件帶任意權(quán)重且有機(jī)器不可用時(shí)間段的并行同構(gòu)機(jī)子問題。

1 數(shù)學(xué)建模

1.1 問題描述

所研究的HFS調(diào)度問題可描述如下：n個(gè)工件在h個(gè)加工階段按相同加工順序進(jìn)行加工，至少有一個(gè)加工階段有多臺(tái)并行同構(gòu)機(jī)；每臺(tái)機(jī)器一次至多加工一個(gè)工件，而每個(gè)工件只能在一臺(tái)機(jī)器上加工，假設(shè)工件動(dòng)態(tài)到達(dá)第一個(gè)加工階段；當(dāng)工件j完成在階段i的加工后，由一臺(tái)運(yùn)輸機(jī)送到下一階段i＋1上，這兩個(gè)階段間可用的運(yùn)輸機(jī)數(shù)有Ri，i＋1臺(tái)，每臺(tái)運(yùn)輸機(jī)一次只能運(yùn)送一個(gè)工件，它將工件送至階段i＋1后返回階段i，設(shè)從階段i到階段i＋1的運(yùn)輸時(shí)間為Ti，i＋1，從階段i＋1到階段i的返程時(shí)間為RTi，i＋1，假設(shè)Ti，i＋1和RTi，i＋1為常數(shù)，與傳送的工件無關(guān)且不可忽略不計(jì)。

1.2 建模策略

將運(yùn)輸機(jī)看作是虛擬機(jī)器，則在運(yùn)輸階段工件的加工時(shí)間等于從前一加工階段到后一加工階段的運(yùn)輸時(shí)間，因此可將考慮運(yùn)輸?shù)脑瓎栴}轉(zhuǎn)換為與其等價(jià)的、不考慮運(yùn)輸?shù)紨?shù)階段有工件相關(guān)不可用機(jī)器時(shí)間段的調(diào)度問題，轉(zhuǎn)換成的階段數(shù)為（2×h－1），且運(yùn)輸階段總在偶數(shù)階段。

需要注意的是，在轉(zhuǎn)換后的問題中，偶數(shù)階段的機(jī)器（運(yùn)輸機(jī)）有不可用時(shí)間段，這意味著機(jī)器不能連續(xù)被使用。因?yàn)楫?dāng)運(yùn)輸機(jī)把工件送到下一加工階段后，經(jīng)返程時(shí)間后才能繼續(xù)執(zhí)行下一運(yùn)輸任務(wù)，所以運(yùn)輸機(jī)在返程的這段時(shí)間內(nèi)是不能使用的。假設(shè)工件［j］和［j＋1］在偶數(shù)階段i的同一臺(tái)機(jī)器l上加工，其中［j］表示加工序列中的第j個(gè)位置，則在偶數(shù)階段i上，機(jī)器l的不可用時(shí)間段從工件［j］在該運(yùn)輸階段的完成時(shí)間Ci［j］的下一時(shí)刻開始直到Ci［j］＋rti－1，i＋1變化，其中rti－1，i＋1為轉(zhuǎn)換后問題的返程時(shí)間。因此，機(jī)器不可用時(shí)間段與工件有關(guān)，且是變化的。

1.3 模型

基于上述建模策略，建立轉(zhuǎn)換后的調(diào)度問題的數(shù)學(xué)模型如下：

（1）參數(shù)

j為工件，j∈Z，Z＝ ｛1，2，…，n｝，其中n是工件數(shù)；

［j］l為在機(jī)器l上加工的工件序列中的第j個(gè)位置，j∈J；

i為階段，i∈｛1，2，…，s｝，其中s是轉(zhuǎn)換后的包括運(yùn)輸階段在內(nèi)的總階段數(shù)；

k為時(shí)間，k∈｛1，2，…，K｝，其中K 是時(shí)間水平；

mi為階段i可利用的機(jī)器數(shù)；

wj為工件j的權(quán)重；

pij為工件j在階段i上的加工時(shí)間，在其值偶數(shù)階段上為運(yùn)輸時(shí)間，在奇數(shù)階段上為機(jī)器上的加工時(shí)間；

rj為工件j的釋放時(shí)間；

rti－1，i＋1為從階段i＋1到階段i－1的返程時(shí)間，等于RTi／2＋1，i／2，i＝2，4，…，s－1。

（2）變量

Xijk＝1 工件j在時(shí)刻k正在階段i上加工

0｛否則，j∈J，i＝1，2，…，s，k＝1，…，K；

Cij為工件j在階段i的完成時(shí)間，j∈J，i＝1，…，s，它是時(shí)間點(diǎn)（Cij＝k表示工序在時(shí)間k的末端完成加工）。

利用上述建模策略和參數(shù)，對(duì)帶有限運(yùn)輸能力的動(dòng)態(tài)HFS調(diào)度問題建模如下：

上述模型中，目標(biāo)函數(shù)（1）是最小化總加權(quán)完成時(shí)間；約束（2）表示工件的工序優(yōu)先級(jí)要求；約束（3）定義了機(jī)器能力要求；約束（4）表示在偶數(shù)（運(yùn)輸）階段上，同一臺(tái)機(jī)器（運(yùn)輸機(jī)）上加工的相鄰兩工件之間，只有當(dāng)前一個(gè)工件被送到下一階段且該機(jī)器（運(yùn)輸機(jī)）返回到該階段，才能開始加工（運(yùn)送）下一個(gè)工件；約束（5）說明在奇數(shù)階段上，同一臺(tái)機(jī)器上加工的相鄰兩工件之間，當(dāng)前一工件完成在該階段的加工后，下一個(gè)工件可以馬上開始它在該機(jī)器的加工；約束（6）表示每個(gè)工件只有當(dāng)它到達(dá)第一個(gè)階段后才能開始加工；約束（7）～約束（9）定義了加工時(shí)間、開始時(shí)間和完成時(shí)間要求；約束（10）～約束（11）定義了變量取值范圍。

2 求解方法——拉格朗日松弛算法

目標(biāo)函數(shù)（1）是加和的形式且約束是線性的，因此可以應(yīng)用LR算法求解上述模型。然而，如果使用傳統(tǒng)的基于工件分解的LR，則由于約束（3）～約束（5）都耦合了不同工件，需要將它們都松弛到目標(biāo)函數(shù)中，而松弛的約束數(shù)越多，得到的原問題的下界越松［12］。因此，本章設(shè)計(jì)了基于階段解耦的LR算法來求解上述模型，該算法首次由Tang等［13］提出并用于求解一般的不考慮運(yùn)輸和工件動(dòng)態(tài)特性的HFS調(diào)度。

2.1 拉格朗日松弛

從1.3節(jié)可以看出，只有約束（2）耦合了不同階段，因此利用拉格朗日乘子｛πij｝松弛該約束到目標(biāo)函數(shù)中，從而形成LR問題：

上述目標(biāo)函數(shù)需滿足式（3）～式（11）和

πij≥0，i＝1，2，…，s－1，j∈Z。 （13）式中：π是由｛πij｝組成的非負(fù)拉格朗日乘子向量，L（π）是乘子函數(shù)，定義為拉格朗日對(duì)偶。因此，拉格朗日對(duì)偶問題為

滿足式（3）～式（11）和式（13）。

給定｛πij｝，上述松弛問題可以分解為多個(gè)階段級(jí)子問題，每個(gè)子問題對(duì)應(yīng)一個(gè)階段。階段i（i∈｛1，…，s｝）的子問題可以表示為

利用LR算法求解上述模型的過程如圖2所示。下面將詳細(xì)描述對(duì)偶問題的求解、可行解的構(gòu)造和子問題的求解。

2.2 更新拉格朗日乘子和構(gòu)造可行解

每次迭代仍應(yīng)用次梯度算法更新拉格朗日乘子：

式中：a為迭代數(shù)；γa為第a次迭代的步長；g（πa）為L（π）的次梯度，其值等于（Cij－ Ci＋1，j＋ pi＋1，j）。γa定義為

式中：L＊為最優(yōu)解，由迄今為止得到的最好可行目標(biāo)函數(shù)值來估計(jì)；La是第a次迭代的L的值。

當(dāng)對(duì)偶間隙非常小或迭代數(shù)達(dá)到限制值時(shí)程序停止。因?yàn)槊看蔚鷱乃沙趩栴}得到的解對(duì)于原問題來說常是不可行解，所以利用兩階段啟發(fā)式將不可行時(shí)間表轉(zhuǎn)換成可行時(shí)間表。在第一階段，對(duì)于階段i（i＝1，…，s），按照松弛問題中工序開始時(shí)間的增序排列各個(gè)工件，根據(jù)形成的列表依次將所有工件安排到可利用的機(jī)器上；在第二階段，通過兩兩交換改進(jìn)上述得到的可行解。

3 求解帶機(jī)器不可用時(shí)間段的并行同構(gòu)機(jī)子問題的動(dòng)態(tài)規(guī)劃

第2.1節(jié)所得到的拉格朗日子問題是帶機(jī)器不可用時(shí)間段和工件動(dòng)態(tài)到達(dá)的并行同構(gòu)機(jī)調(diào)度問題，目標(biāo)是最小化總加權(quán)完成時(shí)間（其中權(quán)重是任意值），且機(jī)器不可用時(shí)間段與工件有關(guān)。Tang等［13］提出動(dòng)態(tài)規(guī)劃算法求解并行同構(gòu)機(jī)調(diào)度問題，但該研究未考慮機(jī)器的不可用時(shí)間段和工件的動(dòng)態(tài)特性，即假設(shè)在任一階段的機(jī)器l上工件［j＋1］可在Ci［j］＋1時(shí)刻立刻開始加工，而且所有工件在計(jì)劃時(shí)間范圍一開始就可利用。對(duì)任一階段i，該研究證明了子問題中的工件在機(jī)器l上需要按照帶正權(quán)重的工序子集、帶零權(quán)重的工序子集、帶負(fù)權(quán)重的工序子集的順序進(jìn)行調(diào)度，而且在帶正負(fù)權(quán)重的工序子集中的工序必須按照加權(quán)最短加工時(shí)間（Weighted Shortest Processing Time，WSPT）規(guī)則進(jìn)行排列。

然而，本文研究的子問題中，在偶數(shù)階段上機(jī)器l在時(shí)間段［Ci［j］＋1，Ci［j］＋rti－1，i＋1］上不可用于加工（運(yùn)送）工件［j＋1］，而且工件［j］在時(shí)刻rj到達(dá)第一個(gè)加工階段后才能開始加工。基于Tang等［13］的相關(guān)結(jié)論，提出下面的性質(zhì)和引理，使其提出的動(dòng)態(tài)規(guī)劃可推廣至解決帶機(jī)器不可用時(shí)間段和工件動(dòng)態(tài)到達(dá)特征的同構(gòu)并行機(jī)調(diào)度問題（證明過程參照文獻(xiàn)［13］）。

性質(zhì)1 令Gip，Gio和Gin分別表示在階段i機(jī)器l上的帶正權(quán)重的工序子集、帶零權(quán)重的工序子集和帶負(fù)權(quán)重的工序子集，則在最優(yōu)解中，這三組子集必須在機(jī)器l上按照Gip—Gio—Gin的順序進(jìn)行調(diào)度。在偶數(shù)階段，Gip和Gin內(nèi)的工序必須按照（pij＋rti－1，i＋1）／＾wij的升序排列；在奇數(shù)階段，Gip和Gin內(nèi)的工序必須按照WSPT的順序排列，而Gio內(nèi)的工序可任意排列。

引理1 令O表示已經(jīng)分配到階段i上某臺(tái)機(jī)器l的工序集合。將工序y插入到O內(nèi)所有工序之前，若i＝2，4，…，s－1，則 ∑＾wijCij將增加W（O）（piy＋rti－1，i＋1）＋＾wiypiy，否則 ∑＾wijCij將增加（W（O）＋＾wiy）piy，其中W（O）表示集合O內(nèi)所有工序的總權(quán)重。

基于以上性質(zhì)和引理，可將動(dòng)態(tài)規(guī)劃的遞歸關(guān)系式歸結(jié)如下：

分別按照（pij＋rti－1，i＋1）／＾wij和pij／＾wij的增序排列偶數(shù)階段的所有工序和奇數(shù)階段的所有工序，令V（j′，Wi1，Wi2，…，Wimi）表示階段i上包含從第n道工序到第j′道工序的部分時(shí)間表的最小總加權(quán)完成時(shí)間，其中Wil是分配到階段i的機(jī)器l上的所有工序的總權(quán)重。

邊界條件：

對(duì)在階段i上所有的j′，V（j′，0，…，0）＝0。

遞歸關(guān)系式：

4 仿真測試

對(duì)所設(shè)計(jì)的算法用C語言編程并在微機(jī)（Pentium（R）1.73GHz）上運(yùn)行，當(dāng)?shù)鷶?shù)達(dá)到最大限制500或?qū)ε奸g隙小于一個(gè)很小的數(shù)（設(shè)為0.5%）時(shí)程序停止。計(jì)算結(jié)果通過對(duì)偶間隙和CPU時(shí)間來衡量，其中對(duì)偶間隙由可行解的目標(biāo)值與對(duì)偶函數(shù)的目標(biāo)值之差除以對(duì)偶函數(shù)目標(biāo)值，然后轉(zhuǎn)換成百分比得到。

在基于階段分解的LR算法中，分解后的階段級(jí)子問題數(shù)為s個(gè)，乘子數(shù)為n×（s－1），利用動(dòng)態(tài)規(guī)劃求解子問題時(shí)，其每個(gè)階段的狀態(tài)總數(shù)為mi，復(fù)雜度為O（（n－1）mi2）。而對(duì)于傳統(tǒng)的基于工件分解的LR算法，分解后的工件級(jí)子問題數(shù)為n個(gè)，乘子數(shù)為s×K，利用動(dòng)態(tài)規(guī)劃求解子問題時(shí)，其每個(gè)階段的狀態(tài)總數(shù)為K，復(fù)雜度為O（（s－1）K2），且若采用基于工件分解的LR算法，則需要松弛三組約束（3）～約束（5），這會(huì)使下界較松，進(jìn)而使對(duì)偶間隙較大。由以上性能可知，從子問題數(shù)、存儲(chǔ)空間、動(dòng)態(tài)規(guī)劃的復(fù)雜度和要松弛的約束數(shù)上，基于階段分解的LR算法都有較顯著的優(yōu)勢，因此本章主要測試基于階段分解的LR算法來檢查其有效性。

4.1 算例

通過測試小規(guī)模問題的一個(gè)實(shí)例，說明由LR算法得到的可行時(shí)間表。令n＝6，mi＝3，s＝3（包括運(yùn)輸階段），運(yùn)輸時(shí)間和返程時(shí)間設(shè)為4，K設(shè)為所有工件在各階段（包括運(yùn)輸階段）的加工時(shí)間之和，其他參數(shù)如表1所示。執(zhí)行算法可以得到該問題的近優(yōu)解，其調(diào)度甘特圖如圖3所示。

表1 實(shí)例數(shù)據(jù)

4.2 仿真實(shí)驗(yàn)

該實(shí)驗(yàn)測試了所提出的LR算法求解不同規(guī)模HFS調(diào)度問題的性能。問題實(shí)例隨機(jī)產(chǎn)生如下：令n＝ ｛20，50，70，100｝，s＝ ｛3，5，7｝（含運(yùn)輸階段），mi＝｛3，4，5｝；每個(gè)工件的加工時(shí)間和權(quán)重均由［1，10］均勻分布隨機(jī)產(chǎn)生，工件釋放時(shí)間滿足［1，5］的均勻分布，運(yùn)輸時(shí)間ti－1，i＋1和返程時(shí)間rti－1，i＋1滿足［4，6］之間的均勻分布，時(shí)間水平K 設(shè)為所有工件的加工時(shí)間之和（含運(yùn)輸階段）。n，s，mi共有36個(gè)組合，對(duì)每個(gè)組合隨機(jī)產(chǎn)生和測試10個(gè)不同的實(shí)例，故本節(jié)共產(chǎn)生和使用360個(gè)測試實(shí)例。

計(jì)算結(jié)果如表2所示，顯示于表1中的每個(gè)數(shù)（除最后一行外）都是所測得相同規(guī)模的10個(gè)實(shí)例的性能平均。

續(xù)表2

表2 不同規(guī)模問題的測試結(jié)果

從表2可以得出如下結(jié)論：

（1）所有實(shí)例在不到1min的計(jì)算時(shí)間內(nèi)得到的平均對(duì)偶間隙為12.44%。這說明對(duì)于所研究的帶有限運(yùn)輸能力和工件動(dòng)態(tài)特性的復(fù)雜調(diào)度問題，所設(shè)計(jì)的LR算法能夠在較短的運(yùn)行時(shí)間內(nèi)得到可接受的近優(yōu)解。

（2）相同工件數(shù)條件下，當(dāng)階段數(shù)增加時(shí)，因?yàn)殡A段數(shù)增多使得分解后的子問題數(shù)增加，從而使問題難以求解，所以解的質(zhì)量會(huì)變差，而且運(yùn)行時(shí)間也會(huì)加長。

（3）對(duì)于70和100個(gè)工件的大規(guī)模問題，LR算法平均耗時(shí)分別為69.55s和122.10s，得到的平均對(duì)偶間隙分別為11.67%和10.59%。因此當(dāng)問題規(guī)模較大時(shí)，所設(shè)計(jì)的LR算法表現(xiàn)出更大的求解潛力。

5 結(jié)束語

本文研究了運(yùn)輸和生產(chǎn)協(xié)調(diào)的動(dòng)態(tài)HFS調(diào)度問題，考慮了實(shí)際生產(chǎn)中運(yùn)輸機(jī)能力有限的要求，目標(biāo)是最小化總加權(quán)完成時(shí)間。將每臺(tái)運(yùn)輸機(jī)視為虛擬機(jī)器，從而將運(yùn)輸階段轉(zhuǎn)換為虛擬的加工階段，進(jìn)而對(duì)轉(zhuǎn)換后的不考慮運(yùn)輸能力但帶與工件有關(guān)的機(jī)器不可用時(shí)間段的動(dòng)態(tài)HFS調(diào)度問題建立數(shù)學(xué)模型。基于階段分解提出了LR算法對(duì)該問題進(jìn)行求解，對(duì)分解后的帶機(jī)器不可用時(shí)間段和工件動(dòng)態(tài)特性的并行同構(gòu)機(jī)調(diào)度，問題設(shè)計(jì)了動(dòng)態(tài)規(guī)劃算法進(jìn)行求解。數(shù)據(jù)實(shí)驗(yàn)表明，所設(shè)計(jì)的LR算法能夠在較短的運(yùn)行時(shí)間內(nèi)產(chǎn)生可接受的近優(yōu)解。進(jìn)一步的研究可推廣至運(yùn)輸能力超過1的HFS調(diào)度問題，以使該算法也適用于其他流程工業(yè)。

［1］ SOUKHAL A，OULAMARA A，MARTINEAU P.Complexity of flow shop scheduling problems with transportation constraints［J］.European Journal of Operational Research，2005，161（1）：32－41.

［2］ TANG 段 ，LUH L H，LIU L U，et al.Steel－making process scheduling using Lagrangian relaxation［J］.International Journal of Production Research，2002，40（1）：55－70.

［3］ TANG L，GONG H.A hybrid two－stage transportation and batch scheduling problem［J］.Applied Mathematical Modelling，2008，32（12）：2467－2479.

［4］ LUO H，HUANG 段 ，ZHANG Z A，et al.Hybrid flowshop scheduling with batch－discrete processors and machine maintenance in time windows［J］.International Journal of Production Research，2011，49（6）：1575－1603.

［5］ BEHNAMIAN J，F(xiàn)ATEMI GHOMI 段 T.Hybrid flowshop scheduling with machine and resource－dependent processing times［J］.Applied Mathematical Modelling，2011，35（3）：1107－1123.

［6］ LI L，WANG 段 ，HUO H O.Hybrid flowshop scheduling with setup times for cold treating process in Baoshan iron ＆steel complex［C］／／Proceedings of 2010International Conference on Logistics Systems and Intelligent Management.Washington，D.C.，USA：IEEE，2010，1：357－363.

［7］ NISHI T，HIRANAKA Y，INUIGUCHI M.Lagrangian relaxation with cut generation for hybrid flowshop scheduling problems to minimize the total weighted tardiness［J］.Computers and Operations Research，2010，37（1）：189－198.

［8］ FIGIELSKA E.A genetic algorithm and a simulated annealing algorithm combined with column generation technique for solving the problem of scheduling in the hybrid flowshop with additional resources［J］.Computers and Industrial Engineering，2009，56（1）：142－151.

［9］ NADERI B，ZANDIEH M，KHALEGHI GHOSHE BALAGH A，et al.An improved simulated annealing for hybrid flowshops with sequence－dependent setup and transportation times to minimize total completion time and total tardiness［J］.Expert Systems with Applications，2009，36（6）：9625－9633.

［10］ NADERI B，ZANDIEH M，SHIRAZI 段 H A.Modeling and scheduling a case of flexible flowshops：Total weighted tardiness minimization［J］.Computers and Industrial Engineering，2009，57（4）：1258－1267.

［11］ TANG 段 ，GUAN J，HU G A.Steelmaking and refining coordinated scheduling problem with waiting time and transportation consideration［J］.Computers ＆Industrial Engineering，2010，58（2）：239－248.

［12］ XUAN H，TANG 段 .Scheduling a hybrid flowshop with batch production at the last stage［J］.Computers ＆ Operations Research，2007，34（9）：2718－2733.

［13］ TANG 段 ，XUAN H，LIU X A.A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time［J］.Computers ＆ Operations Research，2006，33（11）：3344－3359.