罩式退火過程中的多吊機(jī)調(diào)度問題

謝 謝，李彥平

（沈陽大學(xué) 遼寧省裝備制造綜合自動化重點(diǎn)實(shí)驗(yàn)室，遼寧 沈陽 110044）

罩式退火過程中的多吊機(jī)調(diào)度問題

謝 謝，李彥平

（沈陽大學(xué) 遼寧省裝備制造綜合自動化重點(diǎn)實(shí)驗(yàn)室，遼寧 沈陽 110044）

研究了鋼鐵企業(yè)罩式退火中的多吊機(jī)調(diào)度問題，目標(biāo)函數(shù)是最小化最后一個板卷的退火完工時間.通過考慮機(jī)器和吊機(jī)位置，建立了混合整數(shù)規(guī)劃模型，并提出了一種整合的方法以降低問題的難度同時保持問題的本質(zhì).然而，即使是整合后的問題也是強(qiáng)NP難的.進(jìn)一步提出了包括分配和調(diào)度的兩階段啟發(fā)式算法.在分配階段，利用動態(tài)規(guī)劃先將每個吊機(jī)分配給唯一的子區(qū)塊，再進(jìn)行機(jī)器的分配.調(diào)度階段采用最早需要操作階段優(yōu)先的策略.最后，算法的有效性通過絕對性能分析的角度給出了估測.

吊機(jī)調(diào)度；罩式退火過程；強(qiáng)NP難；啟發(fā)式；絕對性能分析

罩式退火過程是鋼鐵企業(yè)冷軋板卷后道工序生產(chǎn)常見的模式.通常三四個板卷預(yù)先組成一垛，每垛板卷需要經(jīng)過先加熱后冷卻的生產(chǎn)階段.加熱階段需要使用的工具為加熱罩，冷卻階段需要使用的工具為冷卻罩.兩種工具的數(shù)量都是有限的.本文將每垛板卷定義為一個工件.罩式退火車間通常由若干矩形的區(qū)組成，在每一區(qū)內(nèi)，爐臺按照它們的坐標(biāo)排列.在區(qū)的上方，有兩個或多個吊機(jī)同時操作，如圖1所示（圖中的符號將在后面解釋）.本文提出并分析了一個多吊機(jī)調(diào)度的模型，同時考慮分配和調(diào)度有限的加熱罩、冷卻罩，以使一個區(qū)內(nèi)工件的最大完工時間最小化.

圖1 罩式退火車間內(nèi)一個R＝10和L＝3區(qū)域的圖例Fig.1 Case diagram of an area with R＝0 and L＝3 in batch annealing workshop

每個板卷的退火過程需要在固定爐臺上進(jìn)行，從裝爐到卸載必須經(jīng)過12個階段，這12個階段為一個退火周期.退火周期各階段如下：■裝板卷和對流板；①裝內(nèi)罩；②自然充氣；③裝加熱罩；④加熱；⑤卸加熱罩；⑥自然冷卻；⑦裝冷卻罩；⑧強(qiáng)制冷卻；⑨卸冷卻罩；⑩卸內(nèi)罩；○11卸板卷和對流板.

在所有階段中，除第2階段（自然充氣）、第4階段（加熱）、第6階段（自然冷卻）和第8階段（強(qiáng)制冷卻）外，其余都需要上方的吊機(jī)的裝載或卸載.裝載一臺工具可以看做由吊機(jī)進(jìn)行的連續(xù)操作：吊機(jī)從當(dāng)前位置提起工具，帶著它一起移動直到將它放置在另一爐臺上.如果沒有其他爐臺需要這個工具，吊機(jī)將它提起后直接放在當(dāng)前爐臺旁邊即完成卸載.

基于上面的問題描述，根據(jù)生產(chǎn)實(shí)際，所提出的主要假設(shè)如下：

（1）每垛板卷必須分配給每個爐臺.對流板數(shù)量充足，放在每個爐臺旁邊.每個爐臺與內(nèi)罩一一對應(yīng).

（2）每垛板卷加工的12個階段必須在一個爐臺上進(jìn)行.

（3）自然充氣和自然冷卻的時間不是嚴(yán)格的確定時間，除此之外，其余各階段的時間均為確定值，并預(yù)先已知.

（4）吊機(jī)在兩個爐臺之間的運(yùn)輸時間可以確定.

（5）各設(shè)備在加工過程中沒有故障.

（6）板卷、各種罩以及吊機(jī)在零時刻之前不可獲得.

（7）直到加熱或冷卻階段停止時，吊機(jī)才允許卸罩或裝罩.

（8）所有的加熱罩（冷卻罩）都是相同的.

現(xiàn)有的關(guān)于吊機(jī)調(diào)度的研究主要處理兩方面的問題：電鍍生產(chǎn)線的吊機(jī)調(diào)度問題和集裝箱終端的岸吊或場吊調(diào)度問題.在電鍍生產(chǎn)線中，無論是單吊機(jī)調(diào)度問題還是多吊機(jī)調(diào)度問題，大部分的研究主要集中在決策最優(yōu)周期的問題［1－3］.Lee等［4］、Hall等［5］、Mak等［6］和 Crama等［7］分別給出了相關(guān)的綜述，幾乎所有的調(diào)度過程都是周期性的.另一方面，在集裝箱終端，大部分的研究主要側(cè)重于從計(jì)算智能的角度對吊機(jī)調(diào)度問題進(jìn)行研究［8－12］，幾乎沒有從理論分析的角度對算法的性能進(jìn)行證明.以上文獻(xiàn)中的吊機(jī)調(diào)度沒有可直接應(yīng)用于鋼鐵企業(yè)中的吊機(jī)調(diào)度.此外，已有文獻(xiàn)對問題的一些額外特點(diǎn)，如工件固定不動、每個工件需要吊機(jī)多次操作以及無周期的目標(biāo)函數(shù)均沒有進(jìn)行研究.本文的研究可以看做結(jié)合了吊機(jī)調(diào)度和工具分配，而在以前的研究中，這兩者是相互獨(dú)立的.這種包含調(diào)度和分配本質(zhì)上增加了問題的復(fù)雜性.在過去的十多年中，盡管罩式退火過程受到了Moon和Hrymak［13］的關(guān)注，然而他們的研究側(cè)重于工件的加工而忽略了吊機(jī)的移動、上提下放時間，即使在最簡單的假設(shè)下，也很少對這個調(diào)度問題提出理論模型并進(jìn)行分析.因此，本文一方面通過理論分析對這個實(shí)際問題進(jìn)行了更清楚的研究，另一方面提出了有效的啟發(fā)式算法，為實(shí)際問題提供更快、更近似的解.

1 問題模型和分析

1.1 問題參數(shù)

給定n個工件的集合Ω＝｛1，2，…，n｝，每個工件已經(jīng)預(yù)先放在裝載區(qū)域上.每個爐臺位置固定并按照坐標(biāo)排放.鑒于加工過程中工件與爐臺之間的一一對應(yīng)，工件i的位置可以表示為w i＝（x i，y i）（?i∈Ω）（如圖1所示）.同一行或列中相鄰兩爐臺之間的距離為d.

給定兩類工具的集合F和C，分別表示加熱罩和冷卻罩的集合.每個集合的基數(shù)為｜·｜.工具的位置等于與它距離最近的爐臺的位置.

給定吊機(jī)的集合M，這些吊機(jī)共享同一跨，從左至右分別表示為1，2，…，｜M｜.為了避免碰撞，相鄰的吊機(jī)之間必須至少保持一個安全距離d.吊機(jī)的位置等于吊鉤向地面的投影與之距離最近的工件位置.

吊機(jī)從爐臺上提或者下放一臺工具到爐臺的時間為μ（本文可以很容易擴(kuò)展為上提和下放時間不同的情況）.吊機(jī)帶著工具運(yùn)行的速度為v，空運(yùn)行的速度為λ（λ≥v）.

定義吊機(jī)操作階段的集合S＝｛0，1，3，5，7，9，10，11｝和兩個加工階段的集合S′＝｛4，8｝，其中，4和8分別代表加熱和強(qiáng)制冷卻階段.此外，自然充氣和自然冷卻的集合可以表示為S″＝｛2，6｝.對于一個工件的任意階段b，q∈S∪S′∪S″，b＜q意味著b必須在q之前進(jìn)行.

令Cmax（σH）為由算法H得到的調(diào)度σH的最大完工時間，Cmax（σ＊）為最優(yōu)調(diào)度σ＊的完工時間.如果對于問題的任意一個例子，都有Cmax（σH）－Cmax（σ＊）≤α成立，那么算法H的絕對性能比為α.

（1）輸入數(shù)據(jù)如下.

p is，?i∈Ω，工件i在第s階段的處理時間.除第3，5，7，9需要在調(diào)度階段進(jìn)行決策外，其他的都是預(yù)先給定的.

A，一個非常大的正數(shù).

（2）決策變量如下.

zipjq∈｛0，1｝，?i，j∈Ω，?p，q∈S∪S′∪S″，如果工件j的第q個狀態(tài)在工件i的第p個狀態(tài)完成后開始，那么zipjq＝1，否則zipjq＝0.

p i3，p i5，p i7和p i9等于工件間總的轉(zhuǎn)移時間，這個時間依賴于它們的位置和上提與下放時間的總和.

Dip，?i∈Ω，p∈S∪S′∪S″，工件i的p個狀態(tài)的完工時間.

1.2 問題模型

根據(jù)上面定義的各變量，問題可以表述成一個混合整數(shù)規(guī)劃模型.當(dāng)相鄰兩個吊機(jī)同時操作時，需要考慮吊機(jī)間的不碰撞約束.

1.3 模型的分析

上述模型包括大量的整數(shù)變量，即使一臺吊機(jī)，使用CPLEX軟件嘗試解決8個工件的例子，預(yù)處理時間已經(jīng)超過40 min.鑒于很難在合理的時間內(nèi)對這個實(shí)際問題求得最優(yōu)調(diào)度，因此需要進(jìn)一步探究問題的性質(zhì)并提出近似算法.

2 一種整合的方法

這種整合的方法可以將罩式退火過程劃分為8個階段，再將這8個階段過程整合為3層.

第一層 由于前三個階段不需要作任何決策，因此這一層包括3個階段.在這一層，裝載一個板卷垛、內(nèi)罩和自然充氣的過程（階段0，1和2）可以看做一道工序.

第二層 這一層從裝載加熱罩到卸載冷卻罩（階段3，4，5，6，7，8和9）.一方面，需要將數(shù)量有限的工具（加熱罩和冷卻罩）分配給工件；另一方面，在避免吊機(jī)碰撞的基礎(chǔ)上調(diào)度這些工具.

第三層 把最后兩階段連續(xù)地進(jìn)行看做一道工序（階段10和11）.吊機(jī)將內(nèi)罩卸載到爐臺旁邊后再將工件卸載到卸載站.

3 兩階段啟發(fā)式算法及絕對性能分析

3.1 兩階段啟發(fā)式算法

這部分提出一個兩階段啟發(fā)式算法H，包括分配工具和調(diào)度吊機(jī)兩方面.第一階段包括吊機(jī)的分配和工具的分配.一方面，將工作區(qū)域分成｜M｜個互不重疊的子區(qū)域，使每個吊機(jī)分配到各自的操作區(qū)域；另一方面，將每臺工具分配到已劃分好的子區(qū)域.也就是說，問題可以看做｜M｜個互不相關(guān)的單吊機(jī)調(diào)度問題.

3.1.1 吊機(jī)分配策略

從左至右，將子區(qū)域編號｛1，2，…，R｝.令L表示在每個子區(qū)域內(nèi)工件的個數(shù)，如圖1所示，R＝10，L＝3.令ak表示分配給吊機(jī)k的最小基本子區(qū)域的編號k＝1，2，…，｜M｜.因此，｛ak，ak＋1，…，ak＋1－1｝即為分配給吊機(jī)k的子區(qū)域集合.根據(jù)子區(qū)域的編號方式，所有的子區(qū)域相互獨(dú)立，獨(dú)一無二地分配吊機(jī).顯然，有

｛a1，a1＋1，…，a2－1，a2，a2＋1，…，

a3－1，…，am，am＋1，…，R｝＝ ｛1，2，…，R｝.

令t（i，j）表示位于從基本區(qū)域i到j(luò)的子區(qū)域中工件總裝載時間和卸載時間和，i≤j.f（k，sk）表示由吊機(jī)k操作工件的最小總完工時間，k＝1，2，…，｜M｜，其中，ak＝sk.也就是分配給每個吊機(jī)k，k＋1，…，｜M｜的子區(qū)域集合分別為｛sk，sk＋1，…，ak＋1－1｝，｛ak＋1，ak＋1＋1，…，ak＋2－1｝，…，｛am，am＋1，…，R｝.事實(shí)上，每臺吊機(jī)每次只能對｛1，2，…，R｝集合中的一個基本子區(qū)域內(nèi)的工件進(jìn)行操作，同時覆蓋這個基本子區(qū)域的位置.根據(jù)t（i，j）和f（k，sk）的定義，

如果k＝1，那么f（1，s1）＝t（s1，a2－1），其中，s1＝1，2，…，R－m＋1.

如果k＝m，那么f（m，sm）＝t（sm，R），其中，sm＝m，m＋1，…，R.

如果1＜k＜m，那么f（k，sk）＝t（sk，ak＋1－1），其中，sk＝k，k＋1，…，R－m＋k.

隨著操作區(qū)域被劃分成｜M｜個互不重疊的子區(qū)域，吊機(jī)分配的策略可以由下式確定：

由于所有的工件事先放在裝載站中，因此計(jì)算t（sk，ak＋1－1）等價于為｜M｜個吊機(jī)分別選擇每個子區(qū)域的工件.

3.1.2 工具分配策略

將在已劃分好的每個子區(qū)域內(nèi)給出工具的分配策略.以加熱罩分配為例，冷卻罩的分配與加熱罩相同.本文中用［x］表示不小于x的最小整數(shù).令Sk表示由吊機(jī)操作的子區(qū)域，其中，k＝1，2，…，｜M｜.ΩSk表示在S k中的工件集合.不失一般性，假設(shè)Sk中分配到的加熱罩?jǐn)?shù)｜FSk｜滿足1≤｜FSk｜≤｜F｜.

3.1.3 調(diào)度階段

基于工具的分配，調(diào)度階段盡可能減少吊機(jī)和工具的空閑或者等待時間.每個子區(qū)域內(nèi)的單吊機(jī)調(diào)度描述如下：

第1步 優(yōu)先于其他操作階段裝載所有的工件.

第2步 決定任意兩個分享同一加熱罩的工件加熱順序.

第3步 為了盡可能減少吊機(jī)空閑時間，計(jì)算工件某階段最早需要吊機(jī)操作的時間（工件某階段最早的完工時間減去吊機(jī)從當(dāng)前位置到工件之間的移動時間）.

3.2 啟發(fā)式的絕對性能分析

由于每臺工具一次最多加工一個工件，可行的吊機(jī)調(diào)度不能小于在每個子區(qū)域內(nèi)一個工件各階段加工時間的總和.這提供了確定最優(yōu)調(diào)度值的下界.另一方面，如果問題的可行解存在，那么依次加工完各工件的總時間提供了最優(yōu)調(diào)度值的上界.因此，可以得到下面的結(jié)論：

最后一項(xiàng)表示所有加熱罩和冷卻罩卸載到最后位置的時間.

結(jié)合n＝RL，可以得到下面的定理：

定理1 對任意一個由算法H產(chǎn)生的調(diào)度σH，它的絕對性能保證為

4 結(jié) 語

本文研究了罩式退火過程中的多吊機(jī)調(diào)度問題以最小化最大完工時間.這個被證明為強(qiáng)NP難的實(shí)際問題，本文給出了混合整數(shù)規(guī)劃模型，并提出一種整合的方法以簡化問題并保持問題的本質(zhì).在此基礎(chǔ)上提出一個啟發(fā)式算法并從絕對性能的角度分析了這個算法.

本文可以擴(kuò)展為多方向的.如，對于加熱罩（冷卻罩）不同這樣更一般的情況提出和分析算法.此外，基于理論分析的其他目標(biāo)函數(shù)的該問題也是吸引我們進(jìn)一步研究的方向.

［1］ Liu J Y，Jiang Y，Zhou Z L.Cyclic scheduling of a single hoist in extended electroplating lines：a comprehensive integer programming solution［J］.IIE Transactions，2002，34（10）：905－914.

［2］ Liu J Y，Jiang Y.An efficient optimal solution to the two－h(huán)oist no－wait cyclic scheduling problem［J］.Operations Research，2005，53（2）：313－327.

［3］ Jiang Y，Liu J Y.Multihoist cyclic scheduling with fixed processing and transfer times［J］.IEEE Transactions on Automation Science and Engineering，2007，4（3）：435－450.

［4］ Lee C Y，Lei L，Pinedo M.Current trends in deterministic scheduling［J］. Annals of Operations Research，1997，70（1）：1－41.

［5］ Hall N G，Kamoun H，Sriskandarjah C.Scheduling in robotic cells：complexity and steady state analysis［J］.European Journal of Operational Research，1998（109）：43－65.

［6］ Mak R，Wong Y，Leung J M Y，et al.The hoist scheduling problem for no－wait production lines：a survey of research［R］∥Technical Report SEEM 2000—2005.2000.

［7］ Crama Y，Kats V，Van de Klundert J，et al.Cyclic scheduling in robotic flowshops［J］.Annals of Operations Research，2000，96：97－124.

［8］ Liu J Y，Wan Y W，Wang L.Quay crane scheduling at container terminals to minimize the maximum relative tardiness of vessel departures［J］. Naval Research Logistics，2006（53）：60－74.

［9］ Zhu Y，Lim A.Crane scheduling with non－crossing constraints［J］.Journal of the Operational Society，2006（57）：1464－1471.

［10］ Bish E K. A multiple－crane－constrained scheduling problem in a container terminal［J］.European Journal of Operational Research，2003（14）：83－107.

［11］ Moccia L，Cordeau J F，Gaudioso M，et al.A branch－and cut algorithm for the quay crane scheduling problem in a container terminal［J］.Naval Research Logistics，2006（53）：45－59.

［12］ Ngw C.Crane scheduling in container yards with intercrane interference［J］.European Journal of Operational Research，2005，164（1）：64－78.

［13］ Moon S，Hrymak A N.Scheduling of the batch annealing process：deterministic case［J］.Computers and Chemical Engineering，1999，23（9）：1193－1208.

［14］ Xie X，Tang L X.Crane Scheduling in Batch Annealing Process［C］.Proceedings of the IEEE International Conference on Automation and Logistics，Qingdao，2008.

Multi－Crane Scheduling in Batch Annealing Process

XIEXie，LIYanping
（Key Laboratory of Manufacturing Industrial and Integrated Automation，Shenyang University，Shenyang 110044，China）

A multi－crane scheduling problem was addressed，which is motivated by batch annealing process（BAP）in the iron and steel factory.The objective is to minimize the last coil annealing completion time（makespan）.A mixed－integer linear programming（MILP）model is formulated by considering both positions of bases and cranes.Afterwards，an aggregate approach is proposed to reduce problem difficulty but keep the essential features of practical problem.However，the aggregated problem is still proofed strongly NP－h(huán)ard.A two－phase heuristic algorithm is proposed，which consists of assignment and scheduling.The assignment phase based on a dynamic programming is to assign each crane to its exclusive sub－region，followed by a resource assignment to each subregion.Scheduling phase adopts an earliest requirement performed stage first strategy.Finally，from an absolute performance point of view，the quality of the proposed heuristic is measured.

crane scheduling；batch annealing process；strongly NP－h(huán)ard；heuristics；absolute performance analysis

TG 156.2

A

1008－9225（2012）01－0012－08

2011－11－10

國家自然科學(xué)基金資助項(xiàng)目（61104029）；遼寧省教育廳基金資助項(xiàng)目（L2011207）.

謝 謝（1981－），女，遼寧沈陽人，沈陽大學(xué)講師，博士；李彥平（1958－），男，遼寧沈陽人，沈陽大學(xué)教授，博士.

劉乃義】