混合亞啟發式算法求解帶有熱量損失的單吊機調度

謝 謝, 周 莉, 鄭勇躍

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

本文研究了一類來自于鋼鐵生產企業中物流系統的吊機調度問題.每階段板坯加工結束后,倉庫作為存儲板坯的緩沖區域,在這里,目標板坯(半成品或成品)需要由吊機操作揀選運輸到下一階段加工或客戶端.倉庫中的主要操作由吊機實施,包括將板坯運輸到適合的位置,揀選客戶的需求板坯,一旦板坯不能直接運輸,先將壓在其上方的阻礙板坯運輸到其他位置等.在這些操作中,將阻礙板坯運輸到其他位置的倒垛操作是非常消耗時間和能源的.倒垛操作的工作量占倉庫總操作的一半以上[1].圖1給出了板坯倉庫的一個存儲區域.鋼鐵企業板坯倉庫中每個存儲區域通常按行列堆放,大約276塊板坯堆放成1～3行,1～92列.黑色和灰色分別表示需求板坯和倒垛板坯,虛線處表示該位置為空.每個區域由1臺吊機操作.吊機可以由一個位置移動到另一個位置,意味著它的吊鉤伴隨著吊機不僅沿著平行的跨方向移動,而且還可以在跨之間的橋來回移動,兩個方向可以同時進行.為了方便,本文中我們將吊鉤看作吊機.板坯在每垛中按層堆放,一個堆放在另一個上面.

圖1 板坯倉庫的存儲區域Fig.1 A storage area in slab warehouse

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

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

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

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

1 問題的定義和描述

為了對問題建立數學模型,基于圖1、圖2,必要的符號說明如下.

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

決策變量如下:

Sj= 第j個裝載移動的開始時間,j=1,2,…,(|B|+|R|);

Cj= 第j個裝載移動的完成時間,j=1,2,…,(|B|+|R|);

i∈B,p∈P;

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

基于以上符號,混合整數規劃模型表示如下.

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

2 復雜性

由于本文研究的問題復雜性不可知,因此使用歸結的方法的證明該問題是強NP-難的.

性質1 即使考慮一種最簡單的情況:吊機的初始位置與需求板坯的目標位置相同,運輸需求板坯的時間趨近于0,該情況也是強NP-難的.

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

3 啟發式算法及最壞性能分析

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

3.1 參考集的建立

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

第2步 逐一計算吊機當前位置到需求板坯的最近距離.

3.2 解的組合機制

3.3 解的改進

3.3.1 鄰域

(1) 轉換移動(Nshift).解的鄰域轉換定義為通過改變解內任意板坯的分配來獲得.

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

3.3.2 變深度搜索策略

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

(2) 探索n1個解的節點鄰域Nswap中,n2為發現的最好解的數目.因此,在d+1層產生的解為N=n1×n2個.如果根節點處的解不能改進,則用該處的解作為最好的解.一旦全局解不能進一步改進,則搜索停止.

4 計算結果

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

問題的實例使用如下數值:存儲區域的全部位置|P|,區域的空間利用率U,所有需求板坯的數目|R|以及倒垛板坯的數目|B|.目標位置都在存儲區域一行的一側,舉例說明,目標位置的選取從1到|R|,具體的位置從可能的位置中選取.如圖1所示,同一垛中相鄰兩板坯的位置為1,相鄰兩垛中的距離為2,吊機沿兩個方向的裝載移動和空載移動的速度分別為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

注: {·} 括號里的數字表示在時間限制內MILP模型不能最優求解的實例數目.

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

隨著空間利用率的增加,MILP求解的時間大大增加了.當總的需求板坯數目和阻礙板坯數目達到8,空間利用率達到70%,時,使用MILP模型就不能在10h內求得問題的最優解.對于一些小規模的例子,MILP模型可以求出問題的最優解.隨著問題規模的擴大,MILP模型和下界之間的偏差變大,表明下界LB的質量看起來隨著問題規模增大而惡化.這是因為,由于下界使用最短的移動時間估測實際的移動時間,然而,隨著問題規模的增大兩個位置之間的平均移動距離也增加了.

混合亞啟發式算法對任意測試的實例幾乎都快速求解,解的質量距離最優解也不遠.與MILP模型相比隨著問題規模的增大,性能更加穩定.雖然隨著問題規模的增加計算時間也增加了,求解70%空間利用率的實例時間長于低空間利用率如50%和高空間利用率90%,不同于MILP模型,求解的最長時間是空間利用率為90%的實例.或許是因為高空間利用率,對于阻礙板坯有非常少的空位,低空間利用率,則阻礙板坯較少可以幫助減少搜索時間.

5 結 論

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