有限預知信息下集裝箱碼頭泊位與岸橋聯合在線調度

鄭斐峰，喬龍亮，黃基誕

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

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

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

現有的研究大都假設船舶需求信息事先全部已知，然而，通過上海洋山港的實地調研發現，因為加班船的大量存在，即使是上海洋山港大型深水碼頭，其船期表也是每天動態調整并安排許多泊位用于服務新抵港的加班船；在其排期密度表中，加班船的服務數量比例甚至達到1/3。加班船不同于主干船的服務特點，后者提前至少一個工作日就確定準確抵港時間，并在碼頭制定服務計劃之前提早一天抵港并在錨地等待；加班船的服務具有明顯的動態實時特征，這源于碼頭事先并不制定每艘加班船的具體服務時間計劃，只是提供一定的泊位和岸橋資源供所有加班船使用的做法。因此，對每一艘加班船的服務安排，碼頭泊位與岸橋資源的調度顯現出了很強的實時性。

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

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

1 問題描述與基本定義

1.1 問題描述及模型假設

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

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

（2）系統中只有兩種請求，小請求、大請求的任務量分別為1和Δ（≥2），分別記ri=1和ri=Δ。

（3）左、中、右這3個離散泊位記為b1、b2、b3，從左至右的岸橋標為q1、q2、q3、q4、q5。在任一時刻，每個泊位及岸橋只能服務1個請求。小請求占用1個泊位且至多由2個相鄰岸橋進行服務，大請求占用2個相鄰泊位且至多由4個相鄰岸橋進行服務。

（4）若請求ri由m i≥1個岸橋進行服務，則其服務時長等于ri/mi[8]。

（5）當請求ri（1≤i≤n-1）釋放時可以預知下一個請求ri+1的信息；rn釋放時可得知序列長度n的值。

模型的優化目標是最小化最后一艘船舶的完工時間。運用四參數描述法[3]，將本文所構建的上述模型標記為

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

1.2 競爭比定義及參數符號說明

一般運用競爭分析方法來求解在線問題，即假定存在一個事先掌握所有請求信息的離線敵手，通過控制請求的輸入序列，使得在線策略執行性能盡可能的差。通常采用競爭比這一指標來度量在線策略的性能[14]。對于某一在線策略A，定義ΩA為其所有可能的請求輸入序列的集合；給定任一序列σ∈ΩA，令Cmax（σ）為策略A服務完成序列σ的最大完工時間，C*（σ）為信息完全的情形下最優方案對應的目標函數值。將策略A的競爭比定義為

稱A具有競爭比ρ或稱A是ρ-競爭的。用競爭比下界表示所有在線策略對于該問題可能達到的最小競爭比。如果某一個在線策略的競爭比達到了競爭比下界值，則稱其為最優在線策略。

下面列出模型討論中主要運用的變量符號：

Cmax（σ）——在線策略的目標函數值

C*（σ）——離線策略的目標函數值

ti，1——ri釋放時至少一個泊位完成此前分配至該泊位的所有請求的最早完工時間

ti，2，ti，3——ri釋放時2、3個連續泊位完成此前分配至各自泊位所有請求的最早完工時間

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

si，ei—— 請求ri的服務開始時間和結束時間

T a= [t1，t2）—— 在線策略分配大請求ri導致某一泊位服務該請求前出現可利用空閑時間段T a，滿足t2=si=t1+1/2；初始化T a= [0，0）

對于

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

2 Δ≥3的情形

2.1 在線策略設計

基于前面對岸橋與泊位兩種資源的固定配置方案，在線策略只需決策分配請求至哪幾個泊位以及相應的服務啟動時間。下面給出在線策略GR1（Greedy-1）的具體描述。

策略GR1若ri=rn，由于預知沒有后續請求，故分配該請求至某一泊位以最小化Cmax。若有多個泊位均可導致相同目標函數值，則分配給下標最小的泊位；否則，若1≤i＜n，由于預知后續請求ri+1，分如下兩種情形進行決策。

C1ri=Δ。對于ri+1=1 或Δ，令啟動時間si=ti，2，將ri分配至左邊2個泊位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泊位。

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

2.2 策略GR1的競爭分析

下面的定理給出策略GR1在Δ≥3情形下的競爭性能。

定理1對于問題

當Δ≥3時，策略GR1具有競爭比5/4。

證明給定任一請求輸入序列σ= ｛r1，r2，…，rn｝，令Cmax（σ）為策略GR1的最大完工時間，C*（σ）為離線最優方案對應的目標函數值。根據GR1策略描述，所有大請求均被分配至左邊2個泊位b1、b2，而且在完成最后一個大請求之前，左邊2個泊位與4個岸橋一直處于服務狀態。下面根據最后一個請求rn的分配結果討論兩種情形：

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

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

（2）rn分配至b3泊位，表明rn=1。根據前一個請求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個小請求和1個大請求組成，從而C*（σ）=Cmax（σ）；否則，若Cn，3≥1，則Cmax（σ）≥2，從而可得

④rn-1=1。如果rn-1滿足策略C2.1情形而分配至b2泊位，則Cn，1=Cn，2。當Cmax（σ）=Cn，1時，C*（σ）≥4Cmax（σ）/5；當Cmax（σ）=Cn，3+1＜Cn，1+1/2時，結合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泊位，矛盾），從而

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

3 2≤Δ＜3的情形

3.1 在線策略設計

對于2 ≤Δ＜3 的情形，設計給出在線策略GR2（Greedy-2）。在該策略中，1個大請求ri（=Δ）的分配可能導致b1或b2泊位在服務該請求之前產生一個空閑時間段[t1，t2）= [t1，si），相應的空閑泊位記為bT。若0＜t2-t1＜1/2，則該時段長度不足以服務后續釋放的任一小請求，記這一不可利用時段為Tw；若t2-t1=1/2，則該時段長度足以服務后續釋放的1個小請求，將這一可利用時間段記為Ta。初始化Ta=Tw= [0，0）。下面給出策略GR2的具體描述。

策略GR2若ri=rn，由于預知沒有后續請求，分配rn至某個泊位以使Cmax最小，若有多個泊位均導致相同的Cmax，則分配rn至下標最小的泊位；否則，若i＜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泊 位 并 重 新 設 置T a= [0，0）；若ri+1=Δ且max｛Ci，1，Ci，2｝-Ci，3+Δ/4≥1，則分配ri至b3泊位且令si=Ci，3；否則，若上述兩種情形均不滿足，則不論ri+1=Δ或1，按如下兩種情形進行調度：

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泊位。

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

圖1 兩類空閑時間段Ta 和T w 示意圖

3.2 策略GR2的競爭分析

下面的定理給出了策略GR2在2≤Δ＜3情形下的競爭比結論。

定理2對于問題

當2≤Δ＜3時，策略GR2具有競爭比5/4。

證明給定任一請求輸入序列σ= ｛r1，r2，…，rn｝，令Cmax（σ）為 策 略GR2 的 最 大 完 工 時 間，C*（σ）為離線最優方案對應的目標函數值。根據序列σ包含的大請求數量討論如下3種情形：

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

分配至b3泊位，則分析同上；若rn-1分配至b2泊位且rn分配至b1泊位，因為Cn，3=0，所以Cn，1=1/2（否則rn將分配至b3泊位）且σ中僅由3個小請求組成，此時，C*（σ）=Cmax（σ）=1。

（2）序列σ中有且僅有1個大請求。在該情形下，T w= [0，0）。

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

（a）k=3＜n。則s3=C3，1=C3，2=1/2。由于Cn，1≥Cn，2≥e3≥1及Cn，3=0，rn必 定分配 至b3泊位。對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個大請求。則該大請求必定分配至泊位b2、b3，根據C2.1和C2.2情形，rn之前的所有小請求均分配至b1或b2泊位，表明Cn，3=Δ/3。

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

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

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

（3）σ中至少包含2個大請求。

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

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

（f）rn分配之后，Ta≠[0，0）。則在該Ta出現后的所有請求均為大請求；同時，根據C2情形可以判定Cn，3≥1（否則，若Cn，3=0，則Ta期間b1泊位上加工的小請求ri由于滿 足ri+1=Δ且max｛Ci，1，Ci，2｝-Ci，3+Δ/4≥1將被分配至b3泊位）。由于T a的空閑時長等于1/2，在該時段內2個空閑岸橋的總加工能力為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，結合1＞Δ/3與Cn，1-Cn，2=1/2，

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

（否則，若Cn，3＜Cn，1-1/2，rn會被分配至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）。此時，r1、r2中有且僅有1個大請求且被分配至b2、b3泊位。根據定義，T w只出現在b1或b2泊位。在T w之前，b1泊位只服務小請求且加工長度均為1/2，而b2泊位所分配的請求除了第1個是大小為Δ/3的大請求，其他均為小請求。因此，若T w在b1或b2泊位，其長度分別為Δ/3-1/2和1-Δ/3。結合2≤Δ＜3，max｛Δ/3-1/2，1-Δ/3｝≤Δ/6，表明在T w期間2個空閑岸橋的總加工能力至多為Δ/3。

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

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

若rn=Δ且分配至b2、b3泊位，則Cmax（σ）=Cn，2+Δ/3，結合條件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。當Cn，3=Δ/3時，由于Cmax（σ）=Δ/3+1，且σ中包含至少2個大請求和2個小請求，結合C*（σ）≥min｛2Δ/3，1+Δ/4｝可得，Cmax（σ）/C*（σ）≤5/4；當Cn，3≥Δ/3+1時，

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

結合定理1、2的結論，對于

模型可設計如下調度策略：對于Δ≥3的情形采用GR1策略，對于2≤Δ＜3的情形采用GR2策略。由定理1、2可知，該調度策略對于上述模型具有競爭比5/4。

4 競爭比下界分析

下面給出泊位與岸橋聯合調度模型的競爭比下界，以及無預知能力時相應的競爭比下界。

定理3問題

的競爭比下界為5/4。

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

定理4問題的競爭比下界為4/3。

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

結合定理1～4可知，即使賦予十分有限的預知能力，即只能預知后續一個請求，在線策略的最壞情形理論競爭性能也是能夠得以改進的。

5 數值分析

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

首先，對于Δ≥3 的情形考察在線策略GR1。給定大請求的任務量Δ=5，設置序列長度n分別等于50、100、150、200、250、300、350、400、450和500；針對上述每一種序列長度分別隨機產生10組序列，并計算GR1策略所給出的目標值與最優值的平均比值，得到表1所示的結果。

將表1的數據在圖2中用折線圖進行表示。由圖2可以看出，對于不同的序列長度，策略GR1所得到的平均競爭比取值在[1.048 7，1.098 4]區間內小幅波動，并無明顯的增減規律，表明序列長度對于策略的平均執行性能基本上沒有影響；其次，所有的值均明顯小于理論競爭比1.25，說明策略的實際執行效果明顯優于理論結果。

表1 Δ=5時不同序列長度下的平均競爭比數值

圖2 策略GR1平均競爭比值隨輸入序列長度的變化趨勢圖

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

表2 序列長度n=100時不同Δ 取值下的平均競爭比數值

圖3 策略GR1平均競爭比值隨大請求任務量的變化趨勢圖

根據表2和圖3，策略GR1的目標函數值與最優值的平均比值在[1.048 7，1.085 5]區間內小幅波動，且無明顯的增減規律，表明大請求的大小對于策略的平均執行性能基本上沒有影響；其次，所有的數值均明顯小于理論結果1.25，表明該策略對于大請求的各種大小均具有良好的平均執行性能。

其次，對于2≤Δ＜3的情形下在線策略GR2的考察思路同前，其分析結論基本相同于策略GR1的結果。設定大請求任務量Δ=2.4，針對前一情形的10種序列長度類似地計算GR2策略的平均競爭比值，結果如圖4所示。策略GR2的目標函數值與最優值的平均比值在[1.051 2，1.058 1]微小區間內波動，波動區間整體小于策略GR1在Δ=5時的情形，表明策略GR2對于較小的Δ值在平均性能上略優于在Δ取值較大時所采用的GR1策略。

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

圖4 策略GR2平均競爭比值隨輸入序列長度的變化趨勢圖

圖5 策略GR2平均競爭比值隨大請求任務量的變化趨勢圖

在圖5中，策略GR2的平均競爭比值的波動區間為[1.052 3，1.058 3]，這個波動區間同樣略優于策略GR1對于不同Δ取值下的平均性能，其結論相同于前面對不同序列長度下的兩種策略優劣的討論；同時，策略GR2的平均競爭比值要明顯優于理論競爭比5/4。

基于上述分析，策略GR1和GR2對于給定的某個大請求任務量取值，其平均執行性能均控制在最優值的1.1倍以內。這表明，2個在線策略具有良好的平均執行性能，其策略構建思路對于碼頭實踐中的調度優化方案設計具有一定的指導作用。

6 結語

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