基于拉格朗日下界求解的煉鋼-連鑄生產調度方法

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

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

基于拉格朗日下界求解的煉鋼-連鑄生產調度方法

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

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

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

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

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

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

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

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

1　煉鋼-連鑄生產調度模型

1.1問題描述

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

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

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

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

1.2模型構造

模型中的符號說明: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階段中的機器上處理前的機器準備時間；wj表示作業(yè)j的權重；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。

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

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

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

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

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

2　拉格朗日下界求解

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

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

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

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

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

可得到其對應的松弛問題（LP）:

以及對偶問題（LD）:

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

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

由

得到

若拉格朗日對偶問題的目標值ZLD有界，則:

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

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

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

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

2.2拉格朗日松弛

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

拉格朗日乘子非負約束:

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

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

其中

2.3拉格朗日對偶

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

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

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

于是，LD問題可轉化為:

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

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

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

式中:gik表示次梯度。

采用次梯度算法更新拉格朗日乘子的基本思路是:對給定的拉格朗日乘子，分別計算出松弛解和次梯度的值，并判斷松弛解的最優(yōu)性，如果不滿足條件則以這個次梯度方向為上升方向尋求松弛解上界。次梯度算法具體步驟如下:

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

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

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

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

迭代終止原則為:

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

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

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

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

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

3.1可行解生成問題分析

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

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

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

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

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

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

符號說明:MAX為一個極大數(shù)；決策變量Si，k，t表示階段i中機器t的第k個任務的開始加工時間；決策變量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。

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

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

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

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

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

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

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

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

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

對于小規(guī)模調度問題，采用上述方法可較容易地獲得最優(yōu)可行解，而針對大規(guī)模案例時，為了能快速獲得最優(yōu)解，本文提出一個融入列表調度思想的啟發(fā)式算法。在加工的第一階段，按照拉格朗日松弛問題解的升序得到一個初始爐次加工序列，基于最早結束優(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，轉至步驟3；否則，令i=i+1，轉至步驟5。

步驟5 如果i＜s，返回步驟2；否則，轉至步驟6。

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

4　算例分析

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

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

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

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

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

4.2解的有效性分析

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

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

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

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

4.3拉格朗日下界分析

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

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

5　結語

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

［責任編輯 尚 晶］

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

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

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

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