基于排隊論的修船碼頭移泊調度系統

唐偉煒，楊坤榮，艾志興(.華南理工大學 土木與交通學院，廣東 廣州 5064;.中船澄西船舶(廣州)有限公司，廣東 廣州 546;.中船黃埔文沖船舶有限公司，廣東 廣州 5075)

基于排隊論的修船碼頭移泊調度系統

唐偉煒1，楊坤榮2，艾志興3
(1.華南理工大學 土木與交通學院，廣東 廣州 510641;2.中船澄西船舶(廣州)有限公司，廣東 廣州 511462;3.中船黃埔文沖船舶有限公司，廣東 廣州 510715)

修船碼頭移泊調度是修船廠作業的重要組成部分，文章基于排隊論對修船碼頭移泊調度系統進行分析，闡述了該系統的排隊流程，并建立了修船碼頭移泊調度排隊模型，研究了碼頭泊位調度系統的運行效率，確定系統參數的最優值，以決定系統的結構是否合理，設計改進的措施等。

修船碼頭；排隊論；系統分析；容量有限排隊模型

排隊論是20世紀初由丹麥數學家Erlang研究并發展起來的一門學科，也稱隨機服務系統理論。通常是建立一些數學模型，對系統狀態可能發生改變的事件進行描述，并對系統的狀態進行預測。發生系統狀態改變的事件通常有2個，一是顧客到達，二是系統提供服務[1]。現實生活中排隊的現象有很多，如到餐廳用餐、輪船進港、病人就診、商店購物等。排隊論主要通過對隊長、等待時間以及忙期分布的研究，判斷一個已知的系統中用什么樣的模型，然后利用排隊理論對系統進行分析，最后解決系統的最優設計和最優運行問題。

1 修船碼頭移泊排隊系統的構成

1.1修船碼頭具有排隊系統的典型特征

1)有請求服務的人或物——請求進廠的船舶，我們將此稱為“顧客”。

2)有為顧客提供服務的人或物——修船碼頭，我們稱此為“服務員”，修船碼頭所提供的服務即為為請求進廠的船舶安排泊位停靠,而每條船都盡量停在它的最佳工作泊位，最佳工作泊位能保障船舶按期完成作業，我們稱最佳工作泊位為服務臺，這些泊位往往是重合的，基本上是靠近碼頭岸線的檔位，由船舶和碼頭組成服務系統。

3)船舶隨機地一艘艘或一批批要求進廠，每艘船只有停泊在最佳工作泊位才能開始作業，而每艘船作業的時間不一定是確定的，服務過程的這種隨機性不僅會造成某個階段船舶排長隊等待最佳工作泊位，而某些階段碼頭又有很多空閑泊位，造成泊位利用率低下。

1.2組成部分

將碼頭移泊調度看作一個排隊系統，它由以下3部分組成。

1)輸入過程，在修船碼頭移泊調度系統中，輸入過程指即船舶來到碼頭的概率分布。系統首先要根據船期表，由船舶到達的規律作出經驗分布，然后根據統計方法確定理論分布，并估計它的參數值。 如在某一周期內，船舶進廠服從泊松分布，且船舶的到達是相互獨立的、平穩的輸入過程。

2)排隊規則，即顧客排隊和等待的規則。排隊規則一般有即時制和等待制2種。在修船碼頭移泊調度系統中，船舶遵循的是混合制規則，即最佳工作泊位被占用時，船舶排隊等候泊位安排，但又不允許隊列無限長，排隊的船舶一般遵循先到先服務的次序規則，但當有緊急任務時則遵循有優先權服務的次序規則。

3)服務機構，修船碼頭有多個泊位，但每個泊位只能停泊一艘船舶。和輸入過程一樣，多數的船舶作業時間都是隨機的，如果我們假定船舶作業時間的分布是平穩的，那么若以Tn表示第n艘船作業所需的時間，則船舶作業時間所構成的序列{Tn}，n=1，2，…所服從的概率分布表達了移泊系統的服務機制，一般假定船舶的作業時間T1，T2，…是獨立分布的，并且任意2艘船舶到來的時間間隔集合{Tn}也是獨立的。

1.3系統參數

研究修船碼頭移泊調度排隊問題的目的，是研究該系統的運行效率，確定系統參數的最優值，以決定該移泊系統的結構是否合理。

衡量碼頭運行效率的指標通常有系統服務能力，系統狀態概率，船舶隊長，船舶等待隊長，船舶逗留時間，船舶等待時間等[2]。除此之外，需考慮的指標還有系統的忙期以及輸出過程。系統的忙期是指從船舶到達較為空閑的碼頭時起，到碼頭再次恢復空閑的這一段時間長度，即修船碼頭連續工作的時間長度(這里的空閑指碼頭沒有進行泊位安排的工作)。它與碼頭連續工作的時間長度以及碼頭的工作強度有關。忙期的長度和一個忙期中平均完成泊位停靠的船舶艘數，這些都是衡量碼頭泊位調度系統服務效率的指標。而輸出過程則是船舶離開碼頭的過程，主要指標有船舶離開碼頭的時間間隔以及一定周期內離開碼頭的船舶艘數。

修船碼頭的泊位調度排隊系統如圖1所示。

圖1 修船碼頭排隊系統框圖

排隊系統還存在以下重要參數。

1)隊長：指碼頭移泊調度系統中的船舶艘數，它的期望值記為Ls；排隊長，指在系統中排隊等待作業的船舶艘數，其期望值記為Lq。

系統中的船舶艘數 = 等待服務的船舶艘數 + 正被服務的船舶艘數。

由此可判斷出，Lq(或Ls)越大，服務的效率則越低。

2)逗留時間：指某一艘船在碼頭的停留時間，即船舶從進廠到泊位安排完畢的時間。其期望值記Ws。等待時間，指某一艘船舶在開始作業之前等待的時間，其期望值記為Wq。

船舶逗留時間 = 船舶等待時間 +船舶被服務時間。

計算這些參數必須知道泊位調度系統狀態的概率，即在t時刻碼頭的船舶艘數。如果在t時刻碼頭有n艘船，就說系統的狀態是n，其概率一般用Pn(t)表示。

2 修船碼頭泊位調度系統的排隊模型

對于修船移泊系統來說，輸入過程為船舶獨立到達且間隔時間服從一般概率分布，系統有多個泊位，即多個服務臺，船舶所需的服務時間服從一般概率分布且是相互獨立的。當系統處在旺季時，進廠船舶較多，相對最佳工作泊位來講我們可以認定顧客源為無限，此時船舶需要排隊等待最佳工作泊位，因工作周期有限，等待時間越久，后續工作時間越緊張，越不容易在計劃周期內完成任務，船東和企業都要接受損失。又因碼頭不能無限制的使用泊位停船，容量有限而要求進廠船舶超出系統最大容量時，后來的船舶將被拒絕進入系統，系統將有損失率。如何使兩者之間達到一個平衡，如何確定系統參數的最優值，是此模型將要研究的問題；另一種情況是系統處在淡季時，一個時期內進廠船舶有限，當進廠船舶艘數小于最佳工作泊位艘數時，船舶無需排隊等待可直接進入系統開始作業。

為更清晰的表達修船碼頭泊位調度系統的排隊模型，一律設系統的輸入過程服從泊松分布，即在t時刻,到達n艘船舶的概率為:

(1)

式中：λ為船舶平均到達率,即單位時間內(通常為24 h內)平均到達碼頭的船舶艘數。

設船舶作業時間服從參數為μ的負指數分布。因系統處于淡季時，船舶艘數小于最佳工作泊位數量，無需排隊等待可直接作業，基本能在計劃周期內完成任務，因此在此研究系統處于旺季時的狀態，系統排隊模型表達形式為M/M/C/N/∞[3]。

M/M/C/N/∞模型是指最佳工作泊位有限，但計劃進廠船舶為無限，船舶到達相互獨立， 到達過程是平穩的，進廠船舶流為泊松流，平均到達率為λ(單位時間到達船舶艘數)，到達數量為n，多服務臺、先到先服務。假設碼頭有C個泊位為最佳工作泊位，系統的最大容量為N(N≥C)，各泊位的船舶靠泊時間滿足負指數分布，且各泊位停泊作業是相互獨立的(不搞協作)，船舶服務率為μ(單位時間服務船舶艘數)，當系統客滿(即有N艘船計劃進廠)時，有C個接受服務，總服務率：當 0lt;nlt;C時為nμ；當n≥C時為Cμ， 系統的服務強度為ρ=λ/Cμ，最佳工作泊位一般為最靠近碼頭岸線的2個檔位，其艘數與船舶長度有關，即

(2)

式中：L為碼頭岸線長度；li為船舶i的長度；S為船舶集合。

可以得到系統的狀態概率平衡方程并由遞推關系可得系統狀態概率：

k=0,1,2,…,C-1,

(3)

(4)

系統的運行指標：

Ls=Lq+Cρ(1-PN),

(5)

(6)

(7)

Ws=Wq+1/μ,

(8)

式中：P0為初始時刻系統狀態概率；Pn為到達n艘船舶時系統狀態概率；PN為到達船舶艘數達到系統極限時系統的狀態概率；Ls為隊長，即所有系統中船舶艘數；Lq為系統中排隊的船舶數量；Ws為船舶在系統中的逗留時間；Wq為船舶等待時間。

3 算例

某碼頭的最佳工作泊位為10，系統容量為30。在某一時期，船舶的到來服從泊松分布，且λ=2(平均每天到達2艘船)，船舶進入碼頭作業時間服從指數分布，且μ=0.1(平均每天服務0.1艘船)，則ρ=2。

由式(3)可知系統的狀態概率P0=1.69×10-13，即整個碼頭空閑的概率為1.69×10-13。

當n=5時，0≤n≤C，Pn=4.5×10-9；

當n=10時，0≤n≤C，Pn=4.8×10-7；

當n=20時，C≤n≤N，Pn=4.9×10-4；

當n=30時，C≤n≤N，Pn=PN=0.5。

當n=35時，對于M/M/C/N/∞模型，如果碼頭已有N艘船舶，則后來的船舶將被拒絕，于是可設PN為被拒絕的概率，1-PN即為接受船舶進廠的概率。λ(1-PN)表示一定周期內實際進入碼頭的船舶艘數，在穩定狀態下，即為一定周期內實際完成靠泊的船舶艘數。系統滿員的損失率：

(9)

若想船舶等待時間越小，在最佳工作泊位艘數，系統容量，λ和μ一定的情況下，則排隊船舶艘數要越少，但是進廠船舶艘數減少直接影響船廠的效益，因此要考慮當船舶總數為多少時才能使系統達到最優的效果。

由式(5)、式(6)可知，系統船舶排隊的艘數Lq=19，Ls=29，即，當系統中船舶總數為29，排隊船舶艘數為19時，系統的狀態能達到最優。此時Pn=0.25，Wq=19，Ws=29。

即船舶平均排隊時間為19天，船舶平均逗留時間為29天。

4 結束語

本文在排隊理論的基礎上對修船碼頭移泊調度系統進行了分析，將移泊系統分成輸入過程，服務過程，輸出過程等。并通過一些指標來衡量碼頭系統的工作效率，來判斷系統結構是否合理。最后針對系統的M/M/C/N/∞模型進行模擬仿真計算，得出了使系統狀態效率最佳的參數數值。

[1] 王庚，王敏生. 現代數學建模方法[M]. 北京：科學出版社，2010.

[2] 唐應輝，唐小我. 排隊論一基礎與分析技術[M]. 北京：科學出版社，2006.

[3] 孫榮恒,李建平.排隊論基礎[M].北京：科學出版社，2002.

Ship berth scheduling is an important part of shipyard.This article studies on the berth scheduling problem based on the queuing theory,expounds the queuing process of the system and the berth scheduling system queue model is established.Running efficiency of the berth scheduling system is studied and the optimal value of system parameters is determined,which may decide whether the system structure is reasonable and design the improvement measures.

ship-repairing dock;queuing theory;system analysis;M/M/C/N/∞ model

U673

10.13352/j.issn.1001-8328.2015.05.014

唐偉煒(1983-)，女，天津人，在讀博士研究生，研究方向為船舶與海洋結構物設計制造。

2015-06-01