集成岸橋分派的在線泊位分配問題

楊 帆，張 安，陳 永，陳光亭

(杭州電子科技大學理學院，浙江 杭州 310018)

集成岸橋分派的在線泊位分配問題

楊 帆，張 安，陳 永，陳光亭

(杭州電子科技大學理學院，浙江 杭州 310018)

主要研究一類集成岸橋分派的在線泊位分配問題.考慮了3個連續(xù)泊位、4臺岸橋的情形，以極小化集裝箱貨輪的總處理(裝載、卸載任務(wù))時間為目標函數(shù)，證明了最好可能的在線分派方案是2-2-0，并設(shè)計了競爭比為5/4的最優(yōu)在線泊位分配算法.

岸橋分派；泊位分配；在線算法；競爭比

0 引 言

1 問題描述與基本符號

記3個連續(xù)的泊位分別為b1,b2,b3，考慮到泊位空間的限制以及岸橋的安全距離要求，一般假定每個泊位至多分派兩臺岸橋[4-5].因此，4臺岸橋在3個連續(xù)泊位上的分派方案只可能有3種：2-2-0，2-1-1，1-2-1(依據(jù)下文貨輪的類型，2-0-2分派方案相對于2-2-0分派方案屬于劣勢分派方案，因此不再考慮2-0-2方案).根據(jù)?？坎次坏那闆r，集裝箱貨輪也分為停靠1個泊位的小型貨輪與?？?個泊位的大型貨輪兩種類型.為簡化模型，記小型貨輪的裝卸需求量為1，大型貨輪的裝卸需求量為Δ，且一般有Δ≥2[4-5].如果一艘大(小)型貨輪?？康牟次簧瞎灿衜(m≥1)臺岸橋，那么它的處理時間為Δ/m(1/m).在線問題是指貨輪及其需求是實時產(chǎn)生的，決策者只有在需求產(chǎn)生后才能決定如何分配泊位.為方便起見，假設(shè)貨輪的需求量按I=(r1,r2,…,rn)順序到達，其中ri=1或Δ，目標是極小化這批需求的總處理時間.由于岸橋總數(shù)為4臺，因此最少處理時間C*(I)必然滿足：

(1)

2 算法設(shè)計與競爭比分析

首先給出在3種可能的岸橋分派方案下在線泊位分配問題的下界.

定理1 當岸橋分派方案為2-2-0時，任意在線泊位分配算法的競爭比至少是5/4；當岸橋分派方案為2-1-1或1-2-1時，任意在線泊位分配算法的競爭比至少是2.

接著給出岸橋分派方案為2-2-0時的最優(yōu)在線泊位分配算法.

算法H 1)若ri=Δ，則將其放在泊位b1,b2上盡可能早地完成裝卸需求；

2)若ri=1，則將其按照最早完工規(guī)則分配在b1或b2上.

引理1 算法H在執(zhí)行過程中至多產(chǎn)生一個空閑時段且其時長為1/2.

證明 顯然,占用2個泊位的大貨輪需求不可能產(chǎn)生空閑時段，小貨輪產(chǎn)生的空閑時長必然等于其處理時間1/2.假設(shè)算法H在執(zhí)行過程中產(chǎn)生了2個時長為1/2的空閑時段，根據(jù)算法第2步，產(chǎn)生第二個空閑時段的小貨輪需求將被分配在第一個時長為1/2的空閑時段，因此不可能產(chǎn)生新的空閑時段，與算法H在執(zhí)行過程中產(chǎn)生了2個時長為1/2的空閑時段的假設(shè)矛盾！所以結(jié)論成立.證畢.

定理2 算法H的競爭比不超過5/4且是最優(yōu)的.

(2)

下面不妨假設(shè)最后一個貨輪需求rn決定算法的目標值，對rn的取值討論如下，最后一個貨輪需求情況如圖1所示.圖1(a)中陰影部分表示空閑時段.

圖1 最后一個貨輪需求情況

綜上，算法H的競爭比不超過5/4.由定理1，算法H是最優(yōu)的.證畢.

定理1和定理2的結(jié)果還表明，對應(yīng)在線泊位分配的最好可能的岸橋分派方案是2-2-0.然而對離線泊位分配問題，用以下實例說明每一種岸橋分派方案都可能是最優(yōu)的.

表1給出3個實例，對每一個例子分別可以得出在3種岸橋分派方案下的最優(yōu)完工時間，通過比較3種岸橋分派方案的完工時間得出最優(yōu)岸橋分派方案，表1中“*”對應(yīng)最優(yōu)方案.

3 岸橋分派方案可動態(tài)調(diào)整的討論

上一節(jié)將岸橋分派方案的選取與泊位的在線分配分別獨立考慮，本節(jié)討論岸橋分派方案可以動態(tài)調(diào)整的情形，即在泊位分配過程中允許實時調(diào)整岸橋分派方案.對離線問題，下述實例表明岸橋方案的動態(tài)調(diào)整可以顯著減少目標值.

圖2 岸橋分派固定方案

圖3 岸橋分派可動態(tài)調(diào)整方案

對在線泊位分配，有以下結(jié)論表明.

定理3 如果泊位分配過程中岸橋分派方案可以動態(tài)調(diào)整，任意在線泊位分配算法的競爭比仍不小于5/4.

由定理3，即使允許動態(tài)調(diào)整岸橋分派方案，選取固定岸橋分派方案2-2-0的在線泊位分配算法H仍是最優(yōu)的.從而表明，最好可能的岸橋方案是固定方案2-2-0.

4 結(jié)束語

本文研究了一類集成岸橋分派的在線泊位分配問題.對4臺岸橋3個泊位這一問題給出了競爭比為5/4的最優(yōu)在線泊位分配算法，并證明了2-2-0為最好可能的岸橋分派方案.下一步將對岸橋與泊位的數(shù)量進行進一步推廣.

[1]PARK Y M, KIM K H. A scheduling method for berth and quay cranes[J]. OR spectrum, 2003,25(1):1-23.

[2]BIERWIRTH C, MEISEL F. A survey of berth allocation and quay crane scheduling problems in container terminals[J]. European Journal of Operational Research, 2010,202(3):615-627.

[3]BLAZEWICZ J, CHENG T C E, MACHOWIAK M, et al. Berth and quay crane allocation: a moldable task scheduling model[J]. Journal of the Operational Research Society, 2011,62(7):1189-1197.

[4]ZHENG F, QIAO L, LIU M. An Online Model of Berth and Quay Crane Integrated Allocation in Container Terminals[M].Houston: Springer International Publishing, 2015:721-730.

[5]PAN J, XU Y. Online Integrated Allocation of Berths and Quay Cranes in Container Terminals with 1-Lookahead[C]//International Computing and Combinatorics Conference. Springer International Publishing, 2015:402-416.

Online Berth Allocation Problem Integrating Quay Cranes Assignment

YANG Fan, ZHANG An, CHEN Yong, CHEN Guangting

(SchoolofScience,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

This paper studies an online over-list model of integrated allocation of 3 berths and 4 quay cranes in a container terminal. The objective is to minimize the maximum completion time for loading or unloading container vessels. It proves that 2-2-0 is the best possible quay cranes assignment(QCA) scheme for online berth allocation. In addition, an optimal online algorithm with competitive ratio 5/4 is provided.

quay cranes assignment; berth allocation; online algorithm; competitive ratio

10.13954/j.cnki.hdu.2017.04.019

2016-12-02

國家自然科學基金資助項目(11571252，11401149)；浙江省自然科學基金資助項目(LY16A010015)

楊帆(1992-)，女，河南新鄉(xiāng)人，碩士研究生，組合優(yōu)化.通信作者：陳光亭教授，E-mail：gtchen@hdu.edu.cn.

O221.7

A

1001-9146(2017)04-0086-04