基于拉格朗日下界求解的煉鋼-連鑄生產(chǎn)調(diào)度方法

韓大勇，唐秋華，張利平，張啟敏，2

（1.武漢科技大學(xué)機(jī)械自動(dòng)化學(xué)院，湖北武漢，430081；2.武漢鋼鐵集團(tuán)鄂城鋼鐵有限責(zé)任公司，湖北鄂州，436002）

基于拉格朗日下界求解的煉鋼-連鑄生產(chǎn)調(diào)度方法

韓大勇1，唐秋華1，張利平1，張啟敏1，2

（1.武漢科技大學(xué)機(jī)械自動(dòng)化學(xué)院，湖北武漢，430081；2.武漢鋼鐵集團(tuán)鄂城鋼鐵有限責(zé)任公司，湖北鄂州，436002）

為提高煉鋼-連鑄生產(chǎn)效率，以加權(quán)總完工時(shí)間、作業(yè)等待懲罰總和最小化為目標(biāo)，基于時(shí)間索引建立數(shù)學(xué)規(guī)劃模型。在證明原問題、松弛問題、對(duì)偶問題三者最優(yōu)解關(guān)系基礎(chǔ)上，將機(jī)器容量約束松弛到目標(biāo)函數(shù)中，運(yùn)用次梯度算法求原問題下界，得到各爐次的開始時(shí)間序列。為消除松弛解中的有向環(huán)，采用融入啟發(fā)式規(guī)則的列表調(diào)度，按照機(jī)器可用性優(yōu)先原則，將爐次均衡地指派到各個(gè)加工機(jī)器上。利用GAMS/Cplex軟件對(duì)18個(gè)調(diào)度算例進(jìn)行測(cè)試運(yùn)算，結(jié)果表明以較少的計(jì)算代價(jià)可以得到令人滿意的近優(yōu)解，因此本文提出的基于拉格朗日下界求解的方法對(duì)煉鋼-連鑄生產(chǎn)調(diào)度問題是可行的和有效的。

煉鋼-連鑄；生產(chǎn)調(diào)度；拉格朗日松弛算法；對(duì)偶問題；次梯度方法；啟發(fā)式規(guī)則

鋼鐵生產(chǎn)系統(tǒng)涉及因素多、工序復(fù)雜，而煉鋼-連鑄過程是其中的關(guān)鍵環(huán)節(jié)之一。該生產(chǎn)過程包括一組有序的作業(yè)，每一個(gè)作業(yè)都需要按照一定的操作順序經(jīng)歷三個(gè)主要生產(chǎn)階段，即煉鋼、精煉和連鑄，并且每個(gè)作業(yè)都有規(guī)定的操作時(shí)間和優(yōu)先級(jí)。從生產(chǎn)管理的角度來看，煉鋼-連鑄階段的主要特點(diǎn)為:在生產(chǎn)過程中鋼水需要保持在一定溫度以上；在連鑄階段必須按澆次進(jìn)行成批連續(xù)加工；需要考慮工件的運(yùn)輸時(shí)間、連鑄和熱軋工序之間的緊密銜接。考慮上述特點(diǎn)，可把煉鋼-連鑄生產(chǎn)調(diào)度視為具有工件（即爐次）駐留時(shí)間受限、最后階段成批連續(xù)加工（即連澆連鑄）、準(zhǔn)時(shí)完工等特殊要求的混合流水車間調(diào)度問題。

圍繞煉鋼-連鑄生產(chǎn)調(diào)度問題，已有研究主要分為三大類:智能算法、啟發(fā)式算法、基于數(shù)學(xué)規(guī)劃的精確算法和近似算法。Atighehchian等［1］通過蟻群算法進(jìn)行爐次指派和排序，形成粗調(diào)度方案，再利用非線性規(guī)劃求解算法消除粗調(diào)度中的設(shè)備沖突，形成可行調(diào)度方案。該方法計(jì)算效率較高，可面向?qū)嶋H應(yīng)用，但當(dāng)?shù)谝浑A段產(chǎn)生的粗調(diào)度不夠理想時(shí)，第二階段的優(yōu)化空間就有限。劉光航等［2］提出一個(gè)基于混合整數(shù)規(guī)劃模型的設(shè)備沖突解消啟發(fā)式方法，利用最優(yōu)線性規(guī)劃來求解。Tang等［3-4］采用以拉格朗日松弛法為基礎(chǔ)的近似算法求解煉鋼-連鑄生產(chǎn)調(diào)度整數(shù)規(guī)劃模型，該方法通過對(duì)時(shí)間變量均勻離散化來建立近似模型，提高了求解效率。

根據(jù)計(jì)算復(fù)雜性理論，大多數(shù)調(diào)度問題都屬于NP難問題，而煉鋼-連鑄調(diào)度問題更是一種特殊的混合流水車間調(diào)度問題，使用精確的求解算法和全局優(yōu)化算法（如分支定界法）在多項(xiàng)式時(shí)間范圍內(nèi)很難求得最優(yōu)解。相反，研究近似算法或針對(duì)具體問題的特殊性調(diào)度方案更具有現(xiàn)實(shí)意義。事實(shí)上，很多調(diào)度問題存在特殊的數(shù)學(xué)結(jié)構(gòu)，若能有效利用，可極大降低求解的計(jì)算復(fù)雜度。拉格朗日松弛算法針對(duì)一些具有可分解性的特殊結(jié)構(gòu)，通過對(duì)難約束松弛以及對(duì)松弛問題分解，將原問題轉(zhuǎn)化為較易處理的子問題或局部問題。基于拉格朗日松弛原理，Tanaka等［5］提出一種分支定界算法求解并行機(jī)調(diào)度問題，每個(gè)分支的界便是由拉格朗日松弛法生成的下界解。Mellouli等［6］設(shè)計(jì)一種列生成（column generation）方法，用于解決帶有完工時(shí)間總加權(quán)和的并行機(jī)調(diào)度問題。Chang等［7］融合拉格朗日松弛和網(wǎng)絡(luò)流方法求解帶有交貨期的流水車間調(diào)度問題，即首先松弛機(jī)器能力約束，然后利用網(wǎng)絡(luò)流求解松弛問題，最后利用優(yōu)先因子法構(gòu)造了一個(gè)生成可行解的啟發(fā)式方法。Nishi等［8］采用切片生成（cut generation）的拉格朗日松弛法求解帶有總權(quán)重拖期的混合流水車間調(diào)度問題，所得拉格朗日下界有很大改善。在現(xiàn)有生產(chǎn)調(diào)度優(yōu)化中求解拉格朗日對(duì)偶問題主要采用次梯度算法，但該算法本身有許多不足，主要包括收斂條件過于嚴(yán)格和求解效率低。針對(duì)求解效率低的不足，研究人員已提出了多種改進(jìn)方法，如序列求解［9］、對(duì)松弛策略進(jìn)行調(diào)整［10］、引入神經(jīng)網(wǎng)絡(luò)算法［11］等；針對(duì)收斂條件過于嚴(yán)格的問題，目前主要解決辦法是采用最大迭代次數(shù)或最大運(yùn)行時(shí)間作為終止條件。

用格朗日松弛算法解決調(diào)度問題主要有3個(gè)步驟:構(gòu)造拉格朗日算法模型并進(jìn)行解耦，更新拉格朗日乘因子，構(gòu)造可行調(diào)度方案。針對(duì)煉鋼-連鑄生產(chǎn)調(diào)度問題，在已有拉格朗日松弛問題求解方法的基礎(chǔ)上，本文擬著重進(jìn)行以下兩方面的工作:①進(jìn)一步剖析次梯度算法，研究在拉格朗日子問題求解時(shí)影響結(jié)果的關(guān)鍵性因素——次梯度的迭代策略；②基于拉格朗日松弛方法所求得的原問題解的下界，構(gòu)造出較優(yōu)的可行解生成模型，并用啟發(fā)式方法完成求解。

1　煉鋼-連鑄生產(chǎn)調(diào)度模型

1.1問題描述

煉鋼-連鑄生產(chǎn)調(diào)度主要涉及煉鋼、精煉和連鑄三個(gè)階段，如圖1所示。煉鋼階段接受來自高爐的鐵水，通過轉(zhuǎn)爐或電弧爐將冶煉好的鐵水或廢鋼轉(zhuǎn)換為鋼水；煉鋼結(jié)束后將鋼水注入鋼包，并轉(zhuǎn)運(yùn)到精煉設(shè)備中進(jìn)一步調(diào)整鋼水的溫度和成分；精煉后的鋼水被運(yùn)送到指定的連鑄機(jī)，連澆連鑄后形成板坯。在此過程中，運(yùn)送鋼水的每個(gè)鋼包被稱為一個(gè)爐次或“工件”，是煉鋼-連鑄的最小生產(chǎn)單元；在同一臺(tái)連鑄機(jī)上連續(xù)澆鑄的爐次集合被稱為一個(gè)澆次，是煉鋼-連鑄的最大生產(chǎn)單元。每個(gè)爐次需按照上述工藝順序依次經(jīng)過三個(gè)階段，每個(gè)階段可能存在一臺(tái)或多臺(tái)并行的生產(chǎn)設(shè)備。

圖1　煉鋼-連鑄生產(chǎn)工藝流程Fig.1 Process flow of steelmaking-continuous casting production

假定:①各爐次在每個(gè)階段的處理時(shí)間已知；②在調(diào)度開始時(shí)所有的機(jī)器均為可用狀態(tài)；③同一階段每臺(tái)機(jī)器性能相同，且不考慮因機(jī)器故障所引起的生產(chǎn)中斷或停線。

因此，煉鋼-連鑄生產(chǎn)調(diào)度可以描述為:爐次j沿著指定的工藝路線經(jīng)過i個(gè)階段，每個(gè)階段具有u臺(tái)相同機(jī)器（u≥1），且至少有一個(gè)階段的機(jī)器數(shù)大于1；在最后一個(gè)階段以澆次為單位連續(xù)作業(yè)。

1.2模型構(gòu)造

模型中的符號(hào)說明:j表示爐次，j=1，2，…，n；l表示澆次，l=1，2，…，B；i表示加工階段，i=1，2，…，s；k表示作業(yè)的時(shí)間點(diǎn)，k=1，2，…，K。

已知參量:bl表示澆次l中的作業(yè)總數(shù)；mi表示各階段機(jī)器數(shù)量；Pij表示作業(yè)j在i階段的處理時(shí)間；Sij表示作業(yè)j在i階段中的機(jī)器上處理前的機(jī)器準(zhǔn)備時(shí)間；wj表示作業(yè)j的權(quán)重；rij表示作業(yè)j在i階段完成后的等待時(shí)間的懲罰系數(shù)；alf表示澆次l中的第f個(gè)作業(yè)，f=1，2，…，bl。

決策變量:Cij（連續(xù)變量），為作業(yè)j在階段i處理的完成時(shí)間；δijk（0-1變量），如果爐次j在時(shí)間點(diǎn)k時(shí)位于階段i進(jìn)行處理，則δijk=1，否則δijk=0。

目標(biāo)函數(shù)（包含兩部分）:第一部分是總加權(quán)完成時(shí)間，以控制生產(chǎn)效率；第二部分為總拖期或提前懲罰，以保證準(zhǔn)時(shí)交貨。

機(jī)器能力約束:同一時(shí)刻在i階段上加工的爐次總數(shù)不大于i階段上的機(jī)器數(shù)；同一爐次j必須在前一階段完成后才能進(jìn)入下一階段。

澆次連鑄工藝約束:在最后一個(gè)階段，同一澆次內(nèi)各爐次需按照事先給定的爐次順序連續(xù)無間斷地加工。

機(jī)器加工無中斷約束:如果爐次j被分配在事件點(diǎn)k加工，直到爐次j被加工完，機(jī)器才能停工。

聯(lián)立式（1）～式（7）即可形成煉鋼-連鑄生產(chǎn)調(diào)度數(shù)學(xué)模型。

2　拉格朗日下界求解

由前面的分析可知，以煉鋼-連鑄實(shí)際生產(chǎn)為基礎(chǔ)所構(gòu)造的混合整數(shù)規(guī)劃模型難以求解。為簡(jiǎn)化模型求解同時(shí)又要獲得最優(yōu)解，這里引入拉格朗日松弛算法。具體策略是:將模型中的難約束松弛為目標(biāo)函數(shù)的一部分，減少原問題約束條件，構(gòu)造其對(duì)偶問題并進(jìn)行求解。這里求得的解為原問題解的下界，利用拉格朗日松弛求取該下界的方法稱為拉格朗日下界求解。

2.1拉格朗日對(duì)偶解的較優(yōu)性分析

由于約束條件松弛，原問題的屬性被改變，解空間增大，所求拉格朗日松弛問題的最優(yōu)解不一定是原問題的最優(yōu)解，在原問題中甚至不一定可行。

為更好地接近原問題的最優(yōu)解，常用拉格朗日對(duì)偶問題的對(duì)偶解來代替拉格朗日松弛問題的解。以下利用對(duì)偶理論相關(guān)知識(shí)，對(duì)拉格朗日對(duì)偶問題的解的優(yōu)越性進(jìn)行論述和證明。

假定線性規(guī)劃問題（IP）的簡(jiǎn)化形式為:

可得到其對(duì)應(yīng)的松弛問題（LP）:

以及對(duì)偶問題（LD）:

引理 若混合整數(shù)線性規(guī)劃松弛問題存在可行解，則有ZLP≤ZLD≤ZIP。

證明:混合整數(shù)線性規(guī)劃問題的解集是有限的離散點(diǎn)的集合，記為Q=｛x|Bx≤d，x∈Z+｝，可驗(yàn)證凸包Con（Q）為凸集。

由

得到

若拉格朗日對(duì)偶問題的目標(biāo)值ZLD有界，則:

即ZLD=min｛CTx|Ax≤b，x∈Con（Q）｝。

所以有:ZLP≤ZLD≤ZIP。證畢。

上述邏輯關(guān)系還可進(jìn)一步用圖2表示。由此可以判斷，為找到與原問題解更為接近的解，可在拉格朗日松弛基礎(chǔ)上，進(jìn)一步進(jìn)行拉格朗日對(duì)偶轉(zhuǎn)化。

圖2　原問題解、松弛解與對(duì)偶解的關(guān)系Fig.2 Relationship between original solution，relaxation solution and dual solution

2.2拉格朗日松弛

在傳統(tǒng)松弛法框架下，可以充分利用問題結(jié)構(gòu)特征對(duì)不容易處理的約束引入拉格朗日乘子進(jìn)行松弛，使其在應(yīng)用時(shí)有很大的靈活性，能夠適應(yīng)復(fù)雜多變的約束類型。這里引入非負(fù)的拉格朗日乘子μ，將資源析取約束式（2）松弛到目標(biāo)函數(shù)，得到拉格朗日松弛問 題（LR）的目標(biāo)函數(shù)，如式（8）所示。

拉格朗日乘子非負(fù)約束:

聯(lián)立式（3）～式（6）、式（8）～式（9），共同形成拉格朗日松弛問題。

由式（8）及其所包含的變量和參數(shù)性質(zhì)不難看出，ZLR可以分解為含未知變量的部分ZLR1以及常量部分ZLR2，即

其中

2.3拉格朗日對(duì)偶

將拉格朗日松弛問題視作原問題，且其最優(yōu)化方向?yàn)樽钚』?，根?jù)對(duì)偶定理，其對(duì)偶問題則為最大化問題，相應(yīng)的目標(biāo)函數(shù)為:

到此為止，在拉格朗日松弛算法的架構(gòu)下，將原來的煉鋼-連鑄調(diào)度問題轉(zhuǎn)化成較易處理的對(duì)偶問題。通過數(shù)學(xué)結(jié)構(gòu)特征分析可知，在此模型中耦合了所有澆次的機(jī)器能力約束松弛。為使問題易于求解，松弛約束式（2），解除澆次之間的耦合關(guān)系。將松弛問題劃分成一組獨(dú)立的容易求解的澆次級(jí)子問題，每一個(gè)子問題對(duì)應(yīng)一個(gè)澆次。因而在求解時(shí)主要考慮的是單個(gè)澆次和獨(dú)立澆次內(nèi)的調(diào)度子問題。在各子問題間以及子問題與原問題間起協(xié)調(diào)作用的是拉格朗日乘子。

從式（10）可以看到，等式右邊包含兩部分，對(duì)于任一給定的拉格朗日乘子，第二項(xiàng)為常數(shù)，第一項(xiàng)是對(duì)所有澆次的求和。而且，式（3）～式（6）都正好對(duì)應(yīng)一個(gè)澆次內(nèi)的爐次約束，因此LD問題是可以被分解為澆次級(jí)子問題的。以第l個(gè)子問題為例:

于是，LD問題可轉(zhuǎn)化為:

2.4次梯度算法更新拉格朗日乘子

次梯度算法是求解對(duì)偶問題較為有效的方法，其與非線性規(guī)劃梯度下降的思想相同。拉格朗日對(duì)偶問題是希望松弛問題的下界盡可能大，于是可按照松弛下界的上升方向逐漸逼近對(duì)偶問題的最優(yōu)上界值。

由連續(xù)函數(shù)的性質(zhì)，可以推導(dǎo)并證明在其極點(diǎn)處的超平面方程，即

式中:gik表示次梯度。

采用次梯度算法更新拉格朗日乘子的基本思路是:對(duì)給定的拉格朗日乘子，分別計(jì)算出松弛解和次梯度的值，并判斷松弛解的最優(yōu)性，如果不滿足條件則以這個(gè)次梯度方向?yàn)樯仙较驅(qū)で笏沙诮馍辖纭４翁荻人惴ň唧w步驟如下:

步驟1 任意選擇一個(gè)初始拉格朗日乘子μ1，令h=1。

步驟2 對(duì)μh，計(jì)算其次梯度gh。若滿足迭代終止原則，則認(rèn)為獲得最優(yōu)解，停止迭代，否則按照下面的迭代法則更新拉格朗日乘子μh。

式中:αh為迭代的步長(zhǎng)；H為最大迭代次數(shù)。

式中:λ為調(diào)整系數(shù)，0＜λ＜2，一般根據(jù)經(jīng)驗(yàn)取值；L*為當(dāng)前所能得到的最好解；Lh為每次迭代之后的實(shí)際值。

迭代終止原則為:

（1）gh=0，這是理論上的最理想狀態(tài)。

（2）在實(shí)際問題中，還可以設(shè)置最大迭代次數(shù)H。

（3）對(duì)拉格朗日乘子和松弛解按變化率設(shè)置條件。在連續(xù)多次迭代中，如果拉格朗日乘子或松弛解的變化率ε小于給定的某一趨于0的值，可認(rèn)為取得最優(yōu)解。

針對(duì)不同的問題，根據(jù)計(jì)算的方便和條件特殊性等約束，可以選擇以上任意一種迭代終止條件，或者綜合運(yùn)用。本文選擇迭代終止原則（3），即在迭代過程中，當(dāng)LR實(shí)際值的變化率小于一個(gè)預(yù)先設(shè)定的較小的正整數(shù)ε時(shí)，就認(rèn)為近似取得最優(yōu)解。

3　基于拉格朗日下界的可行解生成方法

3.1可行解生成問題分析

在拉格朗日松弛算法框架下求解對(duì)偶問題，可獲得爐次的機(jī)器分配結(jié)果。然而，由于松弛了機(jī)器容量約束，導(dǎo)致不同爐次在同一臺(tái)設(shè)備上加工有可能沖突，即同一臺(tái)設(shè)備上的所有爐次加工順序之間可能會(huì)出現(xiàn)有向環(huán)。

例如，松弛解有可能出現(xiàn)如下情況:對(duì)于在第1階段的3個(gè)加工爐次（爐次1、2、3），其指派變量的解為爐次1、2和3安排在機(jī)器1上，順序變量的解為爐次1先于爐次2加工、爐次2先于爐次3加工和爐次3先于爐次1加工。此情形下的加工順序明顯出現(xiàn)矛盾。

上述問題被簡(jiǎn)稱為列表調(diào)度問題。為了消除有向環(huán)，可通過前一階段的順序變量確定所有爐次的加工順序；然后按照機(jī)器優(yōu)先可用性原則，將爐次均衡地指派到各個(gè)加工機(jī)器上，確定每個(gè)階段每個(gè)爐次的加工設(shè)備以及每爐次在各個(gè)階段的開始加工時(shí)間。

3.2基于混合整數(shù)線性規(guī)劃的可行解構(gòu)造模型

針對(duì)煉鋼-連鑄生產(chǎn)調(diào)度問題，大多數(shù)數(shù)學(xué)建模方法是采用大M法或析取規(guī)劃方法。其中，大M法采用一個(gè)足夠大的常數(shù)（通常是生產(chǎn)周期）來表示設(shè)備能力極限約束，即多個(gè)工件不能同時(shí)在一臺(tái)設(shè)備上加工。該方法簡(jiǎn)單易懂，但其數(shù)值大小直接影響求解過程的穩(wěn)定性，而且其松弛解的質(zhì)量較差?；谖鋈∫?guī)劃的數(shù)學(xué)建模方法［12］可避免上述數(shù)值計(jì)算問題，但對(duì)設(shè)備能力約束的表示較為復(fù)雜，同時(shí)也增加了求解的難度。

根據(jù)采用拉格朗日下界求解方法得到的順序變量，可構(gòu)建如下混合整數(shù)線性規(guī)劃模型，來解決列表調(diào)度問題。

符號(hào)說明:MAX為一個(gè)極大數(shù)；決策變量Si，k，t表示階段i中機(jī)器t的第k個(gè)任務(wù)的開始加工時(shí)間；決策變量Zi，j，k，t為0-1變量，如果爐次j在階段i的機(jī)器t上位于時(shí)間點(diǎn)k進(jìn)行處理，則Zi，j，k，t=1，否則Zi，j，k，t=0；yi，j，j′為0-1變量，如果在同一階段上作業(yè)j先于作業(yè)j′加工，則yi，j，j′=1，否則yi，j，j′=0。

目標(biāo)函數(shù):最小化爐次在機(jī)器上的處理開始時(shí)間，即

機(jī)器及爐次分配約束:每個(gè)爐次在任一階段必須且只能分配到一個(gè)機(jī)器的一個(gè)時(shí)間點(diǎn)k，即

最多有一個(gè)爐次被分配到任一機(jī)器t的一個(gè)時(shí)間點(diǎn)，即

當(dāng)前的時(shí)間點(diǎn)不能被分配，除非它前面的時(shí)間點(diǎn)已經(jīng)被分配，即

澆次內(nèi)約束:如果爐次j和j′事先安排為同一澆次內(nèi)的兩個(gè)爐次，那么兩爐次在最后階段必須分配在同一個(gè)機(jī)器上，即

加工連續(xù)性約束:如果爐次j被分配到機(jī)器t的時(shí)間點(diǎn)k，則機(jī)器t不能停工直到爐次j被加工完。由于緩沖器有緩沖能力，且存儲(chǔ)時(shí)間不確定，故以下式（24）和式（25）中的符號(hào)“≥”表示了該時(shí)間的不確定性。

唯一性約束:為消除有向環(huán)，同一階段各爐次的排序必須唯一，即

聯(lián)立式（19）～式（27）即可構(gòu)造一個(gè)簡(jiǎn)單的列表調(diào)度數(shù)學(xué)模型，該模型可采用GAMS/Cplex軟件進(jìn)行求解。

3.3可行解啟發(fā)式快速生成

對(duì)于小規(guī)模調(diào)度問題，采用上述方法可較容易地獲得最優(yōu)可行解，而針對(duì)大規(guī)模案例時(shí)，為了能快速獲得最優(yōu)解，本文提出一個(gè)融入列表調(diào)度思想的啟發(fā)式算法。在加工的第一階段，按照拉格朗日松弛問題解的升序得到一個(gè)初始爐次加工序列，基于最早結(jié)束優(yōu)先規(guī)則修正第二階段的解，同時(shí)進(jìn)行機(jī)器分配，依此類推，得到連鑄階段的爐次加工序列和機(jī)器分配。該算法的具體步驟如下:

步驟1 由拉格朗日松弛解可得到每個(gè)加工爐次在階段i上的開始時(shí)間sti，j，作為一個(gè)初始列表。

步驟2 依據(jù)初始列表，將所有元素按升序排列，確定每個(gè)階段i上的工作排序Ti。

步驟3 Ti（m）表示Ti中的第m個(gè)元素，令j=argj∈Ω｛sti，j=stTi（m），j｝，其中Ω表示作業(yè)集合，更新機(jī)器t的所有分配爐次集合，所分配爐次數(shù)加1。

步驟4 如果m≤n，轉(zhuǎn)至步驟3；否則，令i=i+1，轉(zhuǎn)至步驟5。

步驟5 如果i＜s，返回步驟2；否則，轉(zhuǎn)至步驟6。

步驟6 輸出機(jī)器指派變量值。

4　算例分析

4.1實(shí)驗(yàn)數(shù)據(jù)

利用GAMS 23.8/Cplex軟件對(duì)上述拉格朗日算法進(jìn)行編程，并在Intel（R）Core（TM）i3-2120 CPU@3.30 GHz主頻、4 GB內(nèi)存、Windows 7/32位操作系統(tǒng)環(huán)境下運(yùn)行。將最大迭代數(shù)50設(shè)為停止條件。針對(duì)每種問題規(guī)模隨機(jī)產(chǎn)生幾組不同數(shù)據(jù)，利用這些下界數(shù)據(jù)的平均性能來驗(yàn)證算法求解的有效性。

雖然本文算法能求解不同階段有不同機(jī)器數(shù)的調(diào)度問題，但為了簡(jiǎn)化實(shí)驗(yàn)數(shù)據(jù)，這里假設(shè)每階段的機(jī)器數(shù)均為2（3個(gè)階段共6臺(tái)機(jī)器），并隨機(jī)產(chǎn)生爐次總數(shù)s∈｛4，8，12，18，24，30，36，40，48｝、澆次總數(shù)bl∈｛2，3，4，5，6，8｝，工件權(quán)重設(shè)置相同且為1。

針對(duì)不同參數(shù)的組合隨機(jī)產(chǎn)生18個(gè)算例，如表1所示，表中同時(shí)列出經(jīng)過多次迭代后得到的拉格朗日下界。

表1　實(shí)驗(yàn)數(shù)據(jù)Table 1 Experimental data

4.2解的有效性分析

以包含三個(gè)澆次的簡(jiǎn)單算例（算例2）為代表，進(jìn)一步完成可行解的構(gòu)造，其中三個(gè)澆次｛1，2，3｝分別包含有爐次｛1，2｝，｛3｝，｛4｝。表2列出了每個(gè)爐次在三個(gè)階段的處理時(shí)間，各爐次的加權(quán)懲罰系數(shù)w均為1。在拉格朗日松弛問題的求解基礎(chǔ)上利用啟發(fā)式方法構(gòu)造可行解，得到可行方案的甘特圖，如圖3所示。

表2　各爐次在不同階段的操作時(shí)間Table 2 Operation times of all furnaces at different stages

圖3　可行方案的甘特圖Fig.3 Gantt chart of the feasible scheme

由GAMS23.8/Cplex程序運(yùn)行情況可知，該問題一共產(chǎn)生了141個(gè)離散變量、30個(gè)連續(xù)變量、3775個(gè)線性方程，通過10次迭次獲得最優(yōu)解（圖3）。該結(jié)果表明，利用拉格朗日啟發(fā)式算法可以獲得較好的解甚至最優(yōu)解。

4.3拉格朗日下界分析

從計(jì)算所得到的拉格朗日下界（見表1）來看，每個(gè)澆次內(nèi)預(yù)先設(shè)定的爐次分配對(duì)問題的下界有較大影響。如表1中的算例7和算例8，針對(duì)相同的爐次數(shù)（12）和機(jī)器數(shù)（6），算例7采取3澆次，算例8采用4澆次，結(jié)果得到的拉格朗日下界有很大區(qū)別，其中澆次數(shù)較小的案例所得下界值較優(yōu)。同時(shí)，算法中爐次數(shù)和澆次數(shù)等參數(shù)值較大時(shí)，會(huì)影響算法的收斂性，使得對(duì)偶問題很難收斂到最優(yōu)值。

另外，從程序的運(yùn)行時(shí)間和迭代次數(shù)來看，結(jié)合次梯度優(yōu)化的拉格朗日松弛算法在迭代前期收斂速度較快，但隨著迭代次數(shù)的增加，收斂速度會(huì)有所減緩。

5　結(jié)語

本文建立了煉鋼-連鑄生產(chǎn)調(diào)度的0-1整數(shù)規(guī)劃模型，求解時(shí)將非線性的目標(biāo)函數(shù)轉(zhuǎn)化成線性的，通過松弛資源析取約束來解除連續(xù)變量和整數(shù)變量之間的耦合關(guān)系，將松弛問題分解成兩個(gè)容易求解的子問題。在構(gòu)造問題的可行解時(shí)基于傳統(tǒng)的啟發(fā)式思想，建立新的混合整數(shù)線性規(guī)劃列表調(diào)度模型，并利用GAMS/Cplex軟件求解得到較優(yōu)解。進(jìn)一步的研究將重點(diǎn)考慮在更短時(shí)間內(nèi)取得更大規(guī)模問題的下界，以提高算法的求解效率。

［1］Atighehchian A，Bijari M，Tarkesh H.A novel hybrid algorithm for scheduling steel-making continuous casting production［J］.Computers and Operations Research，2009，36:2450-2461.

［2］劉光航，李鐵克.煉鋼-連鑄生產(chǎn)調(diào)度模型及啟發(fā)式算法［J］.系統(tǒng)工程，2002，20（6）:44-48.

［3］Tang Lixin，Luh P B，Liu Jiyin，et al.Steel-making process scheduling using Lagrangian relaxation［J］.International Journal of Production Research，2002，40（1）:55-70.

［4］Tang Lixin，Liu Jiyin，Rong Aiying，et al.A mathematical programming model for scheduling steelmaking-continuous casting production［J］.European Journal of Operational Research，2000，120: 423-435.

［5］Tanaka S，Araki M.A branch-and-bound algorithm with Lagrangian relaxation to minimize total tardiness on identical parallel machines［J］.International Journal of Production Economics，2008，113:446-458.

［6］Mellouli R，Kacem I，Sadfi C，et al.Lagrangian relaxation and column generation-based lower bounds for the Pm，hj1scheduling problem［J］. Applied Mathematics and Computation，2013，219: 10783-10805.

［7］Chang S-C，Liao D-Y，Hsieh F-S，et al.Flow shop scheduling by a Lagrangian relaxation and network flow approach［C］//Proceedings of the 29th IEEE Conference on Decision and Control.Honolulu，Hawail，1990:122-124.

［8］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:189-198.

［9］Chen Haoxun.A sequential Lagrangian relaxation approach to job shop scheduling［J］.控制理論與應(yīng)用，1995，12（6）:752-757.

［10］Chen Haoxun，Chu Chengbin，Proth J-M.An improvement of the Lagrangean relaxation approach for job shop scheduling:a dynamic programming method［J］.IEEE Transactions on Robotics and Automation，1998，14（5）:786-795.

［11］Luh P B，Zhao Xing，Wang Yajun，et al.Lagrangian relaxation neural networks for job shop scheduling［J］.IEEE Transactions on Robotics and Automation，2000，16（1）:78-88.

［12］Xuan Hua，Tang Lixin.Scheduling a hybrid flowshop with batch production at the last stage［J］. Computers and Operations Research，2007，34: 2718-2733.

［責(zé)任編輯 尚 晶］

Lagrangian lower bound solution based method for steelmaking-continuous casting production scheduling

Han Dayong1，Tang Qiuhua1，Zhang Liping1，Zhang Qimin1，2
（1.College of Machinery and Automation，Wuhan University of Science and Technology，Wuhan 430081，China；2.Echeng Iron and Steel Co.，Ltd.，Wuhan Iron and Steel Corporation，Ezhou 436002，China）

To improve the production efficiency of steelmaking-continuous casting，a mathematical programming model is established based on time index with the objective of minimizing the sum of weighted completion time and waiting punishment.with the relationship between the optimal solutions of original problem，relaxation problem and dual problem proved，the machine capacity constraints are relaxed to the objective function，and the sub-gradient method is employed to seek the lower bound of the original problem，then the start time sequence of all ladles is obtained.To eliminate the directional ring in the relaxation solution，a list scheduling method integrated with heuristic rules is used and all ladles are evenly assigned to the machines according to the priority principle of machine availability.Eighteen scheduling examples are calculated by GAMS/Cplex software.The results show that satisfactory near optimal solution can be achieved at less computing cost.So the proposed method based on Lagrangian lower bound solution is feasible and effective to solve the steelmaking-continuous casting production scheduling problem.

steelmaking-continuous casting；production scheduling；Lagrangian relaxation algorithm；dual problem；sub-gradient method；heuristic rule

TF087；TP29

A

1674-3644（2016）05-0353-08

2016-04-06

國(guó)家自然科學(xué)基金資助項(xiàng)目（51275366，51305311）；中國(guó)博士后科學(xué)基金資助項(xiàng)目（2013M542073）；高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金課題（博導(dǎo)類）（20134219110002）.

韓大勇（1990-），男，武漢科技大學(xué)碩士生.E-mail:1223408932@qq.com

唐秋華（1970-），女，武漢科技大學(xué)教授，博士生導(dǎo)師.E-mail:tangqiuhua@wust.edu.cn