謝 謝, 鄭勇躍

(1. 沈陽大學 裝備制造綜合自動化重點實驗室, 遼寧 沈陽 110044; (2. 遼寧省標準化研究院, 遼寧 沈陽 110004)

?

帶有機器卸載不延誤約束的多吊機調度問題

謝 謝1, 鄭勇躍2

(1. 沈陽大學 裝備制造綜合自動化重點實驗室, 遼寧 沈陽 110044; (2. 遼寧省標準化研究院, 遼寧 沈陽 110004)

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

罩式退火過程; 吊機調度; 強NP難; 啟發(fā)式算法; 最壞性能分析

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

圖1 罩式退火過程

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

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

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

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

1 問題的定義和描述

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

為了便于參閱,將上文提到的全部符號排列如下,一些需要進一步使用的符號將在需要的時候給予定義.

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

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

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

R—車間中列的集合,從左至右延著x軸依次標號1, 2, …, |R|;

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

L—每個列中爐臺的個數(shù);

d—相鄰兩列之間的距離以及同一列中相鄰爐臺之間的距離;

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

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

H—吊機的集合;

μ—上提時間和下放時間;

v1和v2—吊機沿跨移動和沿跨間移動的速度;

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

2 可行解的性質

2.1 吊機分配不碰撞約束

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

(1)

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

(2)

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

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

(3)

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

(4)

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

(5)

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

(6)

圖3 相鄰列中避免吊機沖突的說明

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

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

(7)

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

(8)

圖4 同列中避免吊機沖突的說明

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

(9)

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

(10)

2.2 機器卸載不延誤約束

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

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

(11)

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

(12)

3 啟發(fā)式算法

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

只要列表JList不空,算法如下進行

{

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

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

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

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

如果可行,則構建吊機排序;

否則,交換吊機間的操作,或一臺吊機等待直到另一臺吊機完成當前操作;

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

如果可行,則構建吊機排序;

否則,交換吊機間的操作,或一臺吊機等待直到另一臺吊機完成當前操作;

否則,一旦相同,選擇當前需要最長加工時間的工件;

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

}

結束

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

4 最壞情況分析

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

性質6 問題的下界LB可由下面的三個表達式獲得:

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

于是有

5 數(shù)值計算實驗與結果

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

吊機的數(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]之間離散平均分布隨機生成;

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

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

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

表1 啟發(fā)式算法性能計算實驗結果

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

6 結 論

本文研究一類罩式退火過程中機器卸載不延誤的多吊機調度問題.分析了問題的可行性質以避免吊機沖突以及保證了機器卸載的不延誤,進一步提出一個啟發(fā)式算法并進行了最壞情況分析.未來的研究中,將繼續(xù)考慮鋼鐵企業(yè)其他相 似生產背景中,如罩式退火操作、連續(xù)退火操作和熱鍍鋅過程的吊機調度、以及吊機與其他運輸工具的聯(liá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]. 沈陽大學學報(自然科學版), 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 ] 謝謝,李彥平. 運輸與倒垛集成的多吊機調度問題[J]. 沈陽大學學報(自然科學版), 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.

【責任編輯: 李 艷】

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

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

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

2095-5456(2017)02-0118-07

TP 301.6

A