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

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

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

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

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

1 問題的定義和描述

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

2 復(fù)雜性分析

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

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

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

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

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

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

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

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

3.1 問題的性質(zhì)

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

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

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

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

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

3.2 啟發(fā)式算法

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

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

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

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

4 結(jié) 果

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

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

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

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

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

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

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

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

從計(jì)算結(jié)果可以看出以下幾點(diǎn).

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

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

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

5 結(jié) 論

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