帶批和離散機(jī)柔性流水車間問(wèn)題的混合異步次梯度優(yōu)化的拉格朗日松弛算法

軒 華，王薛苑，李 冰

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

0 引言

鋼鐵業(yè)的一體化生產(chǎn)和化工業(yè)的許多實(shí)際生產(chǎn)問(wèn)題都可歸結(jié)為柔性流水車間問(wèn)題(Flexible Flow Shop Problem, FFSP)[1]。例如，煉鋼—連鑄—熱軋一體化生產(chǎn)過(guò)程由3個(gè)階段組成，經(jīng)煉鋼階段加工完成的鋼水在連鑄階段組成不同的澆次進(jìn)行澆鑄，同一澆次的多爐鋼水要在同一連鑄機(jī)使用相同結(jié)晶器連續(xù)不斷地進(jìn)行加工，最后在熱軋階段將連鑄板坯軋制成帶鋼。在該過(guò)程中，每個(gè)階段有多臺(tái)并行機(jī)，每個(gè)工件依次經(jīng)過(guò)這3個(gè)階段進(jìn)行加工，因此，該結(jié)構(gòu)可看作是FFS。不同于一般FFS的是，該生產(chǎn)過(guò)程中，連鑄機(jī)為串行批處理機(jī)，即它要求一個(gè)澆次(批)內(nèi)的爐次(工件)連續(xù)不間斷地進(jìn)行加工，一批的加工時(shí)間為該批內(nèi)所有工件的加工時(shí)間之和；而其他階段的機(jī)器為離散機(jī)，即一臺(tái)機(jī)器一次至多加工一個(gè)工件。因此，本文研究一類帶批和離散機(jī)的FFSP，其中，批處理機(jī)可以在任何一個(gè)加工階段。

批處理分為并行批處理和串行批處理兩類。前者的批加工時(shí)間是該批內(nèi)工件的最大加工時(shí)間，而后者的批加工時(shí)間則是組成該批的所有工件的加工時(shí)間之和。近年來(lái)，這兩類批處理的調(diào)度問(wèn)題已經(jīng)受到了廣泛的關(guān)注。

針對(duì)含并行批處理機(jī)的情況，文獻(xiàn)[2]提出了差分進(jìn)化算法求解階段1為多臺(tái)并行批處理機(jī)，而階段2含多臺(tái)離散機(jī)的兩階段FFSP，目標(biāo)是最小化makespan；文獻(xiàn)[3]對(duì)階段1有3臺(tái)等同的并行批處理機(jī)而階段2有一臺(tái)離散機(jī)的兩階段FFSP，提出了遺傳算法以最小化makespan；文獻(xiàn)[4]則研究了每階段有并行批處理機(jī)的兩階段FFSP，考慮了交貨期和工件準(zhǔn)備時(shí)間，目標(biāo)是總加權(quán)拖期，提出了結(jié)合鄰域搜索法的迭代階段分解方法。文獻(xiàn)[5]將鋼化玻璃制造的切割—磨邊—回火過(guò)程提煉為前兩個(gè)階段有多臺(tái)非等同機(jī)而第三個(gè)階段有1臺(tái)并行批處理機(jī)的三階段FFS，為最小化makespan，提出了構(gòu)造啟發(fā)式、遺傳算法，模擬退火算法求解實(shí)際大規(guī)模問(wèn)題。文獻(xiàn)[6]針對(duì)某一階段含多臺(tái)并行批處理機(jī)的多階段FFSP設(shè)計(jì)了一種基于時(shí)間窗的蟻群算法，目標(biāo)是最小化makespan。

針對(duì)串行批處理調(diào)度問(wèn)題，文獻(xiàn)[7]將煉鋼—連鑄—熱軋一體化生產(chǎn)環(huán)境歸結(jié)為作業(yè)車間結(jié)構(gòu)，其中連鑄機(jī)為串行批處理機(jī)，提出了基于工件分解和次梯度法的LR算法以最小化提前/拖期懲罰、連軋斷開(kāi)損失懲罰和板坯等待時(shí)間懲罰之和，通過(guò)測(cè)試8個(gè)爐次的一組實(shí)例驗(yàn)證了算法的有效性；文獻(xiàn)[8-10]針對(duì)煉鋼—連鑄的作業(yè)車間問(wèn)題分別提出了多Agent蟻群算法、改進(jìn)NSGA-Ⅱ算法和兩階段優(yōu)化算法，其中文獻(xiàn)[8]是最小化爐次的流程時(shí)間，文獻(xiàn)[9]旨在最大化爐次匹配度、最小化爐次等待時(shí)間及最小化澆次開(kāi)澆提前/拖期時(shí)間，文獻(xiàn)[10]的目標(biāo)是保證澆次準(zhǔn)時(shí)開(kāi)澆、澆次內(nèi)爐次連澆和等待時(shí)間最小。文獻(xiàn)[11]將煉鋼—連鑄生產(chǎn)抽象為流水車間問(wèn)題，提出了離散粒子群算法以最小化總完工時(shí)間。文獻(xiàn)[12]提出了一種混合模糊粒子群算法求解煉鋼—連鑄的FFSP，目標(biāo)是最小化makespan和爐次在工序間的等待時(shí)間；文獻(xiàn)[13]為最小化平均滯留時(shí)間、未啟動(dòng)的澆次開(kāi)工的提前/拖期、斷澆、初始調(diào)度和新調(diào)度中工序開(kāi)始時(shí)間之差的總和、初始調(diào)度和新調(diào)度中不同機(jī)器上加工的工序數(shù)的加權(quán)和，提出了改進(jìn)人工蜂群算法進(jìn)行求解煉鋼—精煉—連鑄生產(chǎn)的多階段FFS的再調(diào)度問(wèn)題；文獻(xiàn)[14]為某階段為串行批處理機(jī)的多階段FFSP設(shè)計(jì)了基于批分解的改進(jìn)LR算法以最小化總加權(quán)完成時(shí)間，為解決同一問(wèn)題，文獻(xiàn)[15]則提出了改進(jìn)遺傳算法；利用上述基于批分解的改進(jìn)LR算法，文獻(xiàn)[16]求解了從煉鋼—連鑄—熱軋生產(chǎn)提煉出的中間階段為批處理機(jī)的雙目標(biāo)問(wèn)題(即最小化總加權(quán)完成時(shí)間和滯留時(shí)間之和)。

然而，上述研究很少考慮工件的動(dòng)態(tài)到達(dá)，大多研究的是靜態(tài)調(diào)度，并且關(guān)于總加權(quán)完成時(shí)間問(wèn)題的探討很少，求解方法多為基于人工智能的近似算法，既有研究(文獻(xiàn)[14])雖求解了多達(dá)60個(gè)工件的中小規(guī)模問(wèn)題，但當(dāng)求解規(guī)模增大時(shí)，每次迭代求解松弛問(wèn)題消耗的運(yùn)行時(shí)間較長(zhǎng)，尤其是批數(shù)較多的大規(guī)模問(wèn)題。本文旨在利用基于最優(yōu)化的近似方法提出一種算法以有效求解這類含批處理機(jī)和離散機(jī)的動(dòng)態(tài)FFS總加權(quán)完成時(shí)間問(wèn)題，因此，提出了混合異步次梯度優(yōu)化的拉格朗日松弛(Lagrangian Relaxation mixed with Interleaved Subgraident Optimization, LR&ISO)算法，設(shè)計(jì)了異步次梯度優(yōu)化使得每次迭代僅最優(yōu)求解一個(gè)批級(jí)子問(wèn)題，以加速LR的求解過(guò)程和改善解的質(zhì)量。本文擴(kuò)展了文獻(xiàn)[14]所提出的LR算法理論，解決了其求解大規(guī)模問(wèn)題效率較低的問(wèn)題。

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

1.1 問(wèn)題設(shè)置

1.2 IP模型

(1)集合

j表示工件集，j=1,…,n；

s表示階段集，s=1,…,S；

f表示批集，f=1,…,F；

k表示時(shí)間集，k=1,…,K。

(2)參數(shù)

Ms表示階段s的并行機(jī)數(shù)；

Pjs表示工件j在階段s的加工時(shí)間；

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

Rj表示工件j的動(dòng)態(tài)到達(dá)時(shí)間；

hfq表示批f內(nèi)的第q個(gè)工件，q=1,…,nf；

Ts,s+1表示階段s到階段s+1的傳送時(shí)間；

STjs表示工件j在階段s的調(diào)整時(shí)間，令l為批處理機(jī)所處階段，則當(dāng)s=l且j=hf1時(shí)，其值大于0，否則都為0。

(3)決策變量

yjsk表示若時(shí)刻k工件j正占用階段s的機(jī)器，則其值為1，否則為0；

cjs表示工件j在階段s的完工時(shí)間；

bjs表示工件j在階段s的開(kāi)工時(shí)間。

基于文獻(xiàn)[14]，建立整數(shù)規(guī)劃(IP)模型：

(1)

(2)

bj1≥Rj,j=1,…,n;

(3)

bjs≥bj,s-1+Pj,s-1+Ts-1,s,j=1,…,n,

s=2,…,S;

(4)

bhfq,l+Phfq,l=bhf,q+1,l,f=1,…,F,

q=1,…,nf;

(5)

bjs-STjs≤k+K(1-yjsk),j=1,…,n,

s=1,…,S,k=1,…,K;

(6)

cjs=bjs+Pjs-1,j=1,…,n,s=1,…,S;

(7)

yjsk{0,1},j=1,…,n,s=1,…,S,

k=1,…,K。

(8)

其中：目標(biāo)(1)旨在最小化所有工件的TWC值；約束(2)說(shuō)明了在任一階段任一時(shí)刻正在加工的工件總數(shù)不能超過(guò)該時(shí)刻可利用的機(jī)器數(shù)；約束(3)確保了每個(gè)工件在其到達(dá)生產(chǎn)系統(tǒng)之前不能開(kāi)始在第一階段的加工；約束(4)表示了一個(gè)工件的相鄰兩工序之間的加工優(yōu)先級(jí)關(guān)系；約束(5)表示了在批處理階段，同一批內(nèi)，前一個(gè)工件加工完成后下一工件立刻開(kāi)始加工，保證了同一批內(nèi)工件加工的連續(xù)性；約束(6)說(shuō)明了工件占用機(jī)器的時(shí)間約束；約束(7)表示了同一工件開(kāi)工時(shí)間和完工時(shí)間的關(guān)系；約束(8)說(shuō)明了決策變量yjsk是0-1變量。

上述模型雖然與文獻(xiàn)[7]相似，但兩者有不同之處，體現(xiàn)在：①本文研究的是一般的含批處理機(jī)和離散機(jī)的多階段FFSP，因此考慮了這類問(wèn)題的關(guān)鍵約束，忽略了在特定生產(chǎn)環(huán)境下的某些具體技術(shù)要求，而文獻(xiàn)[7]考慮到連鑄—熱軋間不同的銜接方式，具體研究了煉鋼—連鑄—熱軋的作業(yè)車間問(wèn)題；②考慮到串行批處理機(jī)要求同一批內(nèi)的工件按照一定的順序連續(xù)地在該階段的一臺(tái)機(jī)器上進(jìn)行加工，因此，將其表示為約束的形式，而文獻(xiàn)[7]則通過(guò)目標(biāo)函數(shù)的一個(gè)懲罰項(xiàng)來(lái)體現(xiàn)該要求；③考慮到工件到達(dá)的動(dòng)態(tài)特性，本文引入了工件釋放時(shí)間約束，而文獻(xiàn)[7]假定所有工件都在時(shí)刻1到達(dá)生產(chǎn)系統(tǒng)；④本文模型旨在降低生產(chǎn)費(fèi)用和在制品庫(kù)存及提高準(zhǔn)時(shí)傳送，而文獻(xiàn)[7]針對(duì)鋼鐵企業(yè)的一體化生產(chǎn)過(guò)程考慮了更多因素。

2 LR&ISO算法

傳統(tǒng)的LR算法要求松弛耦合工件的約束從而將松弛問(wèn)題分解為每個(gè)針對(duì)一個(gè)工件的工件級(jí)子問(wèn)題[7]。1.2節(jié)中約束(2)和約束(5)均關(guān)聯(lián)了不同工件，因此，若使用傳統(tǒng)LR算法則需松弛這兩組約束，而松弛的約束越多，收斂性越差，下界更松[14]，故而根據(jù)模型的批處理生產(chǎn)特點(diǎn)，本文基于批分解方式改進(jìn)LR。

2.1 拉格朗日松弛

引入非負(fù)拉格朗日乘子{γsk}將約束(2)松弛到目標(biāo)函數(shù)中，構(gòu)成拉格朗日松弛問(wèn)題：

s.t.

(3)～(8)；

γsk≥0,s=1,…,S,k=1,…,K。

(9)

拉格朗日代理對(duì)偶問(wèn)題定義為

s.t.

(3)～(9)。

上述LR問(wèn)題的第二項(xiàng)與決策變量無(wú)關(guān)，因此計(jì)算時(shí)先將其忽略，而第一項(xiàng)是對(duì)所有工件求和，即對(duì)所有批求和，因此，可進(jìn)一步將第一項(xiàng)表示為所有批內(nèi)工序之和，即

給定γ，可將LR問(wèn)題分解為F個(gè)批級(jí)子問(wèn)題：

s.t.

(3)～(8)。

由此，可將LR問(wèn)題重新表述為

s.t.

(3)～(9)。

2.2 子問(wèn)題的異步求解

待求解的批級(jí)子問(wèn)題由nf個(gè)工件的多個(gè)工序構(gòu)成，每個(gè)工序可能有多個(gè)緊前工序或緊后工序，故單一方向時(shí)間進(jìn)度的動(dòng)態(tài)規(guī)劃(如文獻(xiàn)[7])不再適用，因此混合兩種方向設(shè)計(jì)求解這類子問(wèn)題的動(dòng)態(tài)規(guī)劃。給定某批L和一組{γsk}，推廣文獻(xiàn)[14]的研究，首先將批L內(nèi)的所有工件的加工工序從階段1、階段2...直到階段S依次按照它們?cè)谂械捻樞蜻M(jìn)行排列。因此，每個(gè)工序x可能有多個(gè)緊前工序或緊后工序。然后，將由上述工序構(gòu)成的優(yōu)先級(jí)圖轉(zhuǎn)換成樹(shù)結(jié)構(gòu)：找到優(yōu)先級(jí)圖中最長(zhǎng)有向路徑，以其為主線，將所有與其相連的其他分支移到樹(shù)的右側(cè)。最后，根據(jù)形成的樹(shù)結(jié)構(gòu)，從后向前利用動(dòng)態(tài)規(guī)劃進(jìn)行求解。

令x表示工序標(biāo)號(hào)，X為批L內(nèi)的工序總數(shù)，可知X=nL·S。將LRBf表示為關(guān)于工序的表達(dá)式，即

(11)

式中：

(12)

(13)

其中jx和sx分別表示工序x對(duì)應(yīng)的工件和階段。

令z1，z2，z3表示樹(shù)結(jié)構(gòu)中工序x的孩子，z1表示工件jx在緊后階段sz1的工序，其集合表示為Ax；z2表示與jx屬于同一批的且在批處理階段的工序x的緊后工序；z3表示工件jx在緊前階段sz3的工序，其集合表示為Bx。

因此，每個(gè)工序x的累計(jì)費(fèi)用可表示為

(14)

計(jì)算得到最優(yōu)費(fèi)用后，再向前追蹤得到對(duì)應(yīng)批L的子問(wèn)題的最優(yōu)解。

對(duì)于分解后的F個(gè)子問(wèn)題，每次迭代僅對(duì)一批L(L=1,…,F)執(zhí)行上述過(guò)程，而對(duì)于其他批，則將子問(wèn)題的解設(shè)為前一次迭代得到的值。因此，迭代F次，所有子問(wèn)題才最優(yōu)求解一遍。

2.3 異步次梯度優(yōu)化

常規(guī)的次梯度算法要求每次迭代最優(yōu)求解所有批級(jí)子問(wèn)題[7,14]，因此當(dāng)問(wèn)題復(fù)雜時(shí)，求解時(shí)間會(huì)較長(zhǎng)，因此設(shè)計(jì)異步次梯度優(yōu)化方法，每次迭代僅最優(yōu)求解一個(gè)批級(jí)子問(wèn)題，從而獲得一個(gè)合理的異步次梯度方向。

異步次梯度定義為

(15)

算法執(zhí)行過(guò)程中，首先，對(duì)一些參數(shù)進(jìn)行初始化處理：令γ=0，通過(guò)最小化所有子問(wèn)題得到初始的{cjs}的值，根據(jù)式(16)和式(17)更新乘子。然后，從第一次迭代開(kāi)始，依次在每次迭代僅最優(yōu)求解一個(gè)子問(wèn)題，計(jì)算代理對(duì)偶值和異步次梯度，直至達(dá)到停止條件，算法停止。

(16)

(17)

其中：η為小于1的正數(shù)，β為步長(zhǎng)，LR*由得到的最好可行目標(biāo)值來(lái)估計(jì)，LDq為當(dāng)前迭代的代理對(duì)偶目標(biāo)值。

2.4 可行解構(gòu)造

為得到原問(wèn)題的可行解，對(duì)批處理階段之前、批處理階段、批處理階段之后的工件加工，根據(jù)松弛問(wèn)題的解和先前階段的完工時(shí)間調(diào)整工件(或批)在該階段的可能開(kāi)工時(shí)間，按該時(shí)間的增序構(gòu)造列表，然后根據(jù)該列表，依次將各工件(或批)分配到相應(yīng)階段可利用的機(jī)器上。

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

3.1 算法參數(shù)

文獻(xiàn)[7]使用的常規(guī)的基于工件解耦和次梯度優(yōu)化的LR算法(LR0)中，分解后的子問(wèn)題僅包含單個(gè)工件的多個(gè)工序的優(yōu)先級(jí)約束，即每個(gè)工序至多有一個(gè)緊前或緊后工序，采用前向或后向動(dòng)態(tài)規(guī)劃均可求解，待求解的子問(wèn)題數(shù)為n，拉格朗日乘子數(shù)為S×K+n，求解子問(wèn)題的動(dòng)態(tài)規(guī)劃的復(fù)雜度為O(2(S-1)K)；文獻(xiàn)[14]提出的基于批解耦和次梯度優(yōu)化的LR算法(LR1)中，子問(wèn)題數(shù)為F，所設(shè)計(jì)的LR&ISO算法(LR2)的子問(wèn)題數(shù)為1，兩者的乘子數(shù)均為S×K，動(dòng)態(tài)規(guī)劃的復(fù)雜度均為O(2(nf×S-1)K)。雖然LR1和LR2求解子問(wèn)題的算法復(fù)雜度相同，但LR1每次迭代要優(yōu)化的子問(wèn)題數(shù)較多，導(dǎo)致消耗的總運(yùn)行時(shí)間較長(zhǎng)，而LR2每次迭代僅需求解一個(gè)子問(wèn)題，因此多次迭代累加所節(jié)省的計(jì)算時(shí)間較為可觀，同時(shí)由于它是近似求解松弛問(wèn)題，故需要相應(yīng)設(shè)計(jì)乘子更新策略來(lái)保證算法的收斂性。

考慮到LR0松弛的約束多會(huì)導(dǎo)致下界較松，且待求解的工件子問(wèn)題也較多，因此本實(shí)驗(yàn)僅測(cè)試了LR1和LR2。當(dāng)?shù)鷶?shù)達(dá)到500或運(yùn)行時(shí)間達(dá)到900 s時(shí)，程序停止。如果對(duì)偶間隙小于很小的數(shù)(0.5%)時(shí)，程序也停止。為公平比較這兩種算法，以LR1的運(yùn)行時(shí)間為停止條件運(yùn)行LR2。

因?yàn)榇韺?duì)偶目標(biāo)值不是通過(guò)最優(yōu)求解松弛問(wèn)題得到，所以它不能作為最優(yōu)費(fèi)用的下界，因此，當(dāng)?shù)Y(jié)束后，通過(guò)最優(yōu)化所有子問(wèn)題得到真正的下界，從而計(jì)算出真正的對(duì)偶間隙(表1中列LR2)。計(jì)算結(jié)果以(代理)對(duì)偶間隙(%)、迭代數(shù)和運(yùn)行時(shí)間(s)來(lái)衡量，其中對(duì)偶間隙定義為歷史上得到的最好上界與最好下界之間的相對(duì)差，并轉(zhuǎn)化成百分比的形式；代理對(duì)偶間隙(表1中列LR′)定義為歷史上得到的最好上界與當(dāng)前代理對(duì)偶目標(biāo)值之間的相對(duì)差，并轉(zhuǎn)化成百分比的形式。利用C語(yǔ)言對(duì)兩種算法進(jìn)行編程，在Windows 7操作系統(tǒng)(64位)的計(jì)算機(jī)(Intel Core i5-5200U 2.20 GHz 2.20 GHz)上運(yùn)行。

3.2 實(shí)驗(yàn)一

利用文獻(xiàn)[17]的寶鋼實(shí)際生產(chǎn)數(shù)據(jù)產(chǎn)生實(shí)驗(yàn)所用各種數(shù)據(jù)。爐次(工件)數(shù)設(shè)為12，加工階段為3(煉鋼，連鑄，熱軋)，澆次(批)數(shù)為{3,4,6}，每階段的機(jī)器數(shù)取自{3,4,5}，計(jì)劃時(shí)間范圍K設(shè)為8小時(shí)(480 min)。wi、Pij、Ri、Tj,j+1、STij分別滿足[10,15]、[30,50]、[1,10]、[20,30]、[15,25]之間的均勻分布。共測(cè)試了9種規(guī)模，每種規(guī)模隨機(jī)產(chǎn)生10個(gè)實(shí)例，因此，本實(shí)驗(yàn)測(cè)試了90個(gè)問(wèn)題實(shí)例，表中的每個(gè)值(除最后一行)為同一規(guī)模的10個(gè)實(shí)例的平均值。

表1列出了測(cè)試結(jié)果。從表中結(jié)果可知：

(1)由LR1和LR2得到的平均對(duì)偶間隙分別為0.39%和0.48%，均小于0.5%，因此兩種算法求解小規(guī)模實(shí)際問(wèn)題時(shí)都能得到非常接近最優(yōu)解的近優(yōu)解。在LR2中，平均代理對(duì)偶間隙為0.47%和真正對(duì)偶間隙相差0.01%，兩者相差不大。

(2)LR1和LR2所使用的平均運(yùn)行時(shí)間分別為8.79和6.39秒，迭代數(shù)分別為185.62和608.47，因此，所提出的LR2在求解速度方面明顯優(yōu)于LR1，即在較短的時(shí)間內(nèi)得到了高質(zhì)量的近優(yōu)解。

表1 n=12的測(cè)試結(jié)果

以上述問(wèn)題12×3×3×3的一個(gè)實(shí)例為例，各工件的加工時(shí)間、釋放時(shí)間、權(quán)重、調(diào)整時(shí)間如表2所示，相鄰兩階段的傳送時(shí)間分別為22和23，已知在批處理階段各工件的組批順序(10→5→4→1，9→7→2→11，12→3→6→8)，運(yùn)行LR&ISO算法，可得到如圖1所示的甘特圖，最小總加權(quán)完成時(shí)間為37224，對(duì)偶間隙為0.70%。

表2 各工件的參數(shù)設(shè)置

3.3 實(shí)驗(yàn)二

本實(shí)驗(yàn)測(cè)試了工件數(shù)為{24,36,48,60,84}的實(shí)例，數(shù)據(jù)隨機(jī)產(chǎn)生如下：

(1)S∈{3,4}，Ms∈{3,4,5}，nf∈{2,3,4}；

(2)工件j的權(quán)重wj和加工時(shí)間Pjs滿足[1,10]的均勻分布，Rj滿足[1,5]的均勻分布；

(3)Ts,s+1和STjs分別滿足[4,6]和[3,5]之間的均勻分布；

(4)計(jì)劃時(shí)間范圍K設(shè)置為所有工件加工時(shí)間之和。

因此，本實(shí)驗(yàn)共測(cè)試了5×2×3×3×10=900個(gè)實(shí)例，測(cè)試結(jié)果如表3～表7所示。

從表中結(jié)果可得到以下結(jié)論：

(1)對(duì)n=24,36,48,60,84的情況，由LR1得到的平均對(duì)偶間隙分別為1.41%，2.03%，2.69%，4.47%，13.16%；由LR2得到的分別為1.51%，1.62%，1.85%，2.16%，3.49%。除了n=24時(shí)LR2表現(xiàn)略差于LR1(相差0.1%)，對(duì)于其他規(guī)模問(wèn)題，LR2均明顯優(yōu)于LR1，而且在解的質(zhì)量方面的優(yōu)勢(shì)隨問(wèn)題規(guī)模的增大而增加。因?yàn)閷?duì)偶間隙是由啟發(fā)式解和下界之間的相對(duì)差計(jì)算得到，所以對(duì)偶間隙小于3%的解非常接近最優(yōu)解，因此，總體來(lái)看，由LR2可得到質(zhì)量更佳的近優(yōu)解。

(2)在相同的運(yùn)行時(shí)間內(nèi)，對(duì)于不同規(guī)模問(wèn)題，LR2執(zhí)行的迭代數(shù)分別為L(zhǎng)R1的7.32，12.15，17.33，20.83，27.32倍，因此，隨著問(wèn)題規(guī)模的增大，所設(shè)計(jì)的LR2迭代次數(shù)要多的多，這是由于LR1每次迭代最優(yōu)求解所有批級(jí)子問(wèn)題使得每次迭代運(yùn)行時(shí)間長(zhǎng)從而導(dǎo)致迭代次數(shù)少。

(3)對(duì)不同規(guī)模問(wèn)題，由LR2得到的代理對(duì)偶間隙分別為1.47%，1.55%，1.71%，1.92%，2.75%，與真正對(duì)偶間隙分別相差0.04%，0.07%，0.14%，0.24%，0.74%，兩者差距隨問(wèn)題規(guī)模的增大呈遞增趨勢(shì)，但總體來(lái)看，相差不大。

表3 n=24的測(cè)試結(jié)果

續(xù)表3

表4 n=36的測(cè)試結(jié)果

表5 n=48的測(cè)試結(jié)果

續(xù)表5

表6 n=60的測(cè)試結(jié)果

表7 n=84的測(cè)試結(jié)果

續(xù)表7

4 結(jié)束語(yǔ)

本文提出了LR&ISO混合算法求解多階段含離散機(jī)和批處理機(jī)的FFSP?；谧訂?wèn)題異步求解策略，該算法每次迭代僅最優(yōu)求解一個(gè)批級(jí)子問(wèn)題，使得迭代時(shí)間有大幅度縮短，這對(duì)實(shí)際生產(chǎn)尤為重要；為得到合理的乘子更新方向，利用異步次梯度優(yōu)化計(jì)算下次迭代的乘子。通過(guò)對(duì)實(shí)際生產(chǎn)數(shù)據(jù)和大量隨機(jī)數(shù)據(jù)的實(shí)驗(yàn)測(cè)試，驗(yàn)證了引入異步求解策略的LR&ISO算法不但解的質(zhì)量較好，而且求解速度較快，尤其是求解大規(guī)模問(wèn)題時(shí)，它在各方面的表現(xiàn)均明顯優(yōu)于基于批解耦和次梯度優(yōu)化的LR算法。

未來(lái)可將LR&ISO算法應(yīng)用于具有其他生產(chǎn)特征的FFSP，由于該算法適合于求解“可分離”的數(shù)學(xué)模型，且求解過(guò)程中某些參數(shù)如步長(zhǎng)等要根據(jù)具體問(wèn)題進(jìn)行調(diào)節(jié)，因此，對(duì)于其他類似問(wèn)題，還需根據(jù)所研究問(wèn)題具體設(shè)計(jì)該方法的應(yīng)用方式，以獲得更佳的近優(yōu)解。