謝 謝, 鄭勇躍

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

?

帶有機(jī)器卸載不延誤約束的多吊機(jī)調(diào)度問題

謝 謝1, 鄭勇躍2

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

針對(duì)鋼鐵企業(yè)冷軋階段罩式退火過程,考慮了一類帶有機(jī)器卸載不延誤約束的多吊機(jī)調(diào)度問題.給出了避免吊機(jī)碰撞和保證機(jī)器卸載不延誤的一些可行性質(zhì).基于這些性質(zhì),提出了一個(gè)啟發(fā)式算法,該算法的計(jì)算復(fù)雜性與吊機(jī)、工件和機(jī)器的數(shù)目有關(guān).同時(shí),給出了問題的一個(gè)下界.分別通過理論分析和計(jì)算實(shí)驗(yàn),證明了啟發(fā)式算法的最壞性能和平均性能.

罩式退火過程; 吊機(jī)調(diào)度; 強(qiáng)NP難; 啟發(fā)式算法; 最壞性能分析

鋼鐵企業(yè)的冷軋生產(chǎn)的罩式退火過程是冷軋板卷后道工序生產(chǎn)的常見的模式,經(jīng)過該過程可以生產(chǎn)出高附加值的產(chǎn)品.每垛板卷預(yù)先放在一個(gè)固定的爐臺(tái)上進(jìn)行兩階段處理.第一階段為加熱,第二階段為冷卻.一臺(tái)加熱機(jī)器(加熱罩)和一臺(tái)冷卻機(jī)器(冷卻罩)被移動(dòng)到這個(gè)工件的位置依次進(jìn)行加熱操作和冷卻操作.為了方便描述,每垛板卷定義為一個(gè)工件.不同于經(jīng)典的兩階段流水作業(yè)的問題,每個(gè)工件需要通過兩臺(tái)固定機(jī)器,這個(gè)過程如圖1所示.機(jī)器的移動(dòng)都由上方移動(dòng)的吊機(jī)實(shí)施.一旦一臺(tái)機(jī)器(加熱罩或冷卻罩)被裝載到工件上,加工(加熱或冷卻)立即開始.當(dāng)加工達(dá)到一個(gè)預(yù)設(shè)的值(加熱時(shí)間或冷卻時(shí)間),機(jī)器必須被立刻卸載以停止進(jìn)一步的加工.也就是說,第一階段一旦板卷溫度達(dá)到設(shè)定值,加熱罩必須移走以停止加工.類似的,第二階段一旦板卷溫度降低到某設(shè)定值,冷卻罩必須移走以停止加工.任何機(jī)器卸載額外的延遲都會(huì)導(dǎo)致工件質(zhì)量的不足.因此,機(jī)器卸載不延誤約束對(duì)于增加鋼鐵企業(yè)機(jī)器利用率、改進(jìn)生產(chǎn)率能量利用率、降低生產(chǎn)費(fèi)用非常關(guān)鍵.可以通過有效的生產(chǎn)計(jì)劃和調(diào)度來實(shí)現(xiàn).

圖1 罩式退火過程

然而,同一工件兩階段加工之間沒有時(shí)間限制.當(dāng)冷卻罩從工件上卸載,意味著工件退火過程的結(jié)束.由吊機(jī)將機(jī)器從一個(gè)位置移動(dòng)到另一個(gè)位置稱為吊機(jī)的裝載移動(dòng).一個(gè)裝載移動(dòng)包括從機(jī)器的位置提起它,移動(dòng)到另一個(gè)位置后將它放下.實(shí)施裝載移動(dòng)的操作后,吊機(jī)需要空移動(dòng)到一個(gè)適合的位置實(shí)施下一個(gè)裝載移動(dòng).顯然,吊機(jī)負(fù)責(zé)將機(jī)器從一個(gè)工件移動(dòng)到另一個(gè)工件保證對(duì)工件進(jìn)行每階段的加工.因此,罩式退火系統(tǒng)的生產(chǎn)率大大依賴于有效的吊機(jī)調(diào)度.

實(shí)際生產(chǎn)中罩式退火車間的爐臺(tái)按列排好,每列具有相同數(shù)目的爐臺(tái),均勻地位于其中.一個(gè)爐臺(tái)的位置可以獨(dú)一無二地使用它的列號(hào)(x坐標(biāo))和行號(hào)(y坐標(biāo))表示.圖2給出了罩式退火車間的俯視圖,圖中各吊機(jī)共用一個(gè)相同的跨.一個(gè)吊機(jī)的橋可以沿著跨到達(dá)不同的列,吊鉤可以沿著橋移動(dòng)到每一列中不同的位置.這樣的結(jié)構(gòu)使得吊機(jī)間不能彼此相互跨越.在任意兩個(gè)相鄰吊機(jī)之間有一個(gè)最小安全距離的要求以避免兩相鄰吊機(jī)之間可能的碰撞.因此,同一列中的爐臺(tái)不能由兩個(gè)或多個(gè)吊機(jī)同時(shí)服務(wù).本文研究的是具有機(jī)器卸載不延誤約束(固定的加熱和冷卻時(shí)間)和吊機(jī)之間不碰撞的多吊機(jī)調(diào)度問題.這個(gè)問題包括分配和調(diào)度兩種機(jī)器以加工工件和調(diào)度吊機(jī)在工件之間移動(dòng)工件.目標(biāo)為最小化車間內(nèi)最后一個(gè)工件的完工時(shí)間.

圖2 罩式退火車間的俯視圖

本文所研究的問題考慮了罩式退火系統(tǒng)中吊機(jī)調(diào)度和機(jī)器分配的組合.已有的有關(guān)罩式退火過程中吊機(jī)調(diào)度的研究主要是決策單吊機(jī)調(diào)度.然而,Catherine等人[1], Moon和Hrymak[2],Liu等人[3]并沒有考慮吊機(jī)移動(dòng)的細(xì)節(jié)以及調(diào)度過程中每個(gè)機(jī)器的具體位置.由于任何延誤時(shí)間都會(huì)導(dǎo)致產(chǎn)品密度和韌性的改變,本文研究的是機(jī)器卸載不延誤約束的生產(chǎn)模式.此外,在這個(gè)鋼鐵的退火系統(tǒng)中即使不考慮機(jī)器卸載不延誤約束,Tang等人[4]研究了單吊機(jī)調(diào)度問題,Xie和Tang[5]以及謝和李[6]研究了多吊機(jī)調(diào)度問題,其中,Xie和Tang[5]致力于考慮機(jī)器預(yù)先分配的問題,然而,并沒有對(duì)多吊機(jī)操作進(jìn)行理論分析.謝和李[6]并沒有考慮機(jī)器卸載不延誤約束的多吊機(jī)調(diào)度問題.為避免吊機(jī)干涉使用同樣的方法鑒別問題的可行性質(zhì)和最優(yōu)性質(zhì),Xie等人[7]對(duì)鋼卷倉庫內(nèi)的多吊機(jī)調(diào)度問題進(jìn)行了研究,謝和李[8]考慮了運(yùn)輸與倒垛集成的多吊機(jī)調(diào)度問題.然而現(xiàn)有文章幾乎很少考慮本文研究的問題,文獻(xiàn)[9-10]考慮了本文所研究問題的簡化版本,但他們忽略了吊機(jī)沿跨和橋移動(dòng)時(shí)的裝載移動(dòng)和空載移動(dòng).此外,他們沒有給出問題的數(shù)學(xué)模型,算法的最壞性能界也僅和吊機(jī)工件的數(shù)目有關(guān),而和吊機(jī)移動(dòng)時(shí)間無關(guān),本文改進(jìn)了該界.盡管Tang等人[11]的研究和罩式退火過程相關(guān),但主要考慮的是分批問題而不是吊機(jī)的調(diào)度過程.因此,大部分研究的方法不能直接應(yīng)用于罩式退火過程中機(jī)器卸載不延誤的多吊機(jī)調(diào)度,很有必要研究這類新的吊機(jī)調(diào)度問題.

1 問題的定義和描述

給定n個(gè)需要加工工件的集合Ω={1,2,…,n},每個(gè)工件已經(jīng)放在了固定的爐臺(tái)上.工件i的位置為wi,這個(gè)位置可以由它所在爐臺(tái)的位置、車間中獨(dú)一無二的坐標(biāo)(xi,yi)表示.用R表示車間中列的集合,從左至右沿著x軸依次標(biāo)號(hào)1,2,…, |R|,因此工件的集合可以分成|R|個(gè)子集Ω1,Ω2, …,Ω|R|,其中Ωr為列r中的工件集合.令L表示每個(gè)列中爐臺(tái)的個(gè)數(shù),如圖2所示,以|R|=10和L=3為例的車間俯視圖.將處在同一y軸的工件表示為(?,yi),同一x軸的工件表示為(xi,?).相鄰兩列之間的距離以及同一列中相鄰爐臺(tái)之間的距離為d.定義吊機(jī)的位置是它的吊鉤向地面投影的位置.如果機(jī)器正在加工工件,它的位置就是這個(gè)工件的位置.否則,它的位置為與它距離最近的工件的位置.所有的工件、機(jī)器和吊機(jī)從0時(shí)刻可獲得.

為了便于參閱,將上文提到的全部符號(hào)排列如下,一些需要進(jìn)一步使用的符號(hào)將在需要的時(shí)候給予定義.

Ω—需要加工工件的集合;

n—需要加工工件的數(shù)量;

wi—工件i的位置,也可以用坐標(biāo)(xi,yi)表示;

R—車間中列的集合,從左至右延著x軸依次標(biāo)號(hào)1, 2, …, |R|;

Ωr—列r中的工件集合;

L—每個(gè)列中爐臺(tái)的個(gè)數(shù);

d—相鄰兩列之間的距離以及同一列中相鄰爐臺(tái)之間的距離;

M—機(jī)器的集合M={1, 2, …,|F|,|F|+1, …,|F|+|C|},包括|F|個(gè)相同的加熱罩以及|C|個(gè)相同的冷卻罩;

pi1和pi2—每個(gè)工件i(i∈Ω)的加熱和冷卻時(shí)間;

H—吊機(jī)的集合;

μ—上提時(shí)間和下放時(shí)間;

v1和v2—吊機(jī)沿跨移動(dòng)和沿跨間移動(dòng)的速度;

λ1和λ2—吊機(jī)沿跨移動(dòng)和沿跨間空移動(dòng)的速度,其中(λ1≥v1),(λ2≥v2);

2 可行解的性質(zhì)

2.1 吊機(jī)分配不碰撞約束

根據(jù)吊機(jī)所在位置以及吊機(jī)間安全距離的要求,如果一個(gè)工件在車間中某列且距離最左側(cè)位置的距離小于d,則這列中的全部工件僅可由吊機(jī)1服務(wù).類似地,如果一個(gè)工件在車間中某列且距離最左側(cè)位置的距離小于2d,則這列中的工件僅可由吊機(jī)1或2服務(wù).因此令Xi(1≤Xi≤|H|)表示服務(wù)于工件i的吊機(jī)號(hào)(?i∈Ω),可得到如下性質(zhì).

(1)

類似地,根據(jù)跨最右側(cè)的位置(xl,·),吊機(jī)的分配決策有如下表達(dá):

(2)

性質(zhì)2 為避免吊機(jī)在相鄰兩列的沖突,對(duì)于任意的r∈R,i∈Ωr,i′,j∈Ωr+1,兩吊機(jī)h,h+1∈H操作的情況如下:

情況1(見圖3a) 可行操作滿足以下安全距離的要求:當(dāng)?shù)鯔C(jī)h完成對(duì)列Ωr中工件i的裝載操作后,空移動(dòng)到列Ωr+1中對(duì)工件i′操作的時(shí)間不早于吊機(jī)h+1完成對(duì)列Ωr+1中工件j的裝載操作.因此,一定有

(3)

情況2(見圖3b) 可行操作滿足以下安全距離的要求: 當(dāng)?shù)鯔C(jī)h開始從列Ωr中工件i到列Ωr+1中工件i′裝載操作的時(shí)間不早于吊機(jī)h+1完成對(duì)列Ωr+1中工件j的裝載操作. 因此, 一定有

(4)

情況3(見圖3c) 可行操作滿足以下安全距離的要求:當(dāng)?shù)鯔C(jī)h完成對(duì)列Ωr中工件i的裝載操作后,空移動(dòng)到列Ωr+1中對(duì)工件i′操作的時(shí)間不早于吊機(jī)h+1開始對(duì)列Ωr+1中工件j的裝載操作.因此,一定有

(5)

情況4(見圖3d) 可行操作滿足以下安全距離的要求:當(dāng)?shù)鯔C(jī)h開始從列Ωr中工件i到列Ωr+1中工件i′裝載操作的時(shí)間不早于吊機(jī)h+1開始對(duì)列Ωr+1中工件j的裝載操作.因此,一定有

(6)

圖3 相鄰列中避免吊機(jī)沖突的說明

性質(zhì)3 為避免吊機(jī)在同列中的沖突,對(duì)任意r∈R,i,i′,j∈Ωr相鄰吊機(jī)h,h+1∈H操作的各情況如下:

情況1(見圖4a) 對(duì)任意同列中的工件i,i′和j,可行操作滿足安全距離的要求,當(dāng)?shù)鯔C(jī)h+1開始從工件i′到工件i裝載的開始時(shí)間不早于吊機(jī)h從工件j裝載的開始時(shí)間,一定有

(7)

情況2(見圖4b) 對(duì)任意同列中的工件i,i′和j,可行操作滿足安全距離的要求,當(dāng)?shù)鯔C(jī)h+1開始從工件i′空移動(dòng)之后對(duì)工件i完成裝載移動(dòng)的時(shí)間不早于吊機(jī)h從工件j裝載的開始時(shí)間,一定有

(8)

圖4 同列中避免吊機(jī)沖突的說明

情況3(見圖4c) 對(duì)任意同列中的工件i,i′和j,可行操作滿足安全距離的要求,當(dāng)?shù)鯔C(jī)h+1開始從工件i′到工件i裝載的開始時(shí)間不早于吊機(jī)h對(duì)工件j完成裝載移動(dòng)的時(shí)間,一定有

(9)

情況4(見圖4d) 對(duì)任意同列中的工件i,i′和j,可行操作滿足安全距離的要求,當(dāng)?shù)鯔C(jī)h+1開始從工件i′空移動(dòng)之后對(duì)工件i完成裝載移動(dòng)的時(shí)間不早于吊機(jī)h對(duì)工件j裝載移動(dòng)的完成時(shí)間,一定有

(10)

2.2 機(jī)器卸載不延誤約束

為了保證機(jī)器卸載不延誤約束,下面的性質(zhì)分別針對(duì)吊機(jī)為同一列和不同列中工件卸載機(jī)器的時(shí)間要求.

性質(zhì)4 如果同一列中的兩工件i和j同時(shí)需要吊機(jī)卸載機(jī)器,則兩個(gè)工件某一操作(加熱或冷卻)的完工時(shí)間之差不能少于

(11)

性質(zhì)5 如果不同列中的兩工件i和j同時(shí)需要吊機(jī)卸載機(jī)器,則兩個(gè)工件某一操作(加熱或冷卻)的完工時(shí)間之差不能少于

(12)

3 啟發(fā)式算法

根據(jù)工件i (i∈Ω)兩階段加工時(shí)間的總和pi1+pi2非增排序,形成列表JList;

只要列表JList不空,算法如下進(jìn)行

{

如果機(jī)器可獲得且存在未完成退火過程的工件,則為工件分配吊機(jī)操作當(dāng)前可獲得的盡可能多的機(jī)器;

如果存在一臺(tái)可獲得的吊機(jī),且兩個(gè)或更多需要吊機(jī)同時(shí)操作為其裝載的工件,則選擇可以最早開始加工的工件(選擇距離吊機(jī)當(dāng)前距離最近的工件);

如果存在兩個(gè)或更多需要吊機(jī)同時(shí)裝載或卸載機(jī)器,則優(yōu)先分配給需要卸載的機(jī)器以完成加工的工件;

如果如果兩個(gè)或多個(gè)吊機(jī)空閑同時(shí)可利用,則選擇具有最短總距離(如果工件正在加工則總距離為吊機(jī)從當(dāng)前位置到該工件的距離;如果工件正等待機(jī)器,則總距離為吊機(jī)從當(dāng)前位置到機(jī)器再到工件的距離)的吊機(jī); 否則根據(jù)性質(zhì)1即公式(1)、(2)檢驗(yàn)當(dāng)前分配的吊機(jī)編碼是否在可行范圍內(nèi);進(jìn)一步為避免吊機(jī)沖突,根據(jù)性質(zhì)2即公式(3)～公式(6),性質(zhì)3即公式(7)～公式(10)分別檢驗(yàn)相鄰兩列和同一列中工件在每種情況下的可行性;

如果可行,則構(gòu)建吊機(jī)排序;

否則,交換吊機(jī)間的操作,或一臺(tái)吊機(jī)等待直到另一臺(tái)吊機(jī)完成當(dāng)前操作;

否則為保證機(jī)器卸載不延誤約束,根據(jù)性質(zhì)4即公式(11)和性質(zhì)5即公式(12)分別檢驗(yàn)同列和不同列的每種可行性;

如果可行,則構(gòu)建吊機(jī)排序;

否則,交換吊機(jī)間的操作,或一臺(tái)吊機(jī)等待直到另一臺(tái)吊機(jī)完成當(dāng)前操作;

否則,一旦相同,選擇當(dāng)前需要最長加工時(shí)間的工件;

否則,刪除退火完成的工件;

}

結(jié)束

工件初始化的排序耗時(shí)時(shí)間O(nlogn).為避免吊機(jī)沖突,檢驗(yàn)可行的吊機(jī)操作時(shí)間為O(n|H|).為保證機(jī)器卸載不延誤約束,檢驗(yàn)可行加熱罩和冷卻罩的操作最多耗時(shí)分別為O(n2|H||F|)和O(n2|H||C|),因此,啟發(fā)式算法的復(fù)雜度為O(n3|H|(|F|+|C|)).

4 最壞情況分析

為了分析算法的最壞性能比,首先提出了下界.由于幾個(gè)下界之間互相補(bǔ)充,沒有一個(gè)能代替另一個(gè).進(jìn)一步采用復(fù)合下界的策略,使得到的問題的下界可以更接近最優(yōu)值.分析了問題啟發(fā)式的最壞性能,也根據(jù)機(jī)器數(shù)目不同的三種情況得到了三個(gè)界.

性質(zhì)6 問題的下界LB可由下面的三個(gè)表達(dá)式獲得:

其中,LB=max{LB1, LB2, LB3}.

于是有

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

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

吊機(jī)的數(shù)目(|H|):2;

工件的數(shù)目(n):9=3×3,15=3×5,18=3×6,20=4×5,24=4×6,30=5×6;

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

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

兩相鄰爐臺(tái)間的距離(d):在[1,10]之間離散平均分布隨機(jī)生成,此計(jì)算實(shí)例中,取d=4;由此可計(jì)算任意兩工件之間裝載移動(dòng)時(shí)間tij和空移動(dòng)時(shí)間eij.

工件的加熱時(shí)間(pi1)和冷卻時(shí)間(pi2):分別在[1,10]、[1,30]、[1,50]和[1,100]之間離散平均分布隨機(jī)生成;

表1 啟發(fā)式算法性能計(jì)算實(shí)驗(yàn)結(jié)果

數(shù)值計(jì)算結(jié)果表明,當(dāng)加熱罩冷卻罩的數(shù)量越充足,啟發(fā)式得到的平均偏差越小,這是因?yàn)闇p少了吊機(jī)、工件不必要的等待時(shí)間.此外,加熱時(shí)間和冷卻時(shí)間越短,便于越早的釋放這兩類加工機(jī)器,使得可利用的機(jī)器數(shù)量充足,同樣啟發(fā)式得到的偏差也減少.可以解釋為加熱罩、冷卻罩為兩類瓶頸設(shè)備.因此有效的吊機(jī)調(diào)度可以優(yōu)化這兩類設(shè)備的使用,從而提高生產(chǎn)率和客戶滿意度.

6 結(jié) 論

本文研究一類罩式退火過程中機(jī)器卸載不延誤的多吊機(jī)調(diào)度問題.分析了問題的可行性質(zhì)以避免吊機(jī)沖突以及保證了機(jī)器卸載的不延誤,進(jìn)一步提出一個(gè)啟發(fā)式算法并進(jìn)行了最壞情況分析.未來的研究中,將繼續(xù)考慮鋼鐵企業(yè)其他相 似生產(chǎn)背景中,如罩式退火操作、連續(xù)退火操作和熱鍍鋅過程的吊機(jī)調(diào)度、以及吊機(jī)與其他運(yùn)輸工具的聯(lián)合運(yùn)輸.

[ 1 ] AZZARO-PANTEL C, BERNAL-HARO L, BAUDET P, et al. A two-stage methodology for short-term batch plant scheduling: discrete-event simulation and generic algorithm[J]. Computers & Chemical Engineering, 1998,22(10):1461-1481.

[ 2 ] MOON S, HRYMAK A N. Scheduling of the batch annealing process: deterministic case[J]. Computers & Chemical Engineering, 1999,23(9):1193-1208.

[ 3 ] LIU Q L, WANG W, ZHAN H R, et al. Optimal scheduling method for bell-type batch annealing shop and its application[J]. Control Engineering Practice, 2005,13(10):1315-1325.

[ 4 ] TANG L X, XIE X, LIU J Y. Scheduling of a single crane in batch annealing process[J]. Computers & Operations Research, 2009,36(10):2853-2865.

[ 5 ] XIE X, TANG L X. Crane scheduling in batch annealing process[C]∥Proceedings of the IEEE International Conference on Automation and Logistics, 1-3 Sept, 2008, Qingdao. IEEE, 2008:2020-2025.

[ 6 ] 謝謝,李彥平. 罩式退火過程中的多吊機(jī)調(diào)度問題[J]. 沈陽大學(xué)學(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.)

[ 7 ] XIE X, ZHENG Y Y, LI Y P. Multi-crane scheduling in steel coil warehouse[J]. Expert Systems with Applications, 2014,41(6):2874-2885.

[ 8 ] 謝謝,李彥平. 運(yùn)輸與倒垛集成的多吊機(jī)調(diào)度問題[J]. 沈陽大學(xué)學(xué)報(bào)(自然科學(xué)版), 2014, 26(3):210-217. (XIE X, LI Y P. Coordinate transportation and shuffling operations in multi-crane scheduling problem[J]. Journal of Shenyang University(Natural Science), 2014,26(3):210-217.)

[ 9 ] XIE X, KONG X Y, ZHENG Y Y, et al. A heuristic algorithm for solving multi-crane scheduling problem in batch annealing process[J]. Applied Mechanics and Materials, 2014,620:179-182.

[10] XIE X, LI Y P, ZHENG Y Y. Multiple crane scheduling in batch annealing process with no-delay constraints for machine unloading[C]∥IEEE International Conference on Information and Automation, 6-8 June, 2012, Shenyang. IEEE, 2012:597-601.

[11] TANG L X, MENG Y, CHEN Z L, et al. Coil batching to improve productivity and energy utilization in steel production[J]. Manufacturing & Service Operations Management, 2015,18(2):1-18.

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

Multiple Crane Scheduling with No-Delay Constraints for Machine Unloading

XieXie1,ZhengYongyue2

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

Aiming at the problem that arises in the batch annealing process in the cold rolling stage of steel production, a multiple crane scheduling problem with no-delay constraints for machine unloading is studied. Some feasible properties are identified to avoid crane collisions and guarantee machine unloading no-delay constraints. Based on these necessary conditions, a heuristic algorithm with running time in connection with the number of cranes, coils and machines is presented. A lower bound to the problem is also developed. Through the theoretically analysis and computational experiments, the worst case bound and the average performance of the heuristic algorithm are proved.

batch annealing process; crane scheduling; strongly NP-hard; heuristic algorithm; worst case analysis

2016-11-28

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

謝 謝(1981-),女,遼寧沈陽人,沈陽大學(xué)副教授,博士.

2095-5456(2017)02-0118-07

TP 301.6

A