鋼卷倉庫中多吊機調(diào)度問題的模型與算法

謝 謝, 周 莉, 鄭勇躍

(1. 沈陽大學(xué) 裝備制造綜合自動化重點實驗室, 遼寧 沈陽 110044;2. 中國標(biāo)準(zhǔn)化研究院 社會信用研究室, 北京 100191;3. 遼寧省檢驗檢測認(rèn)證中心 事業(yè)發(fā)展中心, 遼寧 沈陽 110032)

在傳統(tǒng)的制造過程中,人們往往只注重生產(chǎn)設(shè)備的加工及流程優(yōu)化.對于國民經(jīng)濟具有支柱性的鋼鐵工業(yè)具有生產(chǎn)周期長,資源和能源消耗大,生產(chǎn)成本高的特點.鋼鐵工業(yè)生產(chǎn)的各個工序之間都存在著各類運輸問題:鋼鐵工業(yè)中煉鐵前原料場需要吊機運輸各類原料物資;煉鐵與煉鋼之間需要吊機、魚雷車、臺車等進行運輸;煉鋼環(huán)節(jié)需要吊機運輸鐵水和廢鋼;煉鋼到連鑄之間的鋼水需要用吊機和臺車銜接進行運輸;熱軋階段板坯和冷軋工序中的板卷都需要吊機和臺車、汽車進行聯(lián)合運輸?shù)?如圖1.在各類生產(chǎn)環(huán)節(jié)中,吊機是一類大型、重要的銜接設(shè)備,它啟動成本高,運輸只能在特定的軌道上,由于鋼鐵工業(yè)中的被運件多數(shù)都具有溫度高、單價大、各工序的送達時間由于連續(xù)運作而要求苛刻的特點,因此,鋼鐵工業(yè)通過吊機進行運輸及裝卸操作是最重要的環(huán)節(jié).有效地對吊機進行協(xié)調(diào),將有助于降低能耗、提高生產(chǎn)設(shè)備和其他各類運輸工具的效率、保障實時性要求和生產(chǎn)的順利進行.

圖1 鋼鐵工業(yè)物流的總體結(jié)構(gòu)Fig.1 Structure of logistic in steel industry

本文從鋼鐵工業(yè)冷軋后庫提煉出一類多吊機調(diào)度問題,軋制后(冷軋或熱軋)的板卷由卡車運輸,再由吊機根據(jù)客戶或訂單的需求將板卷放在倉庫內(nèi)的指定位置.圖2給出了多個吊機同時操作一臺卡車的圖示.每臺吊機架設(shè)在倉庫區(qū)域上方的軌道上,吊機可以沿軌道方向、沿軌道之間的跨間來回移動,同時吊鉤可以在垂直地面的方向上下移動.在倉庫內(nèi)吊機或者從卡車將板卷放置在倉庫指定區(qū)域內(nèi),或者根據(jù)客戶訂單的需求從倉庫區(qū)域裝載到卡車上.吊機完成指定部分的工作量后,會接著等待下一個任務(wù).如果沒有進一步的作業(yè),吊機將等待在它們現(xiàn)在的位置.當(dāng)卡車上的板卷裝卸完,卡車就離開倉庫.我們的目的是決策每個吊機的調(diào)度路線以卸載卡車上的所有板卷.

吊機調(diào)度問題是近年來的熱點研究方向,相關(guān)研究的背景主要集中在港口集裝箱碼頭、電鍍生產(chǎn)線以及鋼鐵企業(yè)中.不同背景下的吊機運行方式類似,即這類大型貴重設(shè)備都架設(shè)在軌道上,同一軌道上的相鄰兩吊機必須保證安全距離,彼此之間不能交叉跨越.Daganzo[1]首次研究了港口碼頭的吊機調(diào)度問題,建立了數(shù)學(xué)模型,然而并沒有考慮吊機間的不碰撞.Bierwirth等[2-3]研究了有關(guān)港口集裝箱碼頭吊機調(diào)度問題的分類.此外,一些學(xué)者研究了吊機與其他運輸工具聯(lián)合作業(yè)的集成調(diào)度問題,Zhen[4]等針對兩類吊機的集成調(diào)度問題建立了數(shù)學(xué)模型和啟發(fā)式算法.在鋼鐵企業(yè)中對吊機調(diào)度問題的研究相對較少.謝謝等[5]研究了板坯倉庫中的單吊機調(diào)度問題,并對該問題提出一個混合亞啟發(fā)式算法求解.有關(guān)多吊機調(diào)度問題,謝謝等研究了雙吊機[6]和多吊機[7]調(diào)度問題.盡管研究了多吊機調(diào)度問題,求解的算法也僅對算法的性能從理論分析的角度給出評價,很少對多吊機調(diào)度問題建模并求解,也很少提出基于分散搜索的智能優(yōu)化算法.

圖2 鋼卷倉庫吊機調(diào)度示意圖Fig.2 Diagram of crane scheduling in steel coil warehouse

本文建立了求解鋼卷倉庫多吊機調(diào)度問題的一個數(shù)學(xué)模型,模型中考慮了吊機間不碰撞的約束,證明了問題的復(fù)雜性,進一步分析了問題的性質(zhì),并提出一個基于分散搜索的啟發(fā)式算法,并給出了數(shù)值計算結(jié)果,數(shù)值計算實例證明所提出的模型和算法可以應(yīng)用于實際.

1 問題定義和描述

給定K個吊機和一臺卡車,并假設(shè)吊機的服務(wù)時長為T.根據(jù)吊機間的安全距離,將卡車劃分為S個區(qū)域,每個區(qū)域包含一組被吊板卷.每一個區(qū)域的工作量為wj,j=1,2,…,S.這里區(qū)域的工作量定義為需要從每個區(qū)域吊到倉庫目標(biāo)位置的板卷數(shù)目.每一區(qū)域在同一時間只能有一個吊機在作業(yè),任意兩吊機之間不可發(fā)生碰撞或交叉.即兩個吊機不能在同一時間同一區(qū)域操作.當(dāng)一臺吊機開始在某一區(qū)域作業(yè),直到它卸載完全部的板卷才能停下來.在本文中,由于任意兩點之間的距離已知,根據(jù)吊機的行駛速度,為了方便表達,定義吊機從卡車上一個區(qū)域移動到另一個區(qū)域的行駛時間是一個常數(shù)v.各吊機具有相同的服務(wù)效率μ,即吊機單位時間內(nèi)的裝卸工作量(很容易擴展為各吊機服務(wù)效率不同的情況).目標(biāo)函數(shù)為最小化服務(wù)卡車的最大完工時間Cmax.此外,如果吊機在區(qū)域j可用,使用二元變量bj表示吊機所處的原始位置.即

令二元決策變量xjt表示在t時刻的開始區(qū)域j仍然有工作量剩余,

令二元決策變量wjt表示在t時刻的開始區(qū)域j的剩余工作量,

MinimizeCmax

(1)

Subject to

txjt≤Cmax,1≤j≤S, 1≤t≤T.

(2)

wjt-Mxjt≤0,1≤j≤S, 1≤t≤T.

(3)

(4)

(5)

1≤j≤S, 2≤t≤T-1.

(6)

(7)

(8)

1≤j≤S, 2≤t≤T.

(9)

(10)

(11)

1≤j≤S, 2≤t≤T-1.

(12)

(13)

xjt∈{0, 1},1≤j≤S, 1≤t≤T.

(14)

(15)

wj,t≥0,1≤j≤S, 1≤t≤T.

(16)

式(3)中M是一個足夠大的數(shù).目標(biāo)函數(shù)(1)是完成所有工作量的極小化時間表長,即最后一個吊機裝卸完成的時間.約束(2)表示吊機工作區(qū)域的最后完成時間,即時間表長.約束(3)表明t時刻是否有剩余板卷留在區(qū)域j.約束(4)表示工作量流平衡約束.對每一區(qū)域j,初始工作量滿足wj,1=wj,接下來的每個時間段,如果在某時間內(nèi)某一區(qū)域有一個吊機在工作的話,剩余的工作量將減少μ個單位,直到達到零為止.約束(5)～(8)是網(wǎng)絡(luò)流守恒約束.約束(9)表示在某一時間內(nèi)某一區(qū)域至多只有一個吊機在操作.約束(10)表示吊機間不能彼此交叉碰撞.約束(11)表示在t時段內(nèi)可有一個吊機在區(qū)域j空閑.約束(12)表示吊機無中斷的約束.約束(13)～(16)保證了決策變量的二元性和非負(fù)性.

2 問題性質(zhì)和啟發(fā)式算法及最壞性能分析

1) 問題性質(zhì).

性質(zhì)1 本文所研究的問題是強NP-難的.

如果不考慮相鄰區(qū)域間的移動時間,即我們所研究問題的特例,該問題為旅行商問題,明顯本文的問題也是NP-難的,因此,很難在短時間內(nèi)找到一個大規(guī)模實例的最優(yōu)算法.

本節(jié)提出了保證吊機操作的可行解性質(zhì).吊機調(diào)度不可行通常發(fā)生在如下2種情況下:①當(dāng)前吊機繁忙,板卷等待操作,此時沒有可利用的吊機;②一臺吊機結(jié)束當(dāng)前操作后與另一臺正操作的吊機發(fā)生沖突.為了簡化表達,令sj表示吊機開始運輸區(qū)域j內(nèi)任務(wù)的時間;ej表示吊機結(jié)束運輸區(qū)域j內(nèi)任務(wù)的時間.

性質(zhì)2 同一個吊機對兩區(qū)域內(nèi)板卷操作滿足如下條件時,吊機調(diào)度可行.

證明 情況①,如果si>sj,那么si>ej;情況②,如果si

性質(zhì)3 相鄰兩吊機對同一區(qū)域內(nèi)板卷操作滿足如下條件時,吊機調(diào)度可行.

(sj-si)(ej-si)(sj-ei)(ej-ei)≥0.

證明 情況①,sj>si、ej>si、sj>ei、ej>ei,表明只有當(dāng)區(qū)域i的操作完成時,區(qū)域j才開始;情況②,sj>si、ej>si、sjsi、sjei表明區(qū)域j的運輸開始時間比區(qū)域i早,而結(jié)束時間比i晚;情況④,sj

2) 基于分散搜索的啟發(fā)式算法.基于以上可行性質(zhì),提出基于分散搜索(scatter search)的啟發(fā)式算法.

分散搜索算法是一種基于種群的智能優(yōu)化算法,它的基本思想是對參考集中解的質(zhì)量和分散性進行控制,進一步對解進行組合,為了提高解的質(zhì)量,該算法可以利用局部改進搜索策略,通過多種搜索方式,從而提高求解質(zhì)量.分散搜索算法由Glover[8]于1977年首次提出,但直到1998年,Glover[9]才將整個算法過程系統(tǒng)地進行了總結(jié).圖3給出分散搜索算法基本流程圖.圖中PSize為預(yù)先給定的初始種群,b為預(yù)先給定的參考集RefSet,MaxIter表示迭代的最大次數(shù),MaxSubset表示選定的子集總數(shù),NewElements表示參考集是否被更新.

Step 1 初始化.設(shè)置PSize,MaxIter,b,設(shè)置NewElements=FALSE,Iter=0;將吊機按從小到大的順序編號.

Step 3 在集合Refset中檢驗如下條件:①(sj-si)(ej-si)≥0;②(si-sj)(ei-sj)≥0;③(sj-si)(ej-si)(sj-ei)(ej-ei)≥0,從而構(gòu)造子集NewSubsets.

Step 4 置Iter=Iter+1.若Iter>MaxIter,則算法停止;否則,在NewSubsets中選擇可行解子集s,采用解組合方法對s里的解進行組合,產(chǎn)生新解x.

Step 5 采用如下方式進行搜索:①當(dāng)?shù)鯔C完成各自區(qū)域內(nèi)任務(wù)時,依次計算相鄰吊機當(dāng)前剩余任務(wù)量,選擇剩余任務(wù)量大的區(qū)域分配給當(dāng)前吊機;②如果相鄰區(qū)域吊機未完成工作,則等待直到該吊機空閑;利用此方式搜索改進當(dāng)前解并得到新解x′.

Step 6 如果當(dāng)前解優(yōu)于參考集中質(zhì)量最差的解時,則將該改進解放入候選集合中,以備更新參考集.

Step 7 將子集s從NewSubsets中刪除.若NewSubsets為空,則轉(zhuǎn)入Step 8;否則,執(zhí)行Step 5.

Step 8 更新參考集.從候選集中選擇質(zhì)量優(yōu)的解并替換當(dāng)前參考集中質(zhì)量差的解,然后執(zhí)行Step 4;若候選集為空,則算法停止.

For (Iter=1到MaxIter) 步驟1: 生成初始種群P, |P|=PSize. 步驟2: 從P中選擇b個具有代表性的解, 產(chǎn)生參考集合RefSet. While (NewElements=TRUE) do 步驟3: 從參考集中選定子集, 置NewElements=FALSE. For (SubsetCounter=1, …, MaxSubset) 步驟4: 置NewElements=FALSE 步驟5: 取出第SubsetCounter個子集s. 步驟6: 對子集s應(yīng)用解的組合策略獲得一個或更多的新解xs. 步驟7: 對解xs應(yīng)用解的改進策略獲得改進解x's. 步驟8: 更新參考集. 若參考集被更新, NewElements=TRUE, 跳出循環(huán). End For End WhileEnd For

(17)

(18)

即

因此該算法的最壞性能比是2,而最壞情況分析只表示算法在極端情況時的性能.因此,在下一節(jié)中將通過計算實驗驗證算法的平均計算性能.

3 計算實驗結(jié)果

針對以上啟發(fā)式算法,使用C++語言開發(fā)了算法程序,為了驗證所提出算法的有效性,通過模擬實際數(shù)據(jù),隨機產(chǎn)生了一系列的實驗數(shù)據(jù)進行驗證.實驗環(huán)境如下.

1) 硬件環(huán)境:Dell Optiplex (CPU:Pentium Ⅳ 3.0 GHz,內(nèi)存:1 GB).

2) 軟件開發(fā)環(huán)境:微軟VC++6.0開發(fā)平臺.

3) CPLEX 11.0優(yōu)化軟件.

算例的各參數(shù)產(chǎn)生方式如下:根據(jù)實際問題背景,吊機的數(shù)目K分別取2,3,5,8,10;針對每次吊機個數(shù)的不同取值,卡車的分區(qū)S分別取4種對應(yīng)數(shù)值;區(qū)域的工作量wj在[10,20]之間根據(jù)均勻分布隨機產(chǎn)生.吊機的行駛時間v和服務(wù)效率μ根據(jù)均勻分布分別在[5,10]和[4,8]之間產(chǎn)生.根據(jù)每類數(shù)值的組合,共有20個實例,每個實例隨機產(chǎn)生10組數(shù)據(jù)來驗證MILP模型和啟發(fā)式算法的有效性.表1中列出的結(jié)果是每個實例的平均值.其中“—”表示使用CPLEX軟件在預(yù)先設(shè)定的7 200 s內(nèi)沒能求出問題的最優(yōu)解.為了驗證算法的性能,用最優(yōu)偏差Opt.gap進行度量,如果MILP模型求出了問題的最優(yōu)解,Opt.gap=(CA-C*)/C*·100%;如果MILP模型在預(yù)先設(shè)定時間內(nèi)沒能求出問題的解,則通過松弛所建立數(shù)學(xué)模型的約束(12)獲得問題的下界.此時Opt.gap=(CA-CL)/CL·100%表示問題最優(yōu)解與下界的相對間隙.

表1 混合整數(shù)線性規(guī)劃(MILP)模型和啟發(fā)式算法的計算結(jié)果

4 結(jié) 論

依據(jù)表1的結(jié)果,可以得出如下結(jié)論.

1) 當(dāng)?shù)鯔C數(shù)目不超過5,卡車分區(qū)不超過8的小規(guī)模計算實例,基于分散搜索的啟發(fā)式算法與MILP的平均偏差小于1%,即使全部算例中的最大計算偏差也小于0.50%.此外,從所消耗的計算時間來看,啟發(fā)式算法與MILP的性能是可以比較的.然而,對于MILP中稍微大一些的實例來說,所消耗的時間逐漸增大.

2) 當(dāng)?shù)鯔C數(shù)目不超過5,卡車分區(qū)超過8的中等規(guī)模計算實例,MILP模型可以求出問題的最優(yōu)解,但是所消耗平均計算時間卻很大,而所提出的基于分散搜索的啟發(fā)式算法所消耗的時間相對較小,最長的不超過30 s.

3) 當(dāng)?shù)鯔C數(shù)目超過8,卡車分區(qū)超過8的大規(guī)模計算實例,雖然CPLEX軟件不能在7 200 s內(nèi)求得所有問題的最優(yōu)解,但是它卻可以提供接近最優(yōu)解的下界.隨著問題規(guī)模的增大,所提出的啟發(fā)式算法所消耗的時間不超過60 s.計算結(jié)果顯示啟發(fā)式算法和MILP模型相比所獲得的最大偏差不超過0.40%.

5 結(jié) 語

本文研究了鋼卷倉庫內(nèi)的多吊機調(diào)度問題,針對該問題,建立了多吊機協(xié)調(diào)調(diào)度的模型,考慮了避免吊機碰撞的實際約束,為了求解大規(guī)模的實際問題,進一步提出了一個基于分散搜索算法的啟發(fā)式算法,該算法可以求得問題的近優(yōu)解.未來的研究將進一步考慮具有更多實際約束的該類問題,如考慮將吊機調(diào)度與鋼卷位置的選擇集成考慮,這是因為鋼卷位置的選擇將影響到吊機的調(diào)度,反之也成立.