軒 華， 曹 穎

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

0 引言

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

鋼管的制造方法主要有熱軋、焊接和冷加工等，其中熱軋工藝是無(wú)縫鋼管的主要制造方法，占無(wú)縫管產(chǎn)量的80%.因此，研究熱軋工藝的生產(chǎn)調(diào)度對(duì)于無(wú)縫鋼管的生產(chǎn)具有重要的現(xiàn)實(shí)意義.熱軋無(wú)縫鋼管的生產(chǎn)工藝較為復(fù)雜，其過(guò)程可看做是在管坯切割之后的主要變形，工序有3個(gè)：穿孔、軋管和定徑，如圖1所示.

圖1 熱軋無(wú)縫鋼管的主要工藝流程圖

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

1 問(wèn)題描述

所要研究的問(wèn)題是在s個(gè)階段調(diào)度n個(gè)工件，且它們?cè)诘谝浑A段按照其切割前所屬管坯組成A批進(jìn)行加工，目標(biāo)是最小化所有工件的加權(quán)完成時(shí)間.當(dāng)工件在第一階段組批時(shí)，每批l包含的工件數(shù)al是已知的，同一批內(nèi)工件之間必須按照已知的優(yōu)先級(jí)關(guān)系順序，在第一階段的一臺(tái)機(jī)器上連續(xù)加工.需要注意的是，由于同一批中的工件切割前屬于同一根鋼管，故同一批內(nèi)的前al-1個(gè)工件的加工時(shí)間相同，而當(dāng)前al-1個(gè)工件切割完后，第al個(gè)工件即已成型，因此，第al個(gè)工件的加工時(shí)間為0.

此外，在建模中，還有如下假設(shè)：①允許每個(gè)工件動(dòng)態(tài)到達(dá)第一個(gè)階段.②一個(gè)工件在前一個(gè)階段加工結(jié)束之后才可進(jìn)行下一個(gè)階段的加工.③一個(gè)工件在一個(gè)階段沒(méi)有加工完成之前不允許中斷.④機(jī)器的調(diào)整時(shí)間忽略不計(jì).

2 模型建立

2.1 參數(shù)的設(shè)置

2.2 變量的定義

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

2.3 模型的構(gòu)建

模型構(gòu)建如下：

(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)

在上述模型中，目標(biāo)函數(shù)(1)最小化所有工件的加權(quán)完成時(shí)間；約束(2)表示每個(gè)工件只有到達(dá)第一個(gè)階段的機(jī)器之后，才能開(kāi)始加工；約束(3)確保所有工件對(duì)機(jī)器的需求不能超過(guò)在相應(yīng)時(shí)間段可使用的機(jī)器數(shù)；約束(4)表示同一工件在不同加工階段間的工序優(yōu)先級(jí)約束；約束(5)表示同一批內(nèi)所有工件在第一階段(切割階段)的優(yōu)先級(jí)約束；約束(6)表示工件在各階段占用機(jī)器的時(shí)間區(qū)間；約束(7)定義工件開(kāi)始占用機(jī)器的時(shí)間；約束(8)、(9)定義了變量的取值范圍.

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

3 改進(jìn)LR的求解方法構(gòu)造

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

3.1 拉格朗日松弛

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

(10)

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

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

(11)

從而得到拉格朗日對(duì)偶問(wèn)題

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

(12)

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

(13)

3.2 拉格朗日乘子的更新過(guò)程設(shè)計(jì)

求解對(duì)偶問(wèn)題過(guò)程中，常采用次梯度算法來(lái)更新拉格朗日乘子，μh+1=μh+ahgh，其中，gh=g(μh)是L(μ)的次梯度，ah是第h次迭代的步長(zhǎng).

3.3 原問(wèn)題可行解的構(gòu)造

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

3.4 子問(wèn)題的求解過(guò)程設(shè)計(jì)

圖2 一批的出樹(shù)結(jié)構(gòu)

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

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

(14)

令Ph表示工序h(h= 1,2,…,sal)的緊后工序的集合，令Fh(k)表示調(diào)度工序h和它的緊后工序在時(shí)刻k之前完成的最小總費(fèi)用.后向動(dòng)態(tài)規(guī)劃(BDP)從最后一個(gè)節(jié)點(diǎn)開(kāi)始，一直到節(jié)點(diǎn)1結(jié)束.

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

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

(15)

當(dāng)工序h(h∈{al,…,(s-1)al})的累計(jì)費(fèi)用為

(16)

當(dāng)工序h=1,2,…,al-1的累積費(fèi)用為

(17)

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

(18)

最后沿著最優(yōu)路徑向后追蹤得到對(duì)應(yīng)子問(wèn)題的最優(yōu)解.

4 算例

以一個(gè)有3個(gè)工件的批級(jí)子問(wèn)題為例，假設(shè)這3個(gè)工件{1，2，3}依次經(jīng)過(guò)3個(gè)階段進(jìn)行加工，在第一階段上，它們組成一批并按照1-2-3的順序在一臺(tái)機(jī)器上進(jìn)行加工，運(yùn)輸時(shí)間t12和t23分別為1和2.表1給出了每個(gè)工件在每個(gè)階段的加工時(shí)間、在第一階段的動(dòng)態(tài)到達(dá)時(shí)間、工件的權(quán)重以及在每個(gè)階段可用的機(jī)器能力數(shù).

在求解拉格朗日對(duì)偶問(wèn)題時(shí)，將拉格朗日乘子{μjk}的初始值設(shè)為0.5，第一次迭代時(shí)利用改進(jìn)DP求解這個(gè)批級(jí)子問(wèn)題的詳細(xì)過(guò)程如表1.

表1 算例數(shù)據(jù)

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

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

Step3根據(jù)式(4)和(5)，計(jì)算每個(gè)工件的可能的工序完成時(shí)間.該例中，每個(gè)工件的每道工序的完成時(shí)間集合為：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根據(jù)式(14)，計(jì)算

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根據(jù)式(15)和(16)，計(jì)算F3(C31)，F(xiàn)4(C12)，F(xiàn)5(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根據(jù)式(17)，計(jì)算F1(C11)，F(xiàn)2(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通過(guò)向前追蹤得到子問(wèn)題的解.

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

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

對(duì)考慮運(yùn)輸時(shí)間的第一階段具有批處理特征的動(dòng)態(tài)HFS調(diào)度問(wèn)題進(jìn)行了研究,將此問(wèn)題建模為一個(gè)整數(shù)規(guī)劃模型，并設(shè)計(jì)了改進(jìn)LR算法的求解過(guò)程.通過(guò)松弛機(jī)器能力約束，將原問(wèn)題分解成多個(gè)獨(dú)立的批級(jí)子問(wèn)題，用動(dòng)態(tài)規(guī)劃求解子問(wèn)題，并用實(shí)例來(lái)說(shuō)明第一次迭代時(shí)利用改進(jìn)DP求解批級(jí)子問(wèn)題的詳細(xì)過(guò)程；用次梯度方法求解拉格朗日對(duì)偶問(wèn)題；兩階段啟發(fā)式算法構(gòu)造原問(wèn)題的可行解.下一步研究利用鋼管廠的實(shí)際生產(chǎn)數(shù)據(jù)來(lái)驗(yàn)證所提出的模型和算法過(guò)程.

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