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

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

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

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

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

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

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

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

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

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

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

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

1.1問題描述

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

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

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

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

1.2模型構(gòu)造

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

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

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

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

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

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

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

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

2　拉格朗日下界求解

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

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

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

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

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

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

以及對偶問題（LD）:

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

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

由

得到

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

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

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

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

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

2.2拉格朗日松弛

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

拉格朗日乘子非負約束:

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

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

其中

2.3拉格朗日對偶

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

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

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

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

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

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

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

式中:gik表示次梯度。

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

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

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

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

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

迭代終止原則為:

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

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

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

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

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

3.1可行解生成問題分析

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

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

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

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

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

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

符號說明:MAX為一個極大數(shù)；決策變量Si，k，t表示階段i中機器t的第k個任務(wù)的開始加工時間；決策變量Zi，j，k，t為0-1變量，如果爐次j在階段i的機器t上位于時間點k進行處理，則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ù):最小化爐次在機器上的處理開始時間，即

機器及爐次分配約束:每個爐次在任一階段必須且只能分配到一個機器的一個時間點k，即

最多有一個爐次被分配到任一機器t的一個時間點，即

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

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

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

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

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

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

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

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

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

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

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

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

步驟6 輸出機器指派變量值。

4　算例分析

4.1實驗數(shù)據(jù)

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

雖然本文算法能求解不同階段有不同機器數(shù)的調(diào)度問題，但為了簡化實驗數(shù)據(jù)，這里假設(shè)每階段的機器數(shù)均為2（3個階段共6臺機器），并隨機產(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。

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

表1　實驗數(shù)據(jù)Table 1 Experimental data

4.2解的有效性分析

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

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

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

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

4.3拉格朗日下界分析

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

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

5　結(jié)語

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

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

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

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