有限預(yù)知信息下集裝箱碼頭泊位與岸橋聯(lián)合在線調(diào)度

鄭斐峰，喬龍亮，黃基誕

（東華大學(xué) 旭日工商管理學(xué)院，上海 200051）

根據(jù)英國(guó)航運(yùn)咨詢公司德魯里（Drewry）2015年的CPI報(bào)告，全球班輪準(zhǔn)班率連續(xù)兩月下滑；最新的數(shù)據(jù)顯示，亞歐、跨太平洋和跨大西洋航線的總體準(zhǔn)班率從2014年10月的62%，11 月的64%下降至12月的58%。12月份的準(zhǔn)班率也是2014年8月（55%）以來(lái)的最低水準(zhǔn)[1]。當(dāng)班輪出現(xiàn)延誤之后，要想趕上船期表所計(jì)劃的時(shí)間點(diǎn)，承運(yùn)人需要付出巨大的額外燃油成本。此時(shí)，節(jié)省燃油、降低航次成本可能是其最佳的選擇，從而導(dǎo)致了準(zhǔn)班率的一定下降。站在港口角度，為了保障碼頭關(guān)鍵資源的利用率，往往通過(guò)增加服務(wù)加班船來(lái)應(yīng)對(duì)主干船舶準(zhǔn)班率的下降。在包括上海洋山港三期碼頭的一些港口運(yùn)營(yíng)中，加班船的具體調(diào)度往往不在港口的事先計(jì)劃表中，這意味著對(duì)于港口，加班船具有較強(qiáng)的動(dòng)態(tài)到達(dá)、實(shí)時(shí)服務(wù)的特征。考慮到泊位和岸橋是碼頭最為關(guān)鍵的兩種調(diào)度資源，本文將針對(duì)這兩種資源進(jìn)行服務(wù)加班船的情形設(shè)計(jì)聯(lián)合調(diào)度優(yōu)化方案。

國(guó)內(nèi)外許多學(xué)者對(duì)泊位分配（Berth Allocation Problem，BAP）、岸橋分配（Quay Crane Assignment Problem，QCAP），以及泊位與岸橋的聯(lián)合分配調(diào)度（BAP-QCAP）等問(wèn)題開(kāi)展了大量研究[2-4]。Imai等[2]將泊位資源劃分為離散、連續(xù)和混合型等3種類型，其中，一個(gè)混合型泊位在每個(gè)時(shí)刻要么服務(wù)一艘大型船舶，要么可以同時(shí)服務(wù)2～3艘小型船舶。例如，深圳蛇口的媽灣港根據(jù)碼頭地理特征采用的就是混合型泊位設(shè)計(jì)。對(duì)于BAP-QCAP 聯(lián)合調(diào)度問(wèn)題，Yang等[5]運(yùn)用兩階段決策思想，采用兩個(gè)內(nèi)循 環(huán) 分 別 求 解 BAP 和 QCAP 子 問(wèn) 題。Turkogullari等[6]對(duì)于包括船舶靠泊位置偏離值、等待時(shí)間和離港延遲時(shí)間的總成本優(yōu)化目標(biāo)構(gòu)建整數(shù)規(guī)劃模型。Xiao等[7]將已抵港的船舶根據(jù)服務(wù)狀態(tài)劃分為3類，并采用滾動(dòng)時(shí)域求解算法進(jìn)行求解。Vacca等[8]假設(shè)船舶服務(wù)時(shí)間取決于所分配岸橋數(shù)量，對(duì)所構(gòu)建模型設(shè)計(jì)了分枝定價(jià)精確算法。一些學(xué)者考慮了調(diào)度過(guò)程中的干擾因素并構(gòu)建相關(guān)模型展開(kāi)研究。孫彬等[9]對(duì)于離散泊位且船舶抵港時(shí)間不一的調(diào)度情形，探討了不確定因素的影響作用，對(duì)于最小化所有船舶總延誤時(shí)間的優(yōu)化目標(biāo)設(shè)計(jì)了具有系統(tǒng)魯棒性的調(diào)度策略。曾慶成等[10]對(duì)于連續(xù)型BAP-QCAP 問(wèn)題，著重探討了不確定干擾因素對(duì)調(diào)度過(guò)程的影響情況以及應(yīng)對(duì)策略，建立了兩階段干擾管理決策模型。

現(xiàn)有的研究大都假設(shè)船舶需求信息事先全部已知，然而，通過(guò)上海洋山港的實(shí)地調(diào)研發(fā)現(xiàn)，因?yàn)榧影啻拇罅看嬖?，即使是上海洋山港大型深水碼頭，其船期表也是每天動(dòng)態(tài)調(diào)整并安排許多泊位用于服務(wù)新抵港的加班船；在其排期密度表中，加班船的服務(wù)數(shù)量比例甚至達(dá)到1/3。加班船不同于主干船的服務(wù)特點(diǎn)，后者提前至少一個(gè)工作日就確定準(zhǔn)確抵港時(shí)間，并在碼頭制定服務(wù)計(jì)劃之前提早一天抵港并在錨地等待；加班船的服務(wù)具有明顯的動(dòng)態(tài)實(shí)時(shí)特征，這源于碼頭事先并不制定每艘加班船的具體服務(wù)時(shí)間計(jì)劃，只是提供一定的泊位和岸橋資源供所有加班船使用的做法。因此，對(duì)每一艘加班船的服務(wù)安排，碼頭泊位與岸橋資源的調(diào)度顯現(xiàn)出了很強(qiáng)的實(shí)時(shí)性。

Zhang等[11]將在線理論分析框架引入了集裝箱碼頭調(diào)度問(wèn)題，對(duì)上述船舶抵港時(shí)間順序不確定的情形進(jìn)行刻畫(huà)，并探究了岸橋的動(dòng)態(tài)分配優(yōu)化方案。結(jié)合岸橋具有不可交叉移動(dòng)的操作特征，以最大完工時(shí)間為優(yōu)化目標(biāo)構(gòu)建了over-list在線模型，并給出了漸近競(jìng)爭(zhēng)比為m/[log 2（m+1）]的最優(yōu)在線策略，其中m為岸橋數(shù)量。在線理論主要用于刻畫(huà)現(xiàn)實(shí)中，決策者無(wú)法獲知問(wèn)題的全部信息而又必需進(jìn)行實(shí)時(shí)決策的一類多次決策問(wèn)題。決策者只能逐步獲取信息，同時(shí)根據(jù)已有的信息對(duì)服務(wù)請(qǐng)求作出回應(yīng)，其決策效果通常是與信息完全已知情形下的最優(yōu)效果進(jìn)行比較。

本文采用Zhang等[11]的建模方法，運(yùn)用在線理論來(lái)刻畫(huà)泊位與岸橋的聯(lián)合調(diào)度，根據(jù)船舶動(dòng)態(tài)到達(dá)特征構(gòu)建相應(yīng)的online-oner-list在線模型。結(jié)合碼頭事先掌握一部分待服務(wù)船舶的信息的實(shí)際情況，構(gòu)建有限預(yù)知信息下的泊位與岸橋聯(lián)合調(diào)度在線模型，并探討僅預(yù)知后續(xù)一艘船舶需求信息的特定情形，該研究有助于對(duì)預(yù)知多艘船舶的一般情形設(shè)計(jì)調(diào)度計(jì)劃。帶有預(yù)知信息的在線調(diào)度模型在生產(chǎn)調(diào)度等領(lǐng)域已有不少相關(guān)研究。Mandelbaum等[12]探究了平行機(jī)環(huán)境下，在線策略安排每個(gè)請(qǐng)求時(shí)預(yù)知后續(xù)h個(gè)請(qǐng)求信息的情形，研究結(jié)論表明，預(yù)知能力可以改進(jìn)在線策略的競(jìng)爭(zhēng)性能。Zheng等[13]考慮了決策時(shí)預(yù)知后續(xù)LD（≥0）個(gè)單位時(shí)間內(nèi)所有到達(dá)請(qǐng)求的在線模型，對(duì)于可中斷和不可中斷兩種情形分別探討了預(yù)知能力為0≤LD≤2和0≤LD≤1的在線策略。

1 問(wèn)題描述與基本定義

1.1 問(wèn)題描述及模型假設(shè)

對(duì)于集裝箱碼頭混合型泊位，由于受限制于岸線地理?xiàng)l件約束，其泊位岸線長(zhǎng)度通常約在300～400 m，而每個(gè)岸橋自身寬度約為60 m，加上操作時(shí)的安全距離要求，故一個(gè)混合型泊位一般配置不超過(guò)6個(gè)岸橋，本文主要考察配置5 個(gè)岸橋的情形。對(duì)于加班船，其長(zhǎng)度一般處于100～300 m。鑒于此，考慮如下的混合型泊位參數(shù)：該泊位可以同時(shí)靠泊1艘大船與1 艘小船，或者同時(shí)靠泊3 艘小船。為了方便表述，將這一混合型泊位刻畫(huà)為左、中、右3個(gè)相鄰的小泊位，從而小船（小請(qǐng)求）占用1個(gè)泊位而大船（大請(qǐng)求）占用2 個(gè)相鄰泊位。在onlineover-list模型下，請(qǐng)求信息在零時(shí)刻逐個(gè)到達(dá)，決策者在每個(gè)請(qǐng)求ri釋放時(shí)需立即決策其泊位及岸橋的分配，以及確定服務(wù)時(shí)間段，決策做出之后不可更改；在預(yù)知未來(lái)1個(gè)請(qǐng)求的情景下，在線策略在rn釋放時(shí)即可獲知序列長(zhǎng)度即n取值。后文討論基于如下5個(gè)基本假設(shè)：

（1）所有岸橋共享一條平行于泊位的移動(dòng)軌道，因而每個(gè)岸橋左右相對(duì)位置始終不變。

（2）系統(tǒng)中只有兩種請(qǐng)求，小請(qǐng)求、大請(qǐng)求的任務(wù)量分別為1和Δ（≥2），分別記ri=1和ri=Δ。

（3）左、中、右這3個(gè)離散泊位記為b1、b2、b3，從左至右的岸橋標(biāo)為q1、q2、q3、q4、q5。在任一時(shí)刻，每個(gè)泊位及岸橋只能服務(wù)1個(gè)請(qǐng)求。小請(qǐng)求占用1個(gè)泊位且至多由2個(gè)相鄰岸橋進(jìn)行服務(wù)，大請(qǐng)求占用2個(gè)相鄰泊位且至多由4個(gè)相鄰岸橋進(jìn)行服務(wù)。

（4）若請(qǐng)求ri由m i≥1個(gè)岸橋進(jìn)行服務(wù)，則其服務(wù)時(shí)長(zhǎng)等于ri/mi[8]。

（5）當(dāng)請(qǐng)求ri（1≤i≤n-1）釋放時(shí)可以預(yù)知下一個(gè)請(qǐng)求ri+1的信息；rn釋放時(shí)可得知序列長(zhǎng)度n的值。

模型的優(yōu)化目標(biāo)是最小化最后一艘船舶的完工時(shí)間。運(yùn)用四參數(shù)描述法[3]，將本文所構(gòu)建的上述模型標(biāo)記為

其中：hybr表示混合型泊位；3B、5QC表示3個(gè)離散泊位和5個(gè)岸橋資源；online-over-list表示請(qǐng)求逐個(gè)釋放的在線模型；LD=1表示在線策略可以預(yù)知后續(xù)一個(gè)請(qǐng)求；Cmax為最大完工時(shí)間的目標(biāo)函數(shù)。

1.2 競(jìng)爭(zhēng)比定義及參數(shù)符號(hào)說(shuō)明

一般運(yùn)用競(jìng)爭(zhēng)分析方法來(lái)求解在線問(wèn)題，即假定存在一個(gè)事先掌握所有請(qǐng)求信息的離線敵手，通過(guò)控制請(qǐng)求的輸入序列，使得在線策略執(zhí)行性能盡可能的差。通常采用競(jìng)爭(zhēng)比這一指標(biāo)來(lái)度量在線策略的性能[14]。對(duì)于某一在線策略A，定義ΩA為其所有可能的請(qǐng)求輸入序列的集合；給定任一序列σ∈ΩA，令Cmax（σ）為策略A服務(wù)完成序列σ的最大完工時(shí)間，C*（σ）為信息完全的情形下最優(yōu)方案對(duì)應(yīng)的目標(biāo)函數(shù)值。將策略A的競(jìng)爭(zhēng)比定義為

稱A具有競(jìng)爭(zhēng)比ρ或稱A是ρ-競(jìng)爭(zhēng)的。用競(jìng)爭(zhēng)比下界表示所有在線策略對(duì)于該問(wèn)題可能達(dá)到的最小競(jìng)爭(zhēng)比。如果某一個(gè)在線策略的競(jìng)爭(zhēng)比達(dá)到了競(jìng)爭(zhēng)比下界值，則稱其為最優(yōu)在線策略。

下面列出模型討論中主要運(yùn)用的變量符號(hào)：

Cmax（σ）——在線策略的目標(biāo)函數(shù)值

C*（σ）——離線策略的目標(biāo)函數(shù)值

ti，1——ri釋放時(shí)至少一個(gè)泊位完成此前分配至該泊位的所有請(qǐng)求的最早完工時(shí)間

ti，2，ti，3——ri釋放時(shí)2、3個(gè)連續(xù)泊位完成此前分配至各自泊位所有請(qǐng)求的最早完工時(shí)間

Ci，j（1≤j≤3）——ri釋放時(shí)b j泊位完成此前所分配的所有請(qǐng)求的最早完工時(shí)間

si，ei—— 請(qǐng)求ri的服務(wù)開(kāi)始時(shí)間和結(jié)束時(shí)間

T a= [t1，t2）—— 在線策略分配大請(qǐng)求ri導(dǎo)致某一泊位服務(wù)該請(qǐng)求前出現(xiàn)可利用空閑時(shí)間段T a，滿足t2=si=t1+1/2；初始化T a= [0，0）

對(duì)于

模型，所設(shè)計(jì)的在線策略在服務(wù)事先將每個(gè)岸橋與具體泊位進(jìn)行固定配置，即將左側(cè)的2個(gè)泊位b1、b2分別配置2個(gè)岸橋q1、q2和q3、q4，而最右側(cè)的b3泊位配置1個(gè)岸橋q5。因此，如果某個(gè)大請(qǐng)求被分配至泊位b2、b3，則將會(huì)由3個(gè)岸橋q3、q4、q5進(jìn)行服務(wù)。下面將對(duì)大請(qǐng)求具有任務(wù)量Δ≥3和2≤Δ＜3的兩種情形分別設(shè)計(jì)調(diào)度策略。

2 Δ≥3的情形

2.1 在線策略設(shè)計(jì)

基于前面對(duì)岸橋與泊位兩種資源的固定配置方案，在線策略只需決策分配請(qǐng)求至哪幾個(gè)泊位以及相應(yīng)的服務(wù)啟動(dòng)時(shí)間。下面給出在線策略GR1（Greedy-1）的具體描述。

策略GR1若ri=rn，由于預(yù)知沒(méi)有后續(xù)請(qǐng)求，故分配該請(qǐng)求至某一泊位以最小化Cmax。若有多個(gè)泊位均可導(dǎo)致相同目標(biāo)函數(shù)值，則分配給下標(biāo)最小的泊位；否則，若1≤i＜n，由于預(yù)知后續(xù)請(qǐng)求ri+1，分如下兩種情形進(jìn)行決策。

C1ri=Δ。對(duì)于ri+1=1 或Δ，令啟動(dòng)時(shí)間si=ti，2，將ri分配至左邊2個(gè)泊位b1、b2。

C2ri=1。

C2.1Ci，1-Ci，2=1/2。令si=Ci，2，將ri分配至b2泊位；

C2.2Ci，1=Ci，2。若ri+1=1，則令si=Ci，1，將ri分配至b1泊位；若ri+1=Δ，則令si=Ci，3，并將ri分配至b3泊位。

根據(jù)C2.1、C2.2 兩種情形，若ri（1≤i＜n）是小請(qǐng)求且被分配至b1泊位，則根據(jù)情形C2.2可知下一請(qǐng)求ri+1=1，從而ri+1滿足C2.1條件并被分配至b2泊位。ri+1分配之后，b1、b2泊位同時(shí)從ei+1時(shí)刻進(jìn)入空閑狀態(tài)。因此，任意一個(gè)大請(qǐng)求ri=Δ釋放時(shí)均有Ci，1=Ci，2。上述分析表明，b1、b2泊位及相應(yīng)的4個(gè)岸橋在完成其所分配的所有任務(wù)之前不會(huì)出現(xiàn)空閑狀態(tài)。

2.2 策略GR1的競(jìng)爭(zhēng)分析

下面的定理給出策略GR1在Δ≥3情形下的競(jìng)爭(zhēng)性能。

定理1對(duì)于問(wèn)題

當(dāng)Δ≥3時(shí)，策略GR1具有競(jìng)爭(zhēng)比5/4。

證明給定任一請(qǐng)求輸入序列σ= ｛r1，r2，…，rn｝，令Cmax（σ）為策略GR1的最大完工時(shí)間，C*（σ）為離線最優(yōu)方案對(duì)應(yīng)的目標(biāo)函數(shù)值。根據(jù)GR1策略描述，所有大請(qǐng)求均被分配至左邊2個(gè)泊位b1、b2，而且在完成最后一個(gè)大請(qǐng)求之前，左邊2個(gè)泊位與4個(gè)岸橋一直處于服務(wù)狀態(tài)。下面根據(jù)最后一個(gè)請(qǐng)求rn的分配結(jié)果討論兩種情形：

（1）rn分配至b1或b2泊位。

②rn=1。由于rn分配至b1或b2泊位，其加工長(zhǎng)度為1/2。如果Cmax（σ）=Cn，3（＞en），則分析同情形①；否則，如果Cmax（σ）=en= min｛Cn，1，Cn，2｝+1/2，當(dāng)序列σ包含至多1 個(gè)大請(qǐng)求時(shí)，容易驗(yàn)證Cmax（σ）/C*（σ）≤5/4。當(dāng)σ包含至少2個(gè)大請(qǐng)求時(shí)，由于大請(qǐng)求均分配至泊位b1、b2，min｛Cn，1，Cn，2｝≥2Δ/4≥3/2，同時(shí)，Cn，3＞min｛Cn，1，Cn，2｝-1/2≥1（否則，rn將分配至b3泊位，矛盾），故

（2）rn分配至b3泊位，表明rn=1。根據(jù)前一個(gè)請(qǐng)求rn-1的大小分為如下兩種情形：

③rn-1=Δ，表 明Cn，1=Cn，2。如果Cmax（σ）=Cn，1，分析同上述①中Cmax（σ）=en的情形；反之，如果Cmax（σ）=Cn，3+1，則Cn，1＞Cn，3+1/2=Cmax（σ）-1/2（否則，rn將分配至b1泊位，矛盾）。在該情形下，若Cn，3=0，則Cmax（σ）=1，表明序列σ僅由1個(gè)小請(qǐng)求和1個(gè)大請(qǐng)求組成，從而C*（σ）=Cmax（σ）；否則，若Cn，3≥1，則Cmax（σ）≥2，從而可得

④rn-1=1。如果rn-1滿足策略C2.1情形而分配至b2泊位，則Cn，1=Cn，2。當(dāng)Cmax（σ）=Cn，1時(shí)，C*（σ）≥4Cmax（σ）/5；當(dāng)Cmax（σ）=Cn，3+1＜Cn，1+1/2時(shí)，結(jié)合Cn，3+1/2＜Cn，1與Cn，1＜Cn，3+1，可以推出，Cn，3≥1（否則，1/2＜Cn，1=Cn-1，1＜1，即0＜Cn-1，2= （Cn-1，1-1/2）＜1/2，不等式矛盾），從而

C*（σ）≥（4Cn，1+Cn，3+1）/5≥4Cmax（σ）/5

如果rn-1滿足策略C2.2情形而分配至b1泊位，則Cn，1=Cn，2+1/2。由情形（2）的條件知，Cmax（σ）=Cn，1＞Cn，3+1（否則，rn將分配至b2泊位，矛盾），從而

綜上所述，對(duì)于所有情形，均有Cmax（σ）/C*（σ）≤5/4成立。定理得證。 證畢

3 2≤Δ＜3的情形

3.1 在線策略設(shè)計(jì)

對(duì)于2 ≤Δ＜3 的情形，設(shè)計(jì)給出在線策略GR2（Greedy-2）。在該策略中，1個(gè)大請(qǐng)求ri（=Δ）的分配可能導(dǎo)致b1或b2泊位在服務(wù)該請(qǐng)求之前產(chǎn)生一個(gè)空閑時(shí)間段[t1，t2）= [t1，si），相應(yīng)的空閑泊位記為bT。若0＜t2-t1＜1/2，則該時(shí)段長(zhǎng)度不足以服務(wù)后續(xù)釋放的任一小請(qǐng)求，記這一不可利用時(shí)段為T(mén)w；若t2-t1=1/2，則該時(shí)段長(zhǎng)度足以服務(wù)后續(xù)釋放的1個(gè)小請(qǐng)求，將這一可利用時(shí)間段記為T(mén)a。初始化Ta=Tw= [0，0）。下面給出策略GR2的具體描述。

策略GR2若ri=rn，由于預(yù)知沒(méi)有后續(xù)請(qǐng)求，分配rn至某個(gè)泊位以使Cmax最小，若有多個(gè)泊位均導(dǎo)致相同的Cmax，則分配rn至下標(biāo)最小的泊位；否則，若i＜n，分兩種情形調(diào)度：

介紹一部研究天然氣產(chǎn)業(yè)的專著：《低碳經(jīng)濟(jì)下中國(guó)天然氣產(chǎn)業(yè)發(fā)展戰(zhàn)略》… ……………… 周 鵬（6．封三）

C1ri=Δ。若i=1且r2=1，或者i=2且r1=1，則令si=0，將ri分配至b2、b3泊位；否則，令si=max｛Ci，1，Ci，2｝，將ri分配至b1、b2泊位。若Ci，1-Ci，2=1/2，則令b T=b2且

若0＜|Ci，1-Ci，2|＜1/2，則令

C2ri=1。若T a= [t1，t2）≠[0，0），則令si=t1，將ri分 配 至b T泊 位 并 重 新 設(shè) 置T a= [0，0）；若ri+1=Δ且max｛Ci，1，Ci，2｝-Ci，3+Δ/4≥1，則分配ri至b3泊位且令si=Ci，3；否則，若上述兩種情形均不滿足，則不論ri+1=Δ或1，按如下兩種情形進(jìn)行調(diào)度：

C2.1ti，1=ti，3或ti，1＜ti，2=ti，3。令si=Ci，1，將ri分配至b1泊位；

C2.2ti，1=ti，2＜ti，3或ti，1＜ti，2＜ti，3。令si=ti，2，將ri分配至b2泊位。

給定任意請(qǐng)求輸入序列σ= ｛r1，r2，…，rn｝，根據(jù)C1情形，只有在r1=Δ且r2=1或r1=1且r2=Δ的兩種情形下，序列中的第1個(gè)大請(qǐng)求才被分配至右側(cè)2個(gè)泊位；否則，所有大請(qǐng)求均分配至左側(cè)2個(gè)泊位。同時(shí)，當(dāng)且僅當(dāng)分配第1個(gè)大請(qǐng)求至右側(cè)2個(gè)泊位時(shí)，才可能在分配第2個(gè)大請(qǐng)求時(shí)產(chǎn)生唯一的T w時(shí)間段，如圖1（a）、（b）中的陰影區(qū)域所示，其中，陰影的高度表示空閑時(shí)間的長(zhǎng)度。在圖1中，橫軸表示3個(gè)相鄰泊位，縱軸表示時(shí)間，每一個(gè)矩形表示一個(gè)船舶服務(wù)請(qǐng)求，矩形高度即為該請(qǐng)求實(shí)際服務(wù)的時(shí)長(zhǎng)。對(duì)于左側(cè)b1和b2這2個(gè)泊位，任意2個(gè)相鄰大請(qǐng)求之間若存在空閑時(shí)段，則根據(jù)C2.1情形，必定是后一個(gè)大請(qǐng)求釋放前在b1泊位分配了一個(gè)小請(qǐng)求，即該空閑泊位b T必定是b2，對(duì)應(yīng)空閑時(shí)段Ta的長(zhǎng)度等于1/2，如圖1（c）中的陰影區(qū)域所示。綜上所述，GR2策略所產(chǎn)生的加工序列中至多有1個(gè)T w時(shí)段。

圖1 兩類空閑時(shí)間段Ta 和T w 示意圖

3.2 策略GR2的競(jìng)爭(zhēng)分析

下面的定理給出了策略GR2在2≤Δ＜3情形下的競(jìng)爭(zhēng)比結(jié)論。

定理2對(duì)于問(wèn)題

當(dāng)2≤Δ＜3時(shí)，策略GR2具有競(jìng)爭(zhēng)比5/4。

證明給定任一請(qǐng)求輸入序列σ= ｛r1，r2，…，rn｝，令Cmax（σ）為 策 略GR2 的 最 大 完 工 時(shí) 間，C*（σ）為離線最優(yōu)方案對(duì)應(yīng)的目標(biāo)函數(shù)值。根據(jù)序列σ包含的大請(qǐng)求數(shù)量討論如下3種情形：

（1）序列σ中無(wú)大請(qǐng)求。根據(jù)C2.1和C2.2情形 可 知，r1，r2，…，rn-1均 分 配 至 左 邊2 個(gè) 泊 位 即Cn，3=0。若rn-1分配至b1泊位，則rn將分配至b2泊位，b1、b2泊位的完成時(shí)間相同，從而Cmax（σ）=Cn，1且C*（σ）≥4Cmax（σ）/5；若rn-1分配至b2泊位且rn

分配至b3泊位，則分析同上；若rn-1分配至b2泊位且rn分配至b1泊位，因?yàn)镃n，3=0，所以Cn，1=1/2（否則rn將分配至b3泊位）且σ中僅由3個(gè)小請(qǐng)求組成，此時(shí)，C*（σ）=Cmax（σ）=1。

（2）序列σ中有且僅有1個(gè)大請(qǐng)求。在該情形下，T w= [0，0）。

①r1=r2=1。不妨設(shè)rk=Δ（2＜k≤n），根據(jù)k的取值分為如下3個(gè)子情形：

（a）k=3＜n。則s3=C3，1=C3，2=1/2。由于Cn，1≥Cn，2≥e3≥1及Cn，3=0，rn必 定分配 至b3泊位。對(duì)Cn，1=Cn，2與Cn，1=Cn，2+1/2兩種情形，均可得C*（σ）≥4Cn，1/5=4Cmax（σ）/5。

（b）3＜k=n。由于min｛Cn-1，1，Cn-1，2｝≥1/2，Cn-1，3=0且Cn-1，1+Δ/4≥1，表明rn-1必定分配至b3泊位即Cn，3=1。如果rn分配至b1、b2泊位，不論分配后是否Ta≠[0，0），均有Cmax（σ）=Cn，1+Δ/4且C*（σ）≥4Cmax（σ）/5；如果rn分配至b2、b3泊位，則Cn，1=Cn，2+1/2，Cmax（σ）=Cn，2+Δ/3，且

（c）3 ＜k＜n。類似于（b）情形的分析，有Cn，3=1。若rn分配至b1泊位，則

若rn分配至b2泊位，則

若rn分配至b3泊位且Cmax（σ）=Cn，1，分析同上；若rn分配至b3泊位且Cmax（σ）=Cn，3+1=2，則

②r1、r2中有且僅有1個(gè)大請(qǐng)求。則該大請(qǐng)求必定分配至泊位b2、b3，根據(jù)C2.1和C2.2情形，rn之前的所有小請(qǐng)求均分配至b1或b2泊位，表明Cn，3=Δ/3。

（d）rn分配至b1或b2泊位。結(jié)合2/3≤Δ/3＜1與Cn，3=Δ/3可得，Cn，1≤3/2 且Cn，2≤Δ/3+1/2（否則，rn分配至b3泊位），從而序列σ由1個(gè)大請(qǐng)求和至多5個(gè)小請(qǐng)求組成即n≤6。對(duì)于2≤n≤6，均可驗(yàn)證Cmax（σ）/C*（σ）＜5/4。

（e）rn分配至b3泊位。結(jié)合（d）中情形的分析知，n＞6且有

由于|Cn，1-Cn，3|＜1/2，故

（3）σ中至少包含2個(gè)大請(qǐng)求。

①T w= [0，0）。若r1、r2中有且僅有1個(gè)大請(qǐng)求，由T w= [0，0）可推斷，σ中僅有2個(gè)大請(qǐng)求且rn=Δ分配至b2、b3泊位（否則，由C1情形知，第2個(gè)大請(qǐng)求將分配至b1、b2泊位，從而T w≠[0，0），矛盾）。Cmax（σ）=Cn，2+Δ/3，由于Cn，3=Δ/3，故

下面討論r1=r2=1的情形。在該情形中，序列σ中的所有大請(qǐng)求均分配至b1，b2泊位，除非rn=Δ。

（f）rn分配之后，Ta≠[0，0）。則在該Ta出現(xiàn)后的所有請(qǐng)求均為大請(qǐng)求；同時(shí)，根據(jù)C2情形可以判定Cn，3≥1（否則，若Cn，3=0，則Ta期間b1泊位上加工的小請(qǐng)求ri由于滿 足ri+1=Δ且max｛Ci，1，Ci，2｝-Ci，3+Δ/4≥1將被分配至b3泊位）。由于T a的空閑時(shí)長(zhǎng)等于1/2，在該時(shí)段內(nèi)2個(gè)空閑岸橋的總加工能力為2×（1/2）=1，故

（j）rn分配之后，Ta=[0，0）。若rn=Δ且分配至b1、b2泊位，則Cmax（σ）=Cn，1+Δ/4且C*（σ）≥4Cmax（σ）/5；若rn=Δ且 分 配 至b2、b3泊 位，則Cmax（σ）=Cn，2+Δ/3，結(jié)合1＞Δ/3與Cn，1-Cn，2=1/2，

若rn=1且rn分配至b1泊位，則

（否則，若Cn，3＜Cn，1-1/2，rn會(huì)被分配至b3泊位），

若rn=1 且分配后有Cmax（σ）=Cn，1，則C*（σ）≥4Cmax（σ）/5；若rn=1且分配至b3泊位后，有Cmax（σ）=Cn，3+1，則Cn，2＞Cn，3+1/2。類似于（c）情形的分析，有Cn，3＞1，從而

②T w≠[0，0）。此時(shí)，r1、r2中有且僅有1個(gè)大請(qǐng)求且被分配至b2、b3泊位。根據(jù)定義，T w只出現(xiàn)在b1或b2泊位。在T w之前，b1泊位只服務(wù)小請(qǐng)求且加工長(zhǎng)度均為1/2，而b2泊位所分配的請(qǐng)求除了第1個(gè)是大小為Δ/3的大請(qǐng)求，其他均為小請(qǐng)求。因此，若T w在b1或b2泊位，其長(zhǎng)度分別為Δ/3-1/2和1-Δ/3。結(jié)合2≤Δ＜3，max｛Δ/3-1/2，1-Δ/3｝≤Δ/6，表明在T w期間2個(gè)空閑岸橋的總加工能力至多為Δ/3。

（k）rn分配之后，Ta≠[0，0）。則在該T a出現(xiàn)后的所有請(qǐng)求均為大請(qǐng)求。類似于（f）情形的分析可知，Cn，3≥Δ/3+1，Cmax（σ）=Cn，1+Δ/4。由于T w與Ta時(shí)段內(nèi)2個(gè)空閑岸橋的總加工能力分別不超過(guò)Δ/3和1，故

（l）rn分配之后，Ta=[0，0）。已知Cn，3≥Δ/3且Tw期間2個(gè)空閑岸橋總加工能力至多Δ/3。若rn=Δ且分配至b1、b2泊位，則Cmax（σ）=Cn，1+Δ/4且

若rn=Δ且分配至b2、b3泊位，則Cmax（σ）=Cn，2+Δ/3，結(jié)合條件1＞Δ/3與Cn，1-Cn，2=1/2，

若rn=1且分配至b1泊位，則

從而

若rn=1且分配后有Cmax（σ）=Cn，1，則Cn，3≥Δ/3且

若rn=1且分配至b3泊位后有Cmax（σ）=Cn，3+1，則Cn，1=Cn，2＞Cn，3+1/2。當(dāng)Cn，3=Δ/3時(shí)，由于Cmax（σ）=Δ/3+1，且σ中包含至少2個(gè)大請(qǐng)求和2個(gè)小請(qǐng)求，結(jié)合C*（σ）≥min｛2Δ/3，1+Δ/4｝可得，Cmax（σ）/C*（σ）≤5/4；當(dāng)Cn，3≥Δ/3+1時(shí)，

綜上所述，對(duì)于任意序列σ，總有Cmax（σ）/C*（σ）＜5/4。定理得證。 證畢

結(jié)合定理1、2的結(jié)論，對(duì)于

模型可設(shè)計(jì)如下調(diào)度策略：對(duì)于Δ≥3的情形采用GR1策略，對(duì)于2≤Δ＜3的情形采用GR2策略。由定理1、2可知，該調(diào)度策略對(duì)于上述模型具有競(jìng)爭(zhēng)比5/4。

4 競(jìng)爭(zhēng)比下界分析

下面給出泊位與岸橋聯(lián)合調(diào)度模型的競(jìng)爭(zhēng)比下界，以及無(wú)預(yù)知能力時(shí)相應(yīng)的競(jìng)爭(zhēng)比下界。

定理3問(wèn)題

的競(jìng)爭(zhēng)比下界為5/4。

證明要證明該定理，只需設(shè)計(jì)一個(gè)請(qǐng)求輸入序列σ，使得對(duì)于任一在線策略A滿足不等式Cmax（σ）/C*（σ）≥5/4，其中，Cmax（σ）和C*（σ）分別為策略A所產(chǎn)生服務(wù)序列的最大完工時(shí)間、離線最優(yōu)方案下的目標(biāo)函數(shù)值。序列σ包含至多3個(gè)請(qǐng)求且r1=r2=1。策略A在分配r1時(shí)預(yù)知r2=1。若A分配1個(gè)岸橋服務(wù)r1，則e1=1，σ=｛r1，r2｝，從而Cmax（σ）≥1。最優(yōu)方案將各分配2個(gè)岸橋分別服務(wù)2個(gè)請(qǐng)求，C*（σ）=1/2且Cmax（σ）/C*（σ）≥2；反之，若A分配2個(gè)岸橋服務(wù)r1，則r3=Δ且σ=｛r1，r2，r3｝。因?yàn)閞3需占用2個(gè)相鄰泊位，所以Cmax（σ）≥min｛Δ/3，1/2+Δ/4｝。最優(yōu)方案將分配1個(gè)岸橋服務(wù)前2 個(gè)請(qǐng)求，分配4 個(gè)岸橋服務(wù)r3，C*（σ）=max｛Δ/4，2｝。令Δ=8，從而Cmax（σ）/C*（σ）≥5/4。定理得證。 證畢

定理4問(wèn)題的競(jìng)爭(zhēng)比下界為4/3。

證明相同于定理3的證明思路，只要設(shè)計(jì)一個(gè)請(qǐng)求輸入序列σ，使得對(duì)于任一在線策略A滿足不等式Cmax（σ）/C*（σ）≥4/3即可。序列σ包含至多2個(gè)請(qǐng)求且r1=1。若A對(duì)r1只分配1個(gè)岸橋，則σ= ｛r1｝；Cmax（σ）≥1 而C*（σ）=1/2，從 而Cmax（σ）/C*（σ）≥2；反之，若A分配2個(gè)岸橋服務(wù)r1，則r2=Δ且σ=｛r1，r2｝。由于只有5個(gè)岸橋，策略A要么分配3個(gè)岸橋服務(wù)r2，要么對(duì)r2分配4個(gè)岸 橋 且 最 早 從1/2 時(shí) 刻 啟 動(dòng) 服 務(wù)，Cmax（σ）≥min｛Δ/3，1/2+Δ/4｝。最優(yōu)方案則分別分配1個(gè)和4個(gè) 岸橋來(lái)服務(wù)請(qǐng)求r1和r2，C*（σ）= max｛Δ/4，1｝。令Δ=6，從而Cmax（σ）/C*（σ）≥4/3。定理得證。 證畢

結(jié)合定理1～4可知，即使賦予十分有限的預(yù)知能力，即只能預(yù)知后續(xù)一個(gè)請(qǐng)求，在線策略的最壞情形理論競(jìng)爭(zhēng)性能也是能夠得以改進(jìn)的。

5 數(shù)值分析

針對(duì)前面所討論的Δ≥3和2≤Δ＜3兩種情形，下面通過(guò)數(shù)值計(jì)算進(jìn)一步驗(yàn)證策略GR1 和GR2的平均執(zhí)行性能。主要考察不同的序列長(zhǎng)度，以及大請(qǐng)求的不同任務(wù)量對(duì)相應(yīng)策略的平均性能有何影響，同時(shí)，對(duì)比分析理論證明結(jié)果與模擬分析數(shù)值結(jié)論的差異。這里，對(duì)每一種參數(shù)設(shè)置情形，利用計(jì)算機(jī)分別隨機(jī)產(chǎn)生10 組請(qǐng)求序列，并計(jì)算GR1（或GR2）策略的解與最優(yōu)解對(duì)應(yīng)目標(biāo)函數(shù)值在10組序列中的平均比值，借以判斷在線策略的平均執(zhí)行效果。具體的數(shù)值計(jì)算設(shè)置和分析如下：

首先，對(duì)于Δ≥3 的情形考察在線策略GR1。給定大請(qǐng)求的任務(wù)量Δ=5，設(shè)置序列長(zhǎng)度n分別等于50、100、150、200、250、300、350、400、450和500；針對(duì)上述每一種序列長(zhǎng)度分別隨機(jī)產(chǎn)生10組序列，并計(jì)算GR1策略所給出的目標(biāo)值與最優(yōu)值的平均比值，得到表1所示的結(jié)果。

將表1的數(shù)據(jù)在圖2中用折線圖進(jìn)行表示。由圖2可以看出，對(duì)于不同的序列長(zhǎng)度，策略GR1所得到的平均競(jìng)爭(zhēng)比取值在[1.048 7，1.098 4]區(qū)間內(nèi)小幅波動(dòng)，并無(wú)明顯的增減規(guī)律，表明序列長(zhǎng)度對(duì)于策略的平均執(zhí)行性能基本上沒(méi)有影響；其次，所有的值均明顯小于理論競(jìng)爭(zhēng)比1.25，說(shuō)明策略的實(shí)際執(zhí)行效果明顯優(yōu)于理論結(jié)果。

表1 Δ=5時(shí)不同序列長(zhǎng)度下的平均競(jìng)爭(zhēng)比數(shù)值

圖2 策略GR1平均競(jìng)爭(zhēng)比值隨輸入序列長(zhǎng)度的變化趨勢(shì)圖

下面考察大請(qǐng)求任務(wù)量Δ的不同取值對(duì)策略GR1平均競(jìng)爭(zhēng)比值的影響。分別取Δ=3、6、9、12、15、18、21、24、27 和30，并設(shè)定序列長(zhǎng)度n=100（對(duì)于其他序列長(zhǎng)度，結(jié)論相似）。對(duì)每一個(gè)Δ取值分別隨機(jī)產(chǎn)生10組序列并計(jì)算平均競(jìng)爭(zhēng)比值，得到表2所示的結(jié)果。將表2 的數(shù)據(jù)用折線圖進(jìn)行表示，如圖3所示。

表2 序列長(zhǎng)度n=100時(shí)不同Δ 取值下的平均競(jìng)爭(zhēng)比數(shù)值

圖3 策略GR1平均競(jìng)爭(zhēng)比值隨大請(qǐng)求任務(wù)量的變化趨勢(shì)圖

根據(jù)表2和圖3，策略GR1的目標(biāo)函數(shù)值與最優(yōu)值的平均比值在[1.048 7，1.085 5]區(qū)間內(nèi)小幅波動(dòng)，且無(wú)明顯的增減規(guī)律，表明大請(qǐng)求的大小對(duì)于策略的平均執(zhí)行性能基本上沒(méi)有影響；其次，所有的數(shù)值均明顯小于理論結(jié)果1.25，表明該策略對(duì)于大請(qǐng)求的各種大小均具有良好的平均執(zhí)行性能。

其次，對(duì)于2≤Δ＜3的情形下在線策略GR2的考察思路同前，其分析結(jié)論基本相同于策略GR1的結(jié)果。設(shè)定大請(qǐng)求任務(wù)量Δ=2.4，針對(duì)前一情形的10種序列長(zhǎng)度類似地計(jì)算GR2策略的平均競(jìng)爭(zhēng)比值，結(jié)果如圖4所示。策略GR2的目標(biāo)函數(shù)值與最優(yōu)值的平均比值在[1.051 2，1.058 1]微小區(qū)間內(nèi)波動(dòng)，波動(dòng)區(qū)間整體小于策略GR1在Δ=5時(shí)的情形，表明策略GR2對(duì)于較小的Δ值在平均性能上略優(yōu)于在Δ取值較大時(shí)所采用的GR1策略。

進(jìn)一步，設(shè)定序列長(zhǎng)度n=100，針對(duì)10種不同的Δ取值，即Δ=2.0、2.1、2.2、2.3、2.4、2.5、2.6、2.7、2.8和2.9，分別計(jì)算策略GR2的平均競(jìng)爭(zhēng)比值，如圖5所示。

圖4 策略GR2平均競(jìng)爭(zhēng)比值隨輸入序列長(zhǎng)度的變化趨勢(shì)圖

圖5 策略GR2平均競(jìng)爭(zhēng)比值隨大請(qǐng)求任務(wù)量的變化趨勢(shì)圖

在圖5中，策略GR2的平均競(jìng)爭(zhēng)比值的波動(dòng)區(qū)間為[1.052 3，1.058 3]，這個(gè)波動(dòng)區(qū)間同樣略優(yōu)于策略GR1對(duì)于不同Δ取值下的平均性能，其結(jié)論相同于前面對(duì)不同序列長(zhǎng)度下的兩種策略優(yōu)劣的討論；同時(shí)，策略GR2的平均競(jìng)爭(zhēng)比值要明顯優(yōu)于理論競(jìng)爭(zhēng)比5/4。

基于上述分析，策略GR1和GR2對(duì)于給定的某個(gè)大請(qǐng)求任務(wù)量取值，其平均執(zhí)行性能均控制在最優(yōu)值的1.1倍以內(nèi)。這表明，2個(gè)在線策略具有良好的平均執(zhí)行性能，其策略構(gòu)建思路對(duì)于碼頭實(shí)踐中的調(diào)度優(yōu)化方案設(shè)計(jì)具有一定的指導(dǎo)作用。

6 結(jié)語(yǔ)

針對(duì)集裝箱碼頭加班船作業(yè)的實(shí)時(shí)服務(wù)特征，運(yùn)用在線理論構(gòu)建了有限預(yù)知信息下的泊位與岸橋聯(lián)合調(diào)度在線模型，探討了一個(gè)混合型泊位布局，配置5個(gè)岸橋且僅有兩種大小船請(qǐng)求的情形。對(duì)于預(yù)知未來(lái)一個(gè)請(qǐng)求的能力，設(shè)計(jì)出了具有最優(yōu)競(jìng)爭(zhēng)比5/4的在線調(diào)度策略；同時(shí)，分析指出，無(wú)預(yù)知能力下的在線策略競(jìng)爭(zhēng)比不小于4/3，表明即使十分有限的預(yù)知能力也可以有效地改進(jìn)在線調(diào)度策略的競(jìng)爭(zhēng)性能。在后續(xù)研究中，將進(jìn)一步探討具有多個(gè)并行操作的混合型泊位，或者船舶任務(wù)量在一定范圍內(nèi)任意取值的更一般情形，探析新的模型性質(zhì)并設(shè)計(jì)具有良好競(jìng)爭(zhēng)性的在線策略。