原料碼頭橋式吊機調(diào)度的分組與算法

謝 謝, 鄭勇躍, 張 欣, 李曉麗

(1. 沈陽大學 a. 裝備制造綜合自動化重點實驗室, b. 后勤管理服務(wù)中心, 遼寧 沈陽 110044;2. 遼寧省檢驗檢測認證中心 事業(yè)發(fā)展中心, 遼寧 沈陽 110032;3. 吉林省雙遼市職業(yè)高級中學, 吉林 雙遼 136400)

鋼鐵工業(yè)是經(jīng)濟發(fā)展的關(guān)鍵基礎(chǔ),鋼鐵加工是鋼鐵工業(yè)全過程的核心.鋼鐵工業(yè)的生產(chǎn)和運作直接決定了生產(chǎn)的費用、運作效率以及鋼鐵生產(chǎn)過程的質(zhì)量.高溫融化的鋼鐵、鋼包及大量附屬的原料和產(chǎn)品都經(jīng)由皮帶、臺車和吊機運輸.有效的吊機調(diào)度是確保流暢、高效生產(chǎn)以及穩(wěn)定生產(chǎn)節(jié)奏的基礎(chǔ).吊機調(diào)度作為多個不同過程之間的運輸環(huán)節(jié),直接影響高溫液態(tài)鋼水運輸?shù)臅r間和狀態(tài)的穩(wěn)定.因此,從原料碼頭開始,高效的吊機調(diào)度,即確定吊機的操作順序,是避免不必要的延遲的關(guān)鍵.原料碼頭中,到港輪船一側(cè)的吊機安裝在相同的軌道上,彼此之間相互干擾,但是,在兩側(cè)的吊機可以自由地相互交叉,見圖1.

圖1 原料碼頭吊機操作示意圖Fig.1 Schematic diagram of crane operation of raw material terminal

原料碼頭的吊機調(diào)度問題不僅出現(xiàn)在鋼鐵企業(yè)內(nèi),集裝箱港口碼頭也會遇到類似的調(diào)度問題,在集裝箱港口碼頭使用的吊機稱為龍門吊,該吊機是鐵路和鐵路之間以及鐵路和公路之間集裝箱的重要轉(zhuǎn)運工具,集裝箱在火車和火車以及卡車和火車之間的運輸都由它們負責[1].無論是集裝箱碼頭的龍門吊還是鋼鐵企業(yè)原料碼頭的吊機,通常安裝在場地的兩側(cè),每臺吊機由兩個吊鉤組成,一個安裝在另一個之上,吊鉤之間可以獨立操作,但彼此不交叉.

1 問題的定義和描述

給定M個吊機,吊機布局在集裝箱位置的兩側(cè),吊機分為兩個不同的子集L={l1,…,lm}和R={r1,…,rk},L∪R=M,每個集合的吊機都從左到右排列.可行的調(diào)度至少包括以下幾點:一個吊機每次只能操作一個集裝箱,每個吊機至少處理一個區(qū)域,兩個吊機不能同時處理一個區(qū)域,相同集合內(nèi)的吊機不能交叉.不失一般性,假設(shè)每臺吊機的運輸能力和倒垛能力都相同.兩臺卡車分別位于區(qū)域的兩端.

2 復(fù)雜性分析

本節(jié)證明所研究的問題是一般意義NP難的.常用的方法是對此問題構(gòu)造一個實例,再通過把一個已知的二劃分問題歸約到這個構(gòu)造的實例來實現(xiàn)證明.

引理1 本文所研究的問題是一般意義NP難.

證明 由二劃分問題歸約得到.構(gòu)造的調(diào)度例子如下:兩臺吊機L={l1}和R={r1}.因為兩個吊機不互相干擾,可以進行平等分區(qū).對于每個整數(shù)a∈A,我們設(shè)定一個區(qū)域s∈S(S={1,…,|A|}),負載WS=a,?a∈A.

2007年，農(nóng)場的主干渠修成了水泥U型渠，干渠各出水口有了小閘門，主渠換水時方便又省勁。但田間土渠還得攔水打壩，雨靴還是父親澆水最好的伴侶。

如果二劃分問題有解,易證調(diào)度可行,且目標函數(shù)值為a/2,不超過門檻值.

如果二劃分問題無解,必有函數(shù)值大于門檻值,即必存在某個吊機的工作量超過平均值,從而使得函數(shù)值大于門檻值.

以往對多吊機調(diào)度問題的研究多集中在優(yōu)化吊機之間的避讓,有效地協(xié)調(diào)多吊機之間的操作,減少集裝箱及吊機之間的等待時間,而精細化的吊機之間的操作以減少避讓,增加了算法的運行時間,此外,吊機在原料碼頭對集裝箱這類大型物件實際的操作過程中,對每臺吊機操作的細節(jié)很難具體地實施,本文從平衡集裝箱任務(wù)量的角度,將一側(cè)相鄰兩吊機間的操作看作平行機操作,定義為挪動吊機;另一側(cè)的一臺吊機定義為運輸?shù)鯔C;即每三臺吊機作為一組.這樣避免了吊機之間為保證安全距離而帶來的不必要的等待.分組決策的吊機調(diào)度可以有效地利用吊機,將傳統(tǒng)的生產(chǎn)與物流運輸集成決策的的思想引入調(diào)度過程,可以提高生產(chǎn)率.

3 問題的性質(zhì)及啟發(fā)式算法

3.1 問題的性質(zhì)

性質(zhì)1 在已有吊機分組下存在一個最優(yōu)調(diào)度滿足:任意一個吊機、集裝箱都沒有空閑.

性質(zhì)2 在已有吊機分組下存在一個最優(yōu)調(diào)度滿足:集裝箱被吊機運輸?shù)某霭l(fā)時間或者是在集裝箱區(qū)域內(nèi)挪動完成時間,或者是在吊機的可利用的時間.

性質(zhì)3 在已有吊機分組下存在一個最優(yōu)調(diào)度滿足:①分配給同一個挪動吊機的集裝箱按照挪動時間非降(SPT規(guī)則)排序;②分配給運輸?shù)鯔C的集裝箱按照挪動完成的時間非降排序.

證明 ①通過相鄰的集裝箱交換得證;②按照集裝箱被挪動完成的時間進行重新排序,滿足c1≤c2≤…≤cn.不失一般性,假設(shè)集裝箱k,k+1∈S并且滿足ck≤ck+1.根據(jù)問題描述可知,sk+1≥sk+T.現(xiàn)將集裝箱k+1安排在集裝箱k后運輸,其余集裝箱保持不變.顯然,目標函數(shù)值至少減少T.因此,分配給運輸?shù)鯔C的集裝箱按照挪動完成的時間非降排序.

由以上性質(zhì)可知,當運輸?shù)鯔C可利用時,它或者立刻開始運輸集裝箱,或者等待集裝箱倒垛完成.因此,每一個運輸集裝箱的出發(fā)時間需要決策、運輸集裝箱的順序也是需要決策的.

3.2 啟發(fā)式算法

第1步 吊機分組.左側(cè)吊機按照一臺運輸?shù)鯔C和兩臺倒垛吊機的模式劃分.右側(cè)吊機按照兩臺倒垛吊機和一臺運輸?shù)鯔C的模式劃分.即將左側(cè)第一臺吊機作為運輸?shù)鯔C、與右側(cè)作為倒垛吊機的第一、二臺吊機分為一組.左側(cè)第二、三臺倒垛吊機與右側(cè)第三臺運輸?shù)鯔C分為一組.以此類推.左右兩側(cè)最后剩余的吊機作為一組.如果左右各剩余一臺吊機即一臺作為倒垛吊機一臺作為運輸?shù)鯔C.同一側(cè)剩余吊機僅作為運輸?shù)鯔C使用,將分成的組數(shù)使用|G|表示.

第2步 在每組中,按照SPT規(guī)則首先對分配給同一吊機的倒垛集裝箱進行排序,滿足p1≤p2≤…≤pn,計算挪動完成時間并按照非降的順序c1≤c2≤…≤cn排列.

第3步 計算每一組內(nèi)集裝箱運輸?shù)拈_始時間sj,進一步計算出集裝箱j到達卡車的時間Cj=sj+tj.

定理1 在吊機分組確定時,已知集裝箱在吊機上的倒垛順序與運輸順序,啟發(fā)式算法能夠在O(n4)時間內(nèi)產(chǎn)生最優(yōu)調(diào)度.其中運輸?shù)某霭l(fā)時間sj計算次數(shù)至多為O(n2).

4 結(jié) 果

為了評估啟發(fā)式算法的性能,在本節(jié)中進行數(shù)值計算實驗.啟發(fā)式算法使用VC++6.0編程,在Pentium-Ⅳ的PC機上運行,操作系統(tǒng)是Windows XP,CPU是2.40 GHz,內(nèi)存為1 GB.

依據(jù)鋼鐵企業(yè)碼頭的實際情況,隨機產(chǎn)生的實例參數(shù)如下.

集裝箱數(shù)量n:10, 20, 30, 50, 80, 100;

左右兩側(cè)吊機的數(shù)目L和R:從[1, 10]的均勻分布中產(chǎn)生;

集裝箱原地挪動時間pj:從[1, 10]的均勻分布中產(chǎn)生;

集裝箱的運輸開始時間和運輸時間sj和tj:從[1, 10]和[1, 20]的均勻分布中產(chǎn)生.

實驗結(jié)果如表1所示.在表1中誤差比r的平均值和最大值分別定義為avg(r)和max(r),其中r的平均值表示啟發(fā)式算法對這12組實例的平均運行情況,而最大值則表示其最壞運行情況.使用Avg.CPU表示每一組的平均計算時間.

表1 啟發(fā)式實驗結(jié)果Table 1 Results of heuristic experiment

從計算結(jié)果可以看出以下幾點.

1) 當L=3,R=5或L=5,R=3時,隨著問題規(guī)模的增大算法的平均誤差比avg(r)和最大誤差比max(r)減小,而當L=5,R=3時,算法的avg(r)和max(r)比L=3,R=5時更小,可能由于算法在L=5,R=3時吊機的分組多余了2臺運輸?shù)鯔C,減少了倒垛后集裝箱的等待時間.

2) 類似地,當L=4,R=7或L=7,R=4時,隨著問題規(guī)模的增大算法的平均誤差比avg(r)和最大誤差比max(r)減小,然而比起情況1)時,算法的avg(r)和max(r)有所增大,由于左右兩側(cè)吊機的數(shù)目較大,剩余未被分組的吊機經(jīng)常處于空閑狀態(tài)或使得集裝箱發(fā)生不必要的等待.

3) 隨著吊機數(shù)目的增加,吊機的分組也越來越多,當L=6,R=8或L=8,R=6時,可分為完整的4組時,比起情況1)中的不完整的4組,算法的avg(r)和max(r)減小,說明吊機分組操作集裝箱比起不分組的調(diào)度更有效率.而實際港口碼頭集裝箱數(shù)目需要調(diào)度的數(shù)目不會超過100,對于小規(guī)模實例,算法可以迅速獲得問題的解.對于較大規(guī)模的問題,算法的計算時間也不超過1s.因此計算的實驗結(jié)果表明:本文提出的啟發(fā)式算法可以在很短時間內(nèi)求出問題的近優(yōu)解.

5 結(jié) 論

本文針對原料碼頭的集裝箱調(diào)度問題提出了一個吊機分組的啟發(fā)式算法,首先通過二劃分的歸結(jié)證明了問題是NP難的.進一步分析了問題的最優(yōu)性質(zhì),基于最優(yōu)性質(zhì)提出了基于吊機分組的啟發(fā)式算法.為評價啟發(fā)式算法的性能,提出了有效的下界,通過實驗結(jié)果驗證啟發(fā)式算法的有效性.有關(guān)吊機的分組決策再調(diào)度未來將進一步考慮其他的目標函數(shù),如最大拖期和最大延遲等.