王巍,趙宏,李強(qiáng)
1.天津工業(yè)大學(xué) 經(jīng)濟(jì)學(xué)院,天津 300387
2.天津港(集團(tuán))有限公司 科技設(shè)備部,天津 300461
面向多停泊基地的港口拖輪調(diào)度優(yōu)化研究
王巍1,趙宏1,李強(qiáng)2
1.天津工業(yè)大學(xué) 經(jīng)濟(jì)學(xué)院,天津 300387
2.天津港(集團(tuán))有限公司 科技設(shè)備部,天津 300461
船舶進(jìn)入港口航道時(shí)需要拖輪護(hù)航和協(xié)助靠泊。同樣,船舶在離開泊位出港時(shí),也需要拖輪協(xié)助完成。另外,船舶可能在港口不同泊位之間裝卸貨物,還需要拖輪協(xié)助進(jìn)行不同泊位間的移動(dòng)。因此,拖輪作業(yè)在港口船舶裝卸作業(yè)流程中具有相當(dāng)重要的作用,拖輪作業(yè)調(diào)度的好壞將直接影響船舶的作業(yè)效率和進(jìn)出港時(shí)間。
不同類型的船舶作業(yè)所需要的拖輪類型和數(shù)量互不相同,有的船舶需要一艘拖輪,有的則需要兩艘甚至更多。因此,拖輪調(diào)度具有多機(jī)協(xié)同作業(yè)的特點(diǎn)。此外,隨著現(xiàn)代港口規(guī)模的不斷擴(kuò)大和進(jìn)出港船舶的不斷增多,很多港口建設(shè)了多個(gè)拖輪停泊基地,實(shí)施分區(qū)域拖輪作業(yè)管理,這就使得拖輪調(diào)度的優(yōu)化和決策成為一個(gè)更加復(fù)雜的問題。
目前,針對(duì)上述問題的研究主要集中在拖輪作業(yè)過程的仿真和資源配置方面[1-4],考慮多停泊基地的拖輪調(diào)度優(yōu)化研究尚未見報(bào)道。本文首先分析了拖輪調(diào)度的特點(diǎn),并從多處理器任務(wù)調(diào)度的角度進(jìn)行了闡述。其次,以最大完工時(shí)間和總作業(yè)油耗最小化為優(yōu)化目標(biāo),建立了考慮多拖輪停泊基地的拖輪調(diào)度多目標(biāo)優(yōu)化模型。最后,采用演化策略算法對(duì)所建模型進(jìn)行優(yōu)化,并用算例進(jìn)行了驗(yàn)證,取得了較好的結(jié)果。
多處理器任務(wù)調(diào)度強(qiáng)調(diào)同一時(shí)刻,存在一個(gè)或多個(gè)處理器來完成對(duì)某一個(gè)任務(wù)的作業(yè),其產(chǎn)生于并行計(jì)算和計(jì)算機(jī)系統(tǒng)。多處理器任務(wù)調(diào)度主要分為并行處理器和專用處理器兩種類型。在并行處理器中,強(qiáng)調(diào)每個(gè)處理器均是同類型的,并且按照任務(wù)所要求的處理器數(shù)量,所有處理器中的任意組合均可完成所給出的任務(wù)。在專用處理器中,每個(gè)處理器是不同類型的,每個(gè)任務(wù)均對(duì)應(yīng)于一個(gè)處理器集合,任務(wù)的完成需要該集合中所有處理器同時(shí)工作[5-11]。
拖輪作業(yè)過程中,拖輪與船舶之間存在一定的配比關(guān)系。以某港口的拖輪作業(yè)為例,其擁有883 kW、1 912 kW、2 354 kW、2 500 kW、2 942 kW和3 678 kW等6種不同類型的拖輪,各類型拖輪的數(shù)量分別為{4,8,4,6,4,4}艘,根據(jù)船舶船長(zhǎng)的拖輪配置方法如表1所示。
表1 拖輪與船舶的配比關(guān)系
首先,不同船型所需要的拖輪類型和數(shù)量是有差異的,每種船型所對(duì)應(yīng)的拖輪集合均不同,拖輪集合中的拖輪總數(shù)均大于匹配原則所要求的數(shù)量(1艘或者2艘)。因此,每種船型對(duì)應(yīng)著多個(gè)拖輪子集單元。拖輪作業(yè)的這種特點(diǎn)正好對(duì)應(yīng)著多處理器任務(wù)調(diào)度的一般集合特性。
其次,對(duì)于拖輪調(diào)度問題,由于相同類型的拖輪數(shù)量均大于1(即存在多同類機(jī)的情況),每種船型所對(duì)應(yīng)的拖輪集合中,都存在著多艘相同類型的拖輪。因此,拖輪調(diào)度屬于基于多同類機(jī)的一般集合多處理器任務(wù)調(diào)度問題。
3.1 最大完工時(shí)間的計(jì)算
根據(jù)表1,這里分為兩種情況討論:
(1)第k艘船舶只需要一艘拖輪服務(wù)
假設(shè)分配給第k艘船舶的拖輪類型為i,第i種類型的拖輪數(shù)量為,因此,根據(jù)最短距離作業(yè)的原則,從第i種類型拖輪中,選擇與第k艘船舶的起始位置用Pk_start距離最短的拖輪作為第k艘船舶的服務(wù)拖輪。因此,如果選擇拖輪為第k艘船舶提供作業(yè)服務(wù),那么第k艘船舶在拖輪上的作業(yè)完工時(shí)間表示如下所示。
①限制交叉作業(yè)模式:
(2)第k艘船舶需要兩艘拖輪同時(shí)服務(wù)
假設(shè)被分配的拖輪類型分別是i1和i2,對(duì)于兩種不同類型的拖輪,根據(jù)最短距離作業(yè)的原則,最終選擇的拖輪分別是和。如果拖輪上的上次任務(wù)序號(hào)為k1,拖輪上的上次任務(wù)序號(hào)為k2,那么拖輪上第k1艘的作業(yè)完工時(shí)間表示為,拖輪上第k2艘的作業(yè)完工時(shí)間表示為。因此,可以通過公式(3)、(4)、(5)和(6)得到和,和表示拖輪和在分別完成對(duì)應(yīng)的第k1和k2艘船舶的作業(yè)后,到達(dá)第k艘船舶起始地點(diǎn)的時(shí)間。
①限制允許交叉作業(yè)模式:
由上述公式可以得到不同拖輪配置數(shù)量情況下,第k艘船舶在拖輪上的作業(yè)完工時(shí)間。由于分配在拖輪上的船舶作業(yè)任務(wù)數(shù)量為,拖輪上所分配的所有船舶作業(yè)任務(wù)的最后完工時(shí)間可以表示為,可以由上述公式計(jì)算得到。因此,所有拖輪完成任務(wù)作業(yè)時(shí)間的最大值即為所有船舶作業(yè)任務(wù)的完工時(shí)間,如果用f1表示,則有:
3.2 總作業(yè)油耗的計(jì)算
可以表示如下:
3.3 考慮最大完工時(shí)間和作業(yè)油耗雙目標(biāo)最小的拖輪作業(yè)調(diào)度建模
如果考慮最大完工時(shí)間和作業(yè)油耗的多目標(biāo)優(yōu)化,那么這里采用加權(quán)平均的多目標(biāo)優(yōu)化方法建立拖輪作業(yè)調(diào)度優(yōu)化模型。如果用f表示最大完工時(shí)間和總作業(yè)油耗的加權(quán)平均值,用F表示最大完工時(shí)間和總作業(yè)油耗多目標(biāo)最小化函數(shù)值,那么結(jié)合公式(9)和(13)存在以下關(guān)系:
公式(14)和(15)中,α為加權(quán)系數(shù),且0<α<1。
演化策略算法,也稱為進(jìn)化策略算法,屬于進(jìn)化算法的一種[12-13]。本文采用(μ+λ)-ES演化策略算法來求解拖輪作業(yè)調(diào)度優(yōu)化問題。在(μ+λ)-ES演化策略中,由μ個(gè)父體通過重組和變異產(chǎn)生λ個(gè)后代,然后從μ個(gè)父代和λ個(gè)后代所組成的(μ+λ)個(gè)個(gè)體中,選擇μ個(gè)適應(yīng)值最好的個(gè)體作為下一代的父體。
4.1 基于輪盤賭概率分配的多維實(shí)數(shù)編碼和解碼
4.1.1 多維實(shí)數(shù)編碼
假設(shè)需要拖輪服務(wù)的到港船舶數(shù)量為n艘,演化策略算法的種群數(shù)量為D,那么種群中的第p個(gè)個(gè)體編碼可以定義如表2所示。
表2 個(gè)體編碼
表2中,Vpq表示不同船長(zhǎng)的船型,具體根據(jù)表1,可以將船舶分為100 m以下,100~200 m,200~250 m,250~300 m以及300 m以上5種不同船型。因此,可以分別用數(shù)字1,2,3,4,5表示,即Vpq∈{1,2,3,4,5}。
根據(jù)表1中拖輪與船舶的配比關(guān)系,船舶船長(zhǎng),拖輪可以分為兩大類型:一類是只需要一艘拖輪服務(wù);另外一類是需要兩艘拖輪服務(wù)。因此,apq和bpq為大于0的實(shí)數(shù),可以表示如下:
4.1.2 基于輪盤賭概率分配的解碼
(1)歸一化處理
主要是將基因值apq和bpq經(jīng)過計(jì)算后轉(zhuǎn)換為(0,1)之間的概率值cpq和dpq,計(jì)算方法是將種群內(nèi)各個(gè)個(gè)體相同基因位置上的基因值進(jìn)行累加計(jì)算,然后將各個(gè)個(gè)體基因值與累加值相除即可。
(2)根據(jù)概率分配拖輪類型
對(duì)于每種船型,首先要計(jì)算其對(duì)應(yīng)的拖輪類型中每種拖輪所對(duì)應(yīng)的輪盤賭概率,然后根據(jù)概率值cpq和dpq,分配對(duì)應(yīng)的拖輪類型。
假設(shè)個(gè)體編碼中船舶q的船型Vpq對(duì)應(yīng)的拖輪集合為Sq,集合Sq中有xq種不同的拖輪類型。集合Sq中xq種不同類型拖輪被分配船型Vpq的概率均是相等的,即概率為1/xq。因此,設(shè)定Sq中每種不同類型拖輪被分配船舶的輪盤賭概率為:
4.2 基于三點(diǎn)交叉互換的重組算子
重組算子采用三點(diǎn)交叉互換的雜交方法,以雙親雙子法產(chǎn)生后代個(gè)體。首先隨機(jī)從μ個(gè)個(gè)體中選擇2個(gè)個(gè)體進(jìn)行重組操作,然后在2個(gè)父代個(gè)體中隨即選擇3個(gè)交叉互換點(diǎn),從而將父代個(gè)體分隔為4段,最后采取隔段互換的方式進(jìn)行互換,從而得到2個(gè)子代個(gè)體。具體如圖1所示。
4.3 基于個(gè)體內(nèi)部基因互換的變異算子
變異操作采用的方法:在子代個(gè)體中,隨機(jī)選擇兩種船舶船型相同的基因值,如果其拖輪分配不同,將它們的拖輪分配進(jìn)行互換,具體如圖2所示。對(duì)于每個(gè)子代個(gè)體,變異算子中設(shè)定隨機(jī)選擇基因值互換多次。
圖2 基因值互換的變異算子
在船舶靠離港作業(yè)過程中,不同船型的拖輪作業(yè)時(shí)間有一定差異。根據(jù)船型的大小,隨機(jī)產(chǎn)生60艘船舶的相關(guān)作業(yè)數(shù)據(jù),如表3所示。
表3 60艘船舶的作業(yè)數(shù)據(jù)
表4 不同位置之間的行駛時(shí)間min
表5 不同加權(quán)系數(shù)下最大完工時(shí)間(f1)和總作業(yè)油耗(f2)雙目標(biāo)優(yōu)化的計(jì)算結(jié)果
表3中,分別用數(shù)字1,2,3,4,5表示5種不同船長(zhǎng)的船型,作業(yè)時(shí)間則主要是指船舶在靠泊、離泊和移泊時(shí)的拖輪作業(yè)時(shí)間。
T1,T2,T3,T4,T5,T6,T7和T8分別表示8個(gè)不同的碼頭位置,T0表示船舶進(jìn)港或離港時(shí)與拖輪在航道會(huì)合的位置。為了計(jì)算方便,這9種不同的位置以及與兩個(gè)拖輪基地之間的距離用行駛時(shí)間來代替,具體數(shù)據(jù)如表4所示。所有6種類型的拖輪平均分配在兩個(gè)拖輪基地,即兩個(gè)拖輪基地的拖輪類型和數(shù)量是相同的。
在拖輪作業(yè)過程中,如果限制兩個(gè)拖輪基地的拖輪進(jìn)行交叉作業(yè),那么此時(shí),拖輪基地1的拖輪主要針對(duì)T1,T2,T3,T4這4個(gè)碼頭的船舶進(jìn)行服務(wù);而拖輪基地2的拖輪則針對(duì)T5,T6,T7,T8這4個(gè)碼頭的船舶進(jìn)行服務(wù)。
設(shè)定表1中6種拖輪的運(yùn)行油耗依次為{0.2,0.3,0.36,0.4,0.56,0.64}(t/h)。
設(shè)置演化策略算法的最大迭代次數(shù)為1 000,父代種群數(shù)量μ為50,子代種群數(shù)量λ為40,分別設(shè)置加權(quán)系數(shù)α= {0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9},用公式(15)所建立的以最大完工時(shí)間和總作業(yè)油耗雙目標(biāo)最小的優(yōu)化調(diào)度模型,不同加權(quán)系數(shù)設(shè)置下連續(xù)優(yōu)化計(jì)算20次,計(jì)算結(jié)果如表5所示。
從表5的計(jì)算結(jié)果看,采用兩種不同的作業(yè)模式,不同加權(quán)系數(shù)情況下,雙目標(biāo)優(yōu)化找到的最小值中,最大完工時(shí)間和總作業(yè)油耗均好于相對(duì)應(yīng)作業(yè)模式下的仿真運(yùn)行結(jié)果。其中,最大完工時(shí)間最小值相比仿真運(yùn)行結(jié)果取得較大的改善,不同作業(yè)模式下均減少了約16%。
同時(shí),不同的作業(yè)模式對(duì)結(jié)果也有著不同的影響。其中,允許交叉作業(yè)模式下,雙目標(biāo)優(yōu)化情況下的最大完工時(shí)間最小值明顯好于限制交叉作業(yè)模式。這說明,盡管使用兩個(gè)拖輪停泊基地,如果采用允許交叉作業(yè)模式將更能充分利用拖輪資源。
拖輪調(diào)度是港口生產(chǎn)系統(tǒng)的一個(gè)重要組成部分,其優(yōu)化問題直接影響船舶能否及時(shí)進(jìn)出。本文結(jié)合多處理器任務(wù)調(diào)度理論,以最大完工時(shí)間和總作業(yè)油耗雙目標(biāo)最小化為目標(biāo),對(duì)面向多停泊基地的拖輪作業(yè)調(diào)度問題進(jìn)行了建模分析,并在拖輪調(diào)度模型中考慮了兩種不同的作業(yè)模式。采用演化策略算法對(duì)多停泊基地拖輪作業(yè)調(diào)度多目標(biāo)優(yōu)化問題進(jìn)行了計(jì)算,并對(duì)演化策略算法的編碼和解碼、重組算子和變異算子進(jìn)行了設(shè)計(jì)。計(jì)算結(jié)果表明,演化策略算法可以得到較好的優(yōu)化結(jié)果。
[1]董良才,徐子奇,宓為建.基于遺傳算子粒子群算法的拖輪動(dòng)態(tài)調(diào)度[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2012,42(6):122-133.
[2]何濤,朱宏輝.遺傳算法在拖輪調(diào)度中的應(yīng)用[J].物流技術(shù),2008,27(4):138-139.
[3]陸海波.寧波港拖輪船隊(duì)優(yōu)化配置研究[D].上海:上海海事大學(xué),2007.
[4]劉志雄,王少梅.港口拖輪作業(yè)的計(jì)算機(jī)仿真研究[J].系統(tǒng)仿真學(xué)報(bào),2004,16(1):45-48.
[5]劉莎,楊宏來.基于任務(wù)緊迫度的多處理器任務(wù)調(diào)度算法[J].電子測(cè)量技術(shù),2012,35(9):45-48.
[6]Jin S Y,Schiavone G,Turgut D.A performance study of multiprocessor task scheduling algorithms[J].Journal of Supercomputing,2008,43(1):77-97.
[7]軒華,唐立新.帶多處理器任務(wù)的動(dòng)態(tài)混合流水車間調(diào)度問題[J].計(jì)算機(jī)集成制造系統(tǒng),2007,13(11):2254-2260.
[8]Ying K C,Lin S W.Multiprocessor task scheduling in multistage hybrid flow-shops:an ant colony system approach[J]. International Journal of Production,2006,44(16):3161-3177.
[9]Ercan M F,O?uz C P.Performance of local search heuristics on scheduling a class of pipelined multiprocessor tasks[J]. Computers and Electrical Engineering,2005,31(8):537-555.
[10]Zhong Y,Yang J.A hybrid genetic algorithm for tasks scheduling in parallel multiprocessor systems[J].Journal of Fudan University:Natural Science,2004,43(5):918-922.
[11]O?uz C,Zinder Y,Do V,et al.Hybrid flow-shop scheduling problems with multiprocessor task systems[J].European Journal of Operations Research,2004,152(1):115-131.
[12]畢志升,王甲海,印鑒.基于差分演化算法的軟子空間聚類[J].計(jì)算機(jī)學(xué)報(bào),2012,35(10):2116-2128.
[13]牛思先,蘇玉剛.基于多目標(biāo)演化算法的交通系統(tǒng)實(shí)時(shí)優(yōu)化技術(shù)[J].統(tǒng)計(jì)與決策,2011(1):61-64.
WANG Wei1,ZHAO Hong1,LI Qiang2
1.School of Economy,Tianjin Polytechnic University,Tianjin 300387,China
2.Technology and Equipment Department,Tianjin Port(Group)Co.,Ltd.,Tianjin 300461,China
The tugboat scheduling is a typical multiprocessor tasks scheduling problem.A kind of port tugboat scheduling problem with multi-anchorage bases and different operation modes is presented,and the tugboat scheduling optimization model which objective is to minimize both the maximum completion time and total operation fuel wastage of all tugboats is described.The evolutionary strategy algorithm is applied to optimize the tugboat operation scheduling,and the multi-dimension real encoding and decoding based on the roulette probability assignment is introduced.Finally,the calculation results prove that the evolutionary strategy algorithm can effectively optimize the port tugboat scheduling problem,and the optimization results of the maximum completion time are improved and reduced about 16%than the simulation results on condition of different tugboat operation modes.Moreover,the calculation results show that different operation modes have much effect on the tugboat scheduling.
tugboat scheduling;multi-anchorage bases;multiprocessor tasks;evolutionary strategy algorithm;multi-objectives optimization
拖輪調(diào)度是典型的多處理器任務(wù)調(diào)度問題,針對(duì)多停泊基地和不同作業(yè)模式下的拖輪調(diào)度,以最大完工時(shí)間和總作業(yè)油耗最小化為目標(biāo),建立了拖輪調(diào)度多目標(biāo)優(yōu)化模型。采用演化策略算法對(duì)多停泊基地拖輪調(diào)度優(yōu)化問題進(jìn)行計(jì)算,提出一種基于輪盤賭概率分配的編碼和解碼方法。計(jì)算結(jié)果表明了演化策略算法的有效性和可行性,優(yōu)化后的最大完工時(shí)間最小值相比仿真運(yùn)行結(jié)果取得較大的改善,不同作業(yè)模式下均減少了約16%;計(jì)算結(jié)果還表明不同作業(yè)模式對(duì)拖輪調(diào)度結(jié)果會(huì)產(chǎn)生較大影響。
拖輪調(diào)度;多停泊基地;多處理器任務(wù);演化策略算法;多目標(biāo)優(yōu)化
A
TP39
10.3778/j.issn.1002-8331.1302-0008
WANG Wei,ZHAO Hong,LI Qiang.Multi-objectives optimization for port tugboat scheduling considering multi-anchorage bases.Computer Engineering and Applications,2013,49(13):8-12.
國(guó)家自然科學(xué)基金(No.70801047);國(guó)家軟科學(xué)研究計(jì)劃項(xiàng)目(No.2011GXS2D015);天津市哲學(xué)社會(huì)科學(xué)規(guī)劃項(xiàng)目(No.TJYY11-2-042)。
王?。?980—),女,博士,副教授,碩士生導(dǎo)師,研究方向?yàn)橄到y(tǒng)優(yōu)化,機(jī)器學(xué)習(xí),計(jì)量經(jīng)濟(jì);趙宏(1963—),女,博士,教授,研究方向?yàn)楫a(chǎn)業(yè)經(jīng)濟(jì)學(xué);李強(qiáng)(1982—),男,博士后,高級(jí)工程師,研究方向?yàn)楦劭谠O(shè)備管理,生產(chǎn)調(diào)度優(yōu)化。E-mail:wangweiuser@126.com
2013-02-04
2013-03-24
1002-8331(2013)13-0008-05
CNKI出版日期:2013-03-29http://www.cnki.net/kcms/detail/11.2127.TP.20130329.1701.021.html