工件和工具混合搬運(yùn)的多吊機(jī)調(diào)度問題

謝　謝, 鄭勇躍, 李彥平

(1. 沈陽大學(xué) 裝備制造綜合自動(dòng)化重點(diǎn)實(shí)驗(yàn)室, 遼寧 沈陽　110044;2. 遼寧省標(biāo)準(zhǔn)化研究院, 遼寧 沈陽　110004)

?

工件和工具混合搬運(yùn)的多吊機(jī)調(diào)度問題

謝謝1, 鄭勇躍2, 李彥平1

(1. 沈陽大學(xué) 裝備制造綜合自動(dòng)化重點(diǎn)實(shí)驗(yàn)室, 遼寧 沈陽110044;2. 遼寧省標(biāo)準(zhǔn)化研究院, 遼寧 沈陽110004)

從鋼鐵企業(yè)罩式退火過程提煉出一類工件和工具混合搬運(yùn)的多吊機(jī)調(diào)度問題以最小化最大完工時(shí)間.由于該問題是強(qiáng)NP-難的,提出一個(gè)基于工具分配的啟發(fā)式算法并證明了算法的絕對(duì)性能比為2,漸近性能比為3.算法的性能通過數(shù)值計(jì)算實(shí)驗(yàn)給出了估測(cè),結(jié)果表明,所提出的啟發(fā)式算法對(duì)大規(guī)模問題也可以產(chǎn)生高質(zhì)量的解.

調(diào)度;罩式退火過程;絕對(duì)最壞性能;漸近最壞性能

鋼鐵企業(yè)的罩式退火是根據(jù)材料和工件尺寸采用不同的保溫時(shí)間,然后進(jìn)行緩慢冷卻,目的是使金屬內(nèi)部組織達(dá)到或接近平衡狀態(tài),獲得良好的工藝性能和使用性能,或者為進(jìn)一步淬火作組織準(zhǔn)備.罩式退火車間通常由若干矩形的區(qū)組成,在每一區(qū)內(nèi),爐臺(tái)按照它們的坐標(biāo)排列.在區(qū)的上方,由兩個(gè)或多個(gè)吊機(jī)(如圖1)將排在一起的這幾個(gè)板卷按照一定的順序堆放到適合的爐臺(tái)上,依次經(jīng)過:0—裝板卷和對(duì)流板;1—裝內(nèi)罩;2—自然充氣;3—裝加熱罩;4—加熱;5—卸加熱罩;6—自然冷卻;7—裝冷卻罩;8—冷卻;9—卸冷卻罩;10—卸內(nèi)罩;11—卸板卷和對(duì)流板這12個(gè)階段完成對(duì)板卷的罩式退火過程.除第2、4、6和第8階段外,其余都需要吊機(jī)的裝載或卸載操作.當(dāng)加熱罩或冷卻罩被吊機(jī)移動(dòng)時(shí)(第3,5,7,9階段),這兩種罩不能加工工件.因此,加熱罩或冷卻罩的裝載和卸載,必須同時(shí)考慮吊機(jī)和罩的使用.每個(gè)移動(dòng)的操作都由上方的吊機(jī)執(zhí)行.

本文將板卷看做工件、加熱罩和冷卻罩看做工具,提出并分析將工件和工具混合搬運(yùn)的多吊機(jī)調(diào)度問題,同時(shí)考慮分配和調(diào)度有限的加熱罩、冷卻罩以最小化一個(gè)區(qū)內(nèi)工件的最大完工時(shí)間(也就是說,極小化一個(gè)區(qū)內(nèi)最后工件退火完成的時(shí)間).

圖1　罩式退火車間圖例Fig.1　Sample of a block in batch annealing process workshop

近年來,關(guān)于吊機(jī)調(diào)度問題的研究主要集中在電鍍生產(chǎn)線以及港口碼頭的岸吊調(diào)度中,盡管已經(jīng)有相關(guān)文獻(xiàn)進(jìn)行過研究,但很難直接應(yīng)用于鋼鐵企業(yè)吊機(jī)的實(shí)際作業(yè)過程.Philips和Unger[1]首次提出電鍍生產(chǎn)線中的吊機(jī)調(diào)度問題,他們給出了一個(gè)混合整數(shù)規(guī)劃模型以確定單吊機(jī)生產(chǎn)線的最優(yōu)周期.然而,在此之后的近30年,人們一直都在關(guān)注單吊機(jī)調(diào)度,忽略了多吊機(jī)

間的同時(shí)調(diào)度.一個(gè)重要的原因是:多吊機(jī)調(diào)度問題比單吊機(jī)調(diào)度問題更為復(fù)雜,因此研究相對(duì)較少.在實(shí)際中,由于一跨上存在至少兩吊機(jī),所以需要考慮到吊機(jī)分配的決策以避免吊機(jī)之間的交叉和碰撞.對(duì)于兩臺(tái)吊機(jī)的問題,Lei和Wang[2]使用一種zoned方法提出了一種啟發(fā)式算法.考慮了工件必須沿著從裝載站到卸載站一個(gè)方向依次經(jīng)過處理槽的兩臺(tái)吊機(jī)的調(diào)度問題.他們把這條生產(chǎn)線劃分為兩個(gè)互不重疊的區(qū)域,每個(gè)區(qū)域內(nèi)部處理槽中工件的移動(dòng)分配給一個(gè)吊機(jī),通過交替解決兩個(gè)吊機(jī)的問題來確定最優(yōu)排序.Leung等[3]提出了多吊機(jī)的最小化周期調(diào)度的混合整數(shù)規(guī)劃模型,并對(duì)該問題提出了一個(gè)有效不等式,給出了一些初步的計(jì)算結(jié)果.當(dāng)?shù)鯔C(jī)數(shù)目預(yù)先確定,假設(shè)吊機(jī)間不碰撞,Kats和Levner[4]給出了計(jì)算時(shí)間為O(n2logn)的算法以最小化多吊機(jī)排序問題的周期時(shí)間.此外,Daganzo[5]首次提出岸吊調(diào)度,分析了吊機(jī)分配策略對(duì)于最大化終端輸出和預(yù)期車輛延遲的影響,并沒有考慮到吊機(jī)間的相互干涉.Guan等人[6]針對(duì)問題的中小規(guī)模,分別提出拉格朗日松弛方法和帶有不交叉約束的時(shí)間空間網(wǎng)絡(luò)流模型;對(duì)(Guan,2013 #417)大規(guī)模問題,提出兩個(gè)有效的啟發(fā)式算法.Tang等人[7]考慮了兩類設(shè)備的協(xié)調(diào)以減少連續(xù)作業(yè)任務(wù)間的空閑時(shí)間.分析了問題的最優(yōu)性質(zhì)、建立混合整數(shù)規(guī)劃模型、提出有效不等式及兩個(gè)下界,進(jìn)一步提出一個(gè)改進(jìn)的粒子群算法.Kaveshgar和Huynh[8]考慮了集裝箱、場(chǎng)地區(qū)域、吊機(jī)干涉、安全邊界間的優(yōu)先關(guān)系,建立一個(gè)混合整數(shù)規(guī)劃模型,并設(shè)計(jì)了結(jié)合貪婪算法的遺傳算法.有關(guān)罩式退火過程的多吊機(jī)調(diào)度問題,謝和李[9]提出了一類兩階段的啟發(fā)式算法,分別將吊機(jī)和工具進(jìn)行先分配后調(diào)度,并沒有將多吊機(jī)對(duì)工件和工具的搬運(yùn)混合考慮.

結(jié)合上述文獻(xiàn),很少有學(xué)者將吊機(jī)搬運(yùn)過程的多類物件混合調(diào)度,本文主要研究鋼鐵企業(yè)罩式退火過程將板卷(工件)、加熱罩和冷卻罩(工具)混合考慮的吊機(jī)調(diào)度問題,提出了基于工具分配的啟發(fā)式算法,并進(jìn)一步分析了算法的絕對(duì)最壞性能和漸近最壞性能.

1　問題參數(shù)及描述

2　基于工具分配的啟發(fā)式算法及其分析

啟發(fā)式算法的過程將使用下面的工具分配問題的模型:

(1)

(2)

(3)

(4)

(5)

(6)

給定分配問題的可行解,令

由上面可知,每一個(gè)工件工具之間的分配問題的可行解給出了工具f(c)加工工件的順序.吊機(jī)調(diào)度問題在這個(gè)結(jié)果的基礎(chǔ)上,一旦吊機(jī)空閑,選擇距離當(dāng)前需要操作的最近的工件.

令

對(duì)任意的工件工具分配的距離向量d,令

根據(jù)等待時(shí)間,有

和

因此,問題的最優(yōu)目標(biāo)函數(shù)為

根據(jù)分配問題的最優(yōu)性,有

和

引理1給定工件的距離向量d=(d1,d2,…,dn),啟發(fā)式得到的解滿足下面的條件:

定理1表明當(dāng)工件工具的分配給定,這個(gè)算法的絕對(duì)最壞性能比為3.

定理1ZH/Z*≤3.

下面的定理表明問題的漸近最壞性能比是2.

由于M(d0)≤M(d*),因此,

3　數(shù)值實(shí)驗(yàn)與計(jì)算結(jié)果

在這部分中,我們對(duì)基于工具分配的啟發(fā)式算法進(jìn)行實(shí)驗(yàn)以檢驗(yàn)其有效性.這個(gè)算法由C語言編程,在Pentium-Ⅳ的PC機(jī)上運(yùn)行,操作系統(tǒng)是Windows XP,CPU是2.40 GHz.根據(jù)罩式退火過程的實(shí)際生產(chǎn),測(cè)試問題所用到的參數(shù)利用以下方式隨機(jī)產(chǎn)生.

工件的數(shù)目(n):15,25,55,85,100,200;

加熱罩的數(shù)目(|F|)和冷卻罩的數(shù)目(|C|):在[10,200]之間離散平均分布隨機(jī)生成;

裝載移動(dòng)速度(v),空移動(dòng)速度(λ),提起和下放的時(shí)間(μ):在[1,5]之間離散平均分布隨機(jī)生成,此計(jì)算實(shí)例中,取v=1,λ=2,μ=1;

計(jì)算結(jié)果表明算法最多在15 s的CPU時(shí)間內(nèi)求得問題的近優(yōu)解.從表中可以看出算法的偏差隨著工件數(shù)量的增多,即問題規(guī)模的增大,偏差逐漸減小,但最大的偏差也不超過2,尤其是當(dāng)問題規(guī)模增加到n=100時(shí),偏差明顯減小,當(dāng)n=200時(shí)偏差值已小于1.進(jìn)一步驗(yàn)證了算法的絕對(duì)最壞性能比和漸近最壞性能比.此外,隨著加熱時(shí)間和冷卻時(shí)間的增加,吊機(jī)調(diào)度對(duì)偏差的影響也逐漸減小.當(dāng)工件的數(shù)目n越接近|F|和|C|時(shí),算法的性能越好.這可以解釋當(dāng)需要加工的工件增多時(shí),機(jī)器就變成了瓶頸設(shè)備.計(jì)算實(shí)驗(yàn)表明吊機(jī)與工具的分配并協(xié)調(diào)調(diào)度有利于平衡最大完工時(shí)間和設(shè)備的利用率.

表1　基于工具分配的啟發(fā)式算法性能計(jì)算實(shí)驗(yàn)結(jié)果

4　結(jié)　　論

本文研究了罩式退火過程中多吊機(jī)混合搬運(yùn)工件與工具的調(diào)度問題以最小化最大完工時(shí)間.針對(duì)這個(gè)強(qiáng)NP-難問題,提出一個(gè)基于工具分配的啟發(fā)式算法,并對(duì)該算法的最壞性能和漸進(jìn)最壞性能進(jìn)行了分析.根據(jù)問題的實(shí)際參數(shù)測(cè)試算法的計(jì)算性能表明,本文的研究適合解決混合搬運(yùn)各種吊件進(jìn)行多階段生產(chǎn)的、避免碰撞的多吊機(jī)調(diào)度問題.除了罩式退火過程可以應(yīng)用這個(gè)研究解決外,本章的研究在考慮具體的實(shí)施細(xì)節(jié)時(shí),可以擴(kuò)展到鋼鐵企業(yè)煉鋼連鑄、連鑄精煉中的部分生產(chǎn)過程.

[1] PHILLIPS L W,UNGER P S. Mathematical programming solution of a hoist scheduling problem[J]. IIE Transactions, 1976,8(2):219-225.

[2] LEI L,WANG T J. The minimum common-cycle algorithm for cyclic scheduling of two material handling hoists with time window constraints[J]. Management Science, 1991,37(12):1629-1639.

[3] LEUNG J M Y,ZHANG G Q,YANG X G,et al. Optimal cyclic multi-hoist scheduling:a mixed integer programming approach[J]. Operations Research, 2004,52(6):965-976.

[4] KATS V,LEVNER E. Cyclic scheduling in a robotic production line[J]. Journal of Scheduling, 2002,5(1):23-41.

[5] DAGANZO C F. The crane scheduling problem[J]. Transportation Research Part B Methodological, 1989,23(3):159-175.

[6] GUAN Y P,YANG K H,ZHOU Z L. The crane scheduling problem:models and solution approaches[J]. Annals of Operations Research, 2013,203(1):119-139.

[7] TANG L X,ZHAO J,LIU J Y. Modeling and solution of the joint quay crane and truck scheduling problem[J]. European Journal of Operational Research, 2014,236(3):978-990.

[8] KAVESHGAR N,HUYNH N. Integrated quay crane and yard truck scheduling for unloading inbound containers [J]. International Journal of Production Economics, 2015,159(3):168-177.

[9] 謝謝,李彥平. 罩式退火過程中的多吊機(jī)調(diào)度問題[J]. 沈陽大學(xué)校報(bào)(自然科學(xué)版), 2012,24(1):12-19.

(XIE X,LI Y P. Multi-crane scheduling in batch annealing process[J]. Journal of Shenyang University( Natural Science), 2012,24(1):12-19.)

【責(zé)任編輯: 李艷】

Job and Tool Mixed Transportation Based Multi-Crane Scheduling Problem

XieXie1,ZhengYongyue2,LiYanping1

(1. Key Laboratory of Manufacturing Industrial and Integrated Automation, Shenyang University, Shenyang 110044, China; 2. Liaoning Institute of Standardization, Shenyang 110044, China)

A job and tool mixed transportation based multi-crane scheduling problem is studied for solving batch annealing processing in the iron and steel enterprises. The objective is to minimize the makespan. For the demonstrated NP-hard problem, a tool assigned based heuristic algorithm is proposed. The heuristic is analyzed from an absolute worst-case performance ratio of 3 and an asymptotic worst-case performance ratio is 2 respectively. The average performance of the solution approach is computationally evaluated. The results show that the proposed heuristic algorithm is capable of generating good quality solutions for large-scale problem.

scheduling; batch annealing process; absolute worst-case performance; asymptotic worst-case performance

2015-11-19

國家自然科學(xué)基金資助項(xiàng)目(71201104); 遼寧省高等學(xué)校杰出青年學(xué)者成長(zhǎng)計(jì)劃資助項(xiàng)目(LJQ2014133).

謝謝(1981-),女,遼寧沈陽人,沈陽大學(xué)副教授,博士; 李彥平(1958-),男,遼寧沈陽人,沈陽大學(xué)教授,博士.

2095-5456(2016)04-0291-06

TP 301.6

A