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

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

集成岸橋分派的在線泊位分配問(wèn)題

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

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

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

岸橋分派；泊位分配；在線算法；競(jìng)爭(zhēng)比

0 引 言

1 問(wèn)題描述與基本符號(hào)

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

(1)

2 算法設(shè)計(jì)與競(jìng)爭(zhēng)比分析

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

定理1 當(dāng)岸橋分派方案為2-2-0時(shí)，任意在線泊位分配算法的競(jìng)爭(zhēng)比至少是5/4；當(dāng)岸橋分派方案為2-1-1或1-2-1時(shí)，任意在線泊位分配算法的競(jìng)爭(zhēng)比至少是2.

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

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

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

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

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

定理2 算法H的競(jìng)爭(zhēng)比不超過(guò)5/4且是最優(yōu)的.

(2)

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

圖1 最后一個(gè)貨輪需求情況

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

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

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

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

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

圖2 岸橋分派固定方案

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

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

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

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

4 結(jié)束語(yǔ)

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

[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

國(guó)家自然科學(xué)基金資助項(xiàng)目(11571252，11401149)；浙江省自然科學(xué)基金資助項(xiàng)目(LY16A010015)

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

O221.7

A

1001-9146(2017)04-0086-04