軋鋼切斷階段動態HFS調度模型和LR算法研究

軒 華， 曹 穎

(鄭州大學 管理工程系 河南 鄭州 450001)

0 引言

鋼管是軋鋼生產的一項重要產品，大量用作輸送流體的管道，如輸送石油、天然氣、煤氣、水及某些固體物料的管道等.迄今為止，針對鋼鐵業中的煉鋼過程或熱軋調度的研究比較多[1-2],而針對鋼管生產研究的文獻還比較少.文獻[3]利用了遺傳算法得到鋼管生產批量計劃的近似最優解，模型考慮了兩個目標：最小化剩余物和最小化所有的over-grade.文獻[4]從整個生產工藝的角度，對鋼管合同計劃進行了建模和求解，目標是最小化帶權重的合同完成時間和.

鋼管的制造方法主要有熱軋、焊接和冷加工等，其中熱軋工藝是無縫鋼管的主要制造方法，占無縫管產量的80%.因此，研究熱軋工藝的生產調度對于無縫鋼管的生產具有重要的現實意義.熱軋無縫鋼管的生產工藝較為復雜，其過程可看做是在管坯切割之后的主要變形，工序有3個：穿孔、軋管和定徑，如圖1所示.

圖1 熱軋無縫鋼管的主要工藝流程圖

以天津無縫鋼管公司為例，熱軋無縫鋼管采用的自動軋管機組，切割階段有1臺切割機，穿孔階段有2臺穿孔機，軋管階段有2臺自動軋管機，定徑階段有1臺定徑機.所有的管坯必須在切割之后依次進行穿孔、軋管、定徑等，而且每個階段都有1臺或者1臺以上的同構并行機，因此上述過程可以看作是一個混合流水車間(hybrid flowshop，HFS).然而它不同于典型的HFS，因為在第一階段加工時，一批內的所有工件屬于同一根管坯，因此要求同一批內的所有工件都要在同一臺切割機上進行無間斷地連續切割.于是，上述鋼管切割過程可以看作是第一階段具有批處理特征的HFS調度問題.假定各加工階段間運輸時間不可忽略，所有工件動態到達第一個階段，則形成了本文所研究的考慮運輸時間的第一階段有批處理要求的動態HFS調度問題.

1 問題描述

所要研究的問題是在s個階段調度n個工件，且它們在第一階段按照其切割前所屬管坯組成A批進行加工，目標是最小化所有工件的加權完成時間.當工件在第一階段組批時，每批l包含的工件數al是已知的，同一批內工件之間必須按照已知的優先級關系順序，在第一階段的一臺機器上連續加工.需要注意的是，由于同一批中的工件切割前屬于同一根鋼管，故同一批內的前al-1個工件的加工時間相同，而當前al-1個工件切割完后，第al個工件即已成型，因此，第al個工件的加工時間為0.

此外，在建模中，還有如下假設：①允許每個工件動態到達第一個階段.②一個工件在前一個階段加工結束之后才可進行下一個階段的加工.③一個工件在一個階段沒有加工完成之前不允許中斷.④機器的調整時間忽略不計.

2 模型建立

2.1 參數的設置

2.2 變量的定義

i∈I,j=1,2…,s,k=1,2,…,K;Bij為工件i在第j階段加工的開始時間；Cij為工件i在階段j上的完成時間(它是一個時間點，Cij=k表示工件i的階段j在時刻k的末段完成加工).

2.3 模型的構建

模型構建如下：

(1)

s.t.Bi1≥ri,i∈I,

(2)

(3)

Cij+tj,j+1+pi,j+1≤Ci,j+1,i∈I,j=1,2，…,s-1,

(4)

Cblf，1+pbl,f+1,1=Cbl,f+1,1，l∈{1,2,…,A},f=1,2,…,al-1,

(5)

(6)

kδijk≤Cij,j∈I,j=1,2,…,s,

(7)

δijk∈{0,1},i∈I,j=1,2,…,s,k=1,2,…,K，

(8)

Bij,Cij∈ {1,2,…,K},i∈I,j=1,2,…,s.

(9)

在上述模型中，目標函數(1)最小化所有工件的加權完成時間；約束(2)表示每個工件只有到達第一個階段的機器之后，才能開始加工；約束(3)確保所有工件對機器的需求不能超過在相應時間段可使用的機器數；約束(4)表示同一工件在不同加工階段間的工序優先級約束；約束(5)表示同一批內所有工件在第一階段(切割階段)的優先級約束；約束(6)表示工件在各階段占用機器的時間區間；約束(7)定義工件開始占用機器的時間；約束(8)、(9)定義了變量的取值范圍.

雖然本文所研究的問題與文獻[5]的類似，但這兩項研究不同：首先，研究問題的背景不同，本文所探討的HFS問題來源于鋼管生產的工藝流程，故而第一階段具有批處理特征，而文獻[5]則是從鋼鐵行業煉鋼-熱軋-連鑄階段提煉出來的，且最后一階段是具有批處理特征的HFS調度問題；其次，目標函數不同，本文以最小化工件加權總完成時間為目標，而文獻[5]則考慮了總加權完成時間和對工件等待的懲罰；最后，本文考慮了工件的動態到達時間，從而表現了一定的動態特性，而文獻[5]則是假定所有的工件在時間1都是可用的，即不考慮工件的動態到達時間.

3 改進LR的求解方法構造

以往關于求解HFS調度的研究較多.文獻[6]中對HFS調度問題的求解方法有總結和歸納，主要有精確算法、啟發式算法和混合啟發式算法等.由于精確算法在解決復雜問題時往往耗時較長，而啟發式算法雖然能在較短時間內得到可行解，但解的質量難于評價，又鑒于所建立的模型是“可分離的”(目標(1)是加和的形式，且耦合不同工件的機器能力約束是線性的)，因此，提出改進的LR算法求解2.2節所建模型，求解過程構造如下.

3.1 拉格朗日松弛

由于約束(3)耦合不同的批，利用拉格朗日乘子μjk將其松弛到目標函數中，形成LR問題

(10)

滿足約束(2)，(4)～(9)和

μjk≥0,j=1,2,…,s,k=1,2,…,K，

(11)

從而得到拉格朗日對偶問題

滿足(2)，(4)～(9)，(11).給定一組拉格朗日乘子{μjk}，分解后對應于每批l的子問題為

(12)

滿足(2)，(4)～(9)，(11).因此，L(μ)也可以寫為

(13)

3.2 拉格朗日乘子的更新過程設計

求解對偶問題過程中，常采用次梯度算法來更新拉格朗日乘子，μh+1=μh+ahgh，其中，gh=g(μh)是L(μ)的次梯度，ah是第h次迭代的步長.

3.3 原問題可行解的構造

由于約束(3)被松弛，因此對偶問題的解在某段時間內可能違背能力約束，所以它得到的解通常是不可行的.為構造可行解，基于局域搜索和文獻[7]提出的列表調度構造一個兩階段啟發式算法.

3.4 子問題的求解過程設計

圖2 一批的出樹結構

將文獻[8]所提出的動態規劃應用推廣到上述的批級子問題，令一個節點表示一個工序(i,j)，假定同一批內有3個工件，共有4個階段，即al=3,s=4，則每個批級子問題中的所有工序構成與文獻[5]中子問題結構相反的出樹結構(圖2).圖中虛線框內的所有工序是作為一批在一臺機器上按順序加工且不允許中斷，實箭頭表示物流的流向，虛箭頭表示工序之間的加工順序.

以往也有一些研究對工件間存在優先級或一個工件內的各工序間存在優先級的LR問題應用動態規劃(dynamic programming,DP)進行求解[9-11].然而，作者所研究的子問題和文獻提到的子問題不同，主要區別在于處理第一道工序的那臺機器的生產方式：在該批處理機上有一序列工序，它們是作為一批進行處理，并且除了批中的最后一個工件加工時間為零之外，其他工件的加工時間均相等，且在第一階段同一批內工件的加工順序一定.為此，設計了求解該子問題的改進DP算法.

(14)

令Ph表示工序h(h= 1,2,…,sal)的緊后工序的集合，令Fh(k)表示調度工序h和它的緊后工序在時刻k之前完成的最小總費用.后向動態規劃(BDP)從最后一個節點開始，一直到節點1結束.

工序h=(s-1)al+1,(s-1)al+2,…,sal的費用給定為

Fh(Cih jh)=Vh(Cih jh).

(15)

當工序h(h∈{al,…,(s-1)al})的累計費用為

(16)

當工序h=1,2,…,al-1的累積費用為

(17)

在計算Fh(Cihjh)時，關于工序h的緊后工序的函數Fx(Cixjx)和Fy(Ciyjy)都是已知量.由于每批內第一道工序是所有其他sal-1道工序的先前工序，因此，可計算得到下界

(18)

最后沿著最優路徑向后追蹤得到對應子問題的最優解.

4 算例

以一個有3個工件的批級子問題為例，假設這3個工件{1，2，3}依次經過3個階段進行加工，在第一階段上，它們組成一批并按照1-2-3的順序在一臺機器上進行加工，運輸時間t12和t23分別為1和2.表1給出了每個工件在每個階段的加工時間、在第一階段的動態到達時間、工件的權重以及在每個階段可用的機器能力數.

在求解拉格朗日對偶問題時，將拉格朗日乘子{μjk}的初始值設為0.5，第一次迭代時利用改進DP求解這個批級子問題的詳細過程如表1.

表1 算例數據

Step1按照從第一階段到最后階段及工序在批內的位置排列所有工序，與圖2相似(無第4階段).

Step2確定每道工序的緊前工序，并對它們進行分類.工序7,8,9無緊后工序；工序3,4,5,6有一道緊后工序，分別為6,7,8,9，它們屬于x類型；工序1,2有兩道緊后工序：包括x類型工序{4,5}和y類型的工序{2,3}.

Step3根據式(4)和(5)，計算每個工件的可能的工序完成時間.該例中，每個工件的每道工序的完成時間集合為：C11∈{2,3,4,5,6}，C12∈{6,7,8,9}，C13∈{9,10,11,12}，C21∈{4,5,6,7,8}，C22∈{6,7,8,9,10}，C23∈{9,10,11,12,13}，C31∈{6,7,8,9}，C32∈{9,10,11,12,13}，C33∈{14,15,16,17}.

Step4根據式(14)，計算

F7(9)= 18.5;F7(10)=20.5;F7(11)=22.5;F7(12)=24.5;

F8(9)=9.5;F8(10)=10.5;F8(11)=11.5;F8(12)=12.5;F8(13)=13.5;

F9(14)=29.5;F9(15)=31.5;F9(16)=33.5;F9(17)=35.5.

Step5根據式(15)和(16)，計算F3(C31)，F4(C12)，F5(C22)和F6(C32).

F6(9)=V6(9)+F9(14)=30.5;F6(10)=V6(10)+F9(15)=32.5;

F6(11)=V6(11)+F9(16)=34.5;F6(12)=V6(12)+F9(17)=36.5;

F5(6)=V5(6)+F8(9)=10;F5(7)=V5(7)+F8(10)=11;F5(8)=V5(8)+F8(11)=12;

F5(9)=V5(9)+F8(12)=12;F5(10)=V5(10)+F8(13)=13;

F4(6)=V4(6)+F7(9)=19.5;F4(7)=V4(7)+F7(10)=21.5;

F4(8)=V4(8)+F7(11)=23.5;F4(9)=V4(9)+F7(12)=25.5;

F3(6)=V3(6)+F6(9)=30.5;F3(7)=V3(7)+F6(10)=32.5;

F3(8)=V3(8)+F6(11)=34.5;F3(9)=V3(9)+F6(12)=36.5.

Step6根據式(17)，計算F1(C11)，F2(C21).

F2(4)=V2(4)+F5(6)+F3(6)=41.5;F2(5)=V2(5)+F5(7)+F3(7)=44.5;

F2(6)=V2(6)+F5(8)+F3(8)=47.5;F2(7)=V2(7)+F5(9)+F3(9)=50.5;

F2(8)=V2(8)+F5(10)+F3(10)=53.5;

F1(2)=V1(2)+F2(4)+F4(6)=62;F1(3)=V1(3)+F2(5)+F4(7)=65;

F1(4)=V1(4)+F2(6)+F4(8)=68;F1(5)=V1(5)+F2(7)+F4(9)=71;

F1(6)=V1(6)+F2(8)+F4(10)=74.

Step7通過向前追蹤得到子問題的解.

C11=2;C12=6;C13=9;C21=4;C22=6;C23=9;C31=6;C32=9;C33=14.

5 結束語

對考慮運輸時間的第一階段具有批處理特征的動態HFS調度問題進行了研究,將此問題建模為一個整數規劃模型，并設計了改進LR算法的求解過程.通過松弛機器能力約束，將原問題分解成多個獨立的批級子問題，用動態規劃求解子問題，并用實例來說明第一次迭代時利用改進DP求解批級子問題的詳細過程；用次梯度方法求解拉格朗日對偶問題；兩階段啟發式算法構造原問題的可行解.下一步研究利用鋼管廠的實際生產數據來驗證所提出的模型和算法過程.

[1] Atighehchian A,Bijari M,Tarkesh H.A novel hybrid algorithm for scheduling steel-making continuous casting production[J].Computers & Operations Research,2009,36(8): 2450-2461.

[2] 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.

[3] Li Dawei,Wang Li,Wang Mengguang.Genetic algorithm for production lot planning of steel pipe[J].Production Planning and Control,1999,10(1): 54-57.

[4] Xuan Hua.A Lagrangian relaxation algorithm for the order planning of steel pipe[J].International Conference of Management Science and Information System,2009(1/2/3/4): 685-688.

[5] Xuan Hua,Tang Lixin.Scheduling a hybrid flowshop with batch production at the last stage[J].Computer & Operations Research,2007,34(9): 2718-2733.

[6] Ruiz R,Vazquez-Rodriguez J A.The hybrid flow shop scheduling problem[J].European Journal of Operational Research,2010,205:1-18.

[7] Hoitomt D J,Luh P B,Pattipati K R.A practical approach to job-shop scheduling problems[J].IEEE Transactions on Robotics and Automation,1993,9(1): 1-13.

[8] Oguz C,Tang L.A Lagrangian relaxation method for hybrid flow-shop scheduling with multiprocessor tasks to minimize total weighted completion time[C]//Proceedings of the 1st Multidisciplinary International Conference on Scheduling:Theory and Applications.Nottingham,2003: 638-653.

[9] Abdul-Razaq T S,Potts C N,Van Wassenhove L N.A survey of algorithms for the single machine total weighted tardiness scheduling problem[J].Discrete Applied Mathematics,1990,26(2/3):235-253.

[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] Tang Lixin,Xuan Hua,Liu Jiyin.Hybrid backward and forward dynamic programming based Lagrangian relaxation for single machine scheduling[J].Computers & Operations Research,2007,34(9): 2625-2636.