混合亞啟發(fā)式算法求解帶有熱量損失的單吊機(jī)調(diào)度

謝 謝, 周 莉, 鄭勇躍

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

本文研究了一類來自于鋼鐵生產(chǎn)企業(yè)中物流系統(tǒng)的吊機(jī)調(diào)度問題.每階段板坯加工結(jié)束后,倉庫作為存儲(chǔ)板坯的緩沖區(qū)域,在這里,目標(biāo)板坯(半成品或成品)需要由吊機(jī)操作揀選運(yùn)輸?shù)较乱浑A段加工或客戶端.倉庫中的主要操作由吊機(jī)實(shí)施,包括將板坯運(yùn)輸?shù)竭m合的位置,揀選客戶的需求板坯,一旦板坯不能直接運(yùn)輸,先將壓在其上方的阻礙板坯運(yùn)輸?shù)狡渌恢玫?在這些操作中,將阻礙板坯運(yùn)輸?shù)狡渌恢玫牡苟獠僮魇欠浅Ｏ臅r(shí)間和能源的.倒垛操作的工作量占倉庫總操作的一半以上[1].圖1給出了板坯倉庫的一個(gè)存儲(chǔ)區(qū)域.鋼鐵企業(yè)板坯倉庫中每個(gè)存儲(chǔ)區(qū)域通常按行列堆放,大約276塊板坯堆放成1～3行,1～92列.黑色和灰色分別表示需求板坯和倒垛板坯,虛線處表示該位置為空.每個(gè)區(qū)域由1臺(tái)吊機(jī)操作.吊機(jī)可以由一個(gè)位置移動(dòng)到另一個(gè)位置,意味著它的吊鉤伴隨著吊機(jī)不僅沿著平行的跨方向移動(dòng),而且還可以在跨之間的橋來回移動(dòng),兩個(gè)方向可以同時(shí)進(jìn)行.為了方便,本文中我們將吊鉤看作吊機(jī).板坯在每垛中按層堆放,一個(gè)堆放在另一個(gè)上面.

圖1 板坯倉庫的存儲(chǔ)區(qū)域Fig.1 A storage area in slab warehouse

基于每垛存放的行列位置,圖2以一垛為例,如果需求板坯在正上方,可以被直接吊走,否則需要先將阻礙板坯移動(dòng)到其他地方以露出需求板坯.不同于Tang等[2-3]和Singh等[4]考慮的問題,根據(jù)存儲(chǔ)區(qū)域的實(shí)際,本文考慮的倒垛板坯不需要再移動(dòng)回原位,同時(shí),所選取存放的位置要盡可能離倒垛板坯的原位置很近以減少倒垛時(shí)間,降低熱量損失.由于原始的堆放可以保證每個(gè)板坯的位置,因此,板坯的倒垛位置充足.

圖2板坯倉庫的一垛板坯
Fig.2Aslabstackintheslabwarehouse

對(duì)于每個(gè)需求板坯,吊機(jī)需要盡快地將其移動(dòng)到指定位置.本文研究的問題就是確定需求板坯的移動(dòng)順序、倒垛板坯的移動(dòng)位置最小化總溫降損失.盡管倒垛板坯可以被移動(dòng)到任一空位,為了避免進(jìn)一步倒垛,本文不允許將倒垛板坯移動(dòng)到需求板坯的上方,吊機(jī)的工作量包括倒垛和移動(dòng)操作,該過程非常繁忙,是全部操作的瓶頸.因此吊機(jī)調(diào)度可以保證每個(gè)需求板坯及時(shí)被取出并減少熱量損失.

盡管已有一些相關(guān)文獻(xiàn)研究鋼鐵倉庫的吊機(jī)調(diào)度問題[5-9].但很少有研究考慮被吊物件熱量損失的問題,求解問題的算法也僅僅是包括啟發(fā)式規(guī)則和簡單的鄰域搜索策略,很少有嘗試將貪婪算法和變深度鄰域搜索策略組合對(duì)問題求解.Tang等[2]提出一個(gè)整數(shù)規(guī)劃模型和兩階段啟發(fā)式算法求解具有不同板坯族的問題.Tang等[3]研究了沒有通用板坯的該問題并且提出遺傳算法求解.Singh等[4]也提出一個(gè)改進(jìn)的平行遺傳算法,其中包含了一些新的遺傳因子,以上研究的目標(biāo)都是減少倒垛次數(shù),在一定程度上節(jié)省了板坯操作的費(fèi)用,Tang和Ren[10]也研究了板坯倒垛問題,提出了基于啟發(fā)式的分部動(dòng)態(tài)規(guī)劃最小化吊機(jī)的總工作量.

1 問題的定義和描述

為了對(duì)問題建立數(shù)學(xué)模型,基于圖1、圖2,必要的符號(hào)說明如下.

B為所有倒垛板坯的集合;R為所有需求板坯的集合;ri為需求板坯i的釋放時(shí)間;P為所有位置的集合;poi為板坯i的初始位置(i∈B∪R);tp,p′為從位置P到位置p′的裝載移動(dòng)時(shí)間;ep,p′為從位置P到位置p′的空載移動(dòng)時(shí)間;pdi為需求板坯i的指定位置(i∈R);p0為吊機(jī)的初始位置.

決策變量如下:

Sj= 第j個(gè)裝載移動(dòng)的開始時(shí)間,j=1,2,…,(|B|+|R|);

Cj= 第j個(gè)裝載移動(dòng)的完成時(shí)間,j=1,2,…,(|B|+|R|);

i∈B,p∈P;

i∈B∪R,j=1,2,…,(|B|+|R|).

基于以上符號(hào),混合整數(shù)規(guī)劃模型表示如下.

這個(gè)混合整數(shù)線性規(guī)劃模型是線性的,因此可以使用CPLEX軟件求解.然而,隨著問題規(guī)模的擴(kuò)大,CPLEX求解耗費(fèi)大量時(shí)間,根據(jù)一次實(shí)際計(jì)劃(大約超過20個(gè)位置),該軟件就停止計(jì)算了,因此有必要對(duì)該問題提出有效的啟發(fā)式算法.

2 復(fù)雜性

由于本文研究的問題復(fù)雜性不可知,因此使用歸結(jié)的方法的證明該問題是強(qiáng)NP-難的.

性質(zhì)1 即使考慮一種最簡單的情況:吊機(jī)的初始位置與需求板坯的目標(biāo)位置相同,運(yùn)輸需求板坯的時(shí)間趨近于0,該情況也是強(qiáng)NP-難的.

證明 當(dāng)這種情況發(fā)生時(shí),只需要考慮對(duì)阻礙板坯進(jìn)行倒垛.給定旅行商問題的實(shí)例,將旅行商看作單吊機(jī),將城市看作阻礙板坯的位置.單吊機(jī)需要從它的初始位置運(yùn)輸通過每個(gè)倒垛板坯的位置后再回到初始位置,使得總完工時(shí)間最短,由于任意2個(gè)板坯位置預(yù)先已知,這種情況等價(jià)于已知的旅行商問題.由于旅行商問題是強(qiáng)NP-難的,因此,可知這種情況可解當(dāng)且僅當(dāng)旅行商問題可解.

3 啟發(fā)式算法及最壞性能分析

在本節(jié)中,提出了一個(gè)混合亞啟發(fā)式算法求解該問題.該算法在搜索不同的鄰域空間與當(dāng)前解的有效性上保持了一種平衡.分散搜索作為一種搜索機(jī)制結(jié)合了變深度鄰域搜索的特點(diǎn)對(duì)解進(jìn)一步搜索.第一步,首先使用貪婪啟發(fā)式算法構(gòu)成參考集,再根據(jù)解的組合機(jī)制產(chǎn)生新的解.之后通過使用變深度鄰域搜索策略改進(jìn)當(dāng)前解,如果改進(jìn)的解好于當(dāng)前參考集的最壞解,則替換當(dāng)前參考集里的解.

3.1 參考集的建立

第1步 計(jì)算吊機(jī)對(duì)阻礙板坯從各自的位置到倒垛空位的距離,逐一按照非減的順序排序;

第2步 逐一計(jì)算吊機(jī)當(dāng)前位置到需求板坯的最近距離.

3.2 解的組合機(jī)制

3.3 解的改進(jìn)

3.3.1 鄰域

(1) 轉(zhuǎn)換移動(dòng)(Nshift).解的鄰域轉(zhuǎn)換定義為通過改變解內(nèi)任意板坯的分配來獲得.

(2) 交互式移動(dòng)(Nswap).解的鄰域可以定義為通過交換解內(nèi)兩個(gè)板坯的分配來獲得.

3.3.2 變深度搜索策略

(1) 通過搜索初始解的鄰域Nswap獲得.一旦找到局部最優(yōu)解η(假設(shè)η是第一層的節(jié)點(diǎn)數(shù))作為產(chǎn)生搜索樹的第一層,搜索樹的下一層按照如下方式建立:假設(shè)n1表示層d的節(jié)點(diǎn)數(shù)目;令d表示層數(shù),M(d)為層d中解的候選列表;假設(shè)n1為候選解集M(d)的移動(dòng)數(shù)目,n2為通過局部搜索產(chǎn)生的移動(dòng)中最好的移動(dòng)數(shù)目.

(2) 探索n1個(gè)解的節(jié)點(diǎn)鄰域Nswap中,n2為發(fā)現(xiàn)的最好解的數(shù)目.因此,在d+1層產(chǎn)生的解為N=n1×n2個(gè).如果根節(jié)點(diǎn)處的解不能改進(jìn),則用該處的解作為最好的解.一旦全局解不能進(jìn)一步改進(jìn),則搜索停止.

4 計(jì)算結(jié)果

為了估測所提出啟發(fā)式算法的性能,計(jì)算實(shí)驗(yàn)基于實(shí)際生產(chǎn)數(shù)據(jù).所有的算法使用VC++ 6.0編程并且運(yùn)行在P4-3.00 GHz CPU以及內(nèi)存為1G RAM的電腦上.MILP模型使用軟件CPLEX 11.0版本求解.

問題的實(shí)例使用如下數(shù)值:存儲(chǔ)區(qū)域的全部位置|P|,區(qū)域的空間利用率U,所有需求板坯的數(shù)目|R|以及倒垛板坯的數(shù)目|B|.目標(biāo)位置都在存儲(chǔ)區(qū)域一行的一側(cè),舉例說明,目標(biāo)位置的選取從1到|R|,具體的位置從可能的位置中選取.如圖1所示,同一垛中相鄰兩板坯的位置為1,相鄰兩垛中的距離為2,吊機(jī)沿兩個(gè)方向的裝載移動(dòng)和空載移動(dòng)的速度分別為v1=1 m/s,v2=2 m/s,λ1=2 m/s,λ2=4 m/s.上提下放的速度為μ=2.5 m/s.

表1 2種所提出算法的性能比較Table 1 The performance for two proposed methods

注: {·} 括號(hào)里的數(shù)字表示在時(shí)間限制內(nèi)MILP模型不能最優(yōu)求解的實(shí)例數(shù)目.

對(duì)于每個(gè)實(shí)例,倉庫的存儲(chǔ)基于空間利用率以及N個(gè)可利用的位置.初始位置的選擇考慮板坯的可行性,|R|個(gè)需求板坯存儲(chǔ)在所有可行位置.嘗試使用MILP模型求解小規(guī)模問題R,B,P分別為2,3,12.對(duì)于以上參數(shù)的各種組合,10個(gè)實(shí)例一組,分別使用MILP模型和混合亞啟發(fā)式算法求解問題.設(shè)置10h為使用MILP模型求解問題的時(shí)間限制,如果在這個(gè)時(shí)間內(nèi)不能獲得最優(yōu)解,則記錄下最好的可行解.由于MILP模型不能對(duì)每個(gè)實(shí)例求出最優(yōu)解,使用下界LB,作為比較不同解質(zhì)量的標(biāo)準(zhǔn)(Cmax-LB)/LB×100%.我們也將混合亞啟發(fā)式算法與下界進(jìn)行比較從而對(duì)所提出的算法進(jìn)行估測.算法的平均相對(duì)偏差(ARD)和計(jì)算時(shí)間如表1.

隨著空間利用率的增加,MILP求解的時(shí)間大大增加了.當(dāng)總的需求板坯數(shù)目和阻礙板坯數(shù)目達(dá)到8,空間利用率達(dá)到70%,時(shí),使用MILP模型就不能在10h內(nèi)求得問題的最優(yōu)解.對(duì)于一些小規(guī)模的例子,MILP模型可以求出問題的最優(yōu)解.隨著問題規(guī)模的擴(kuò)大,MILP模型和下界之間的偏差變大,表明下界LB的質(zhì)量看起來隨著問題規(guī)模增大而惡化.這是因?yàn)?由于下界使用最短的移動(dòng)時(shí)間估測實(shí)際的移動(dòng)時(shí)間,然而,隨著問題規(guī)模的增大兩個(gè)位置之間的平均移動(dòng)距離也增加了.

混合亞啟發(fā)式算法對(duì)任意測試的實(shí)例幾乎都快速求解,解的質(zhì)量距離最優(yōu)解也不遠(yuǎn).與MILP模型相比隨著問題規(guī)模的增大,性能更加穩(wěn)定.雖然隨著問題規(guī)模的增加計(jì)算時(shí)間也增加了,求解70%空間利用率的實(shí)例時(shí)間長于低空間利用率如50%和高空間利用率90%,不同于MILP模型,求解的最長時(shí)間是空間利用率為90%的實(shí)例.或許是因?yàn)楦呖臻g利用率,對(duì)于阻礙板坯有非常少的空位,低空間利用率,則阻礙板坯較少可以幫助減少搜索時(shí)間.

5 結(jié) 論

本文研究了鋼鐵企業(yè)板坯倉庫的單吊機(jī)倒垛問題,目標(biāo)函數(shù)為最小化被吊板坯總熱量損失.針對(duì)這個(gè)問題,建立了混合整數(shù)規(guī)劃模型,該模型用于最優(yōu)求解小規(guī)模的問題,針對(duì)中大規(guī)模問題,進(jìn)一步提出一個(gè)混合亞啟發(fā)式算法,通過變深度鄰域搜索策略改進(jìn)初始解的性能.計(jì)算實(shí)驗(yàn)表明,所提出的方法可以有效的求解該問題.未來的研究將進(jìn)一步擴(kuò)展問題的模型和算法用于求解其他目標(biāo)函數(shù),如最小化總倒垛和總揀選的費(fèi)用等.