基于排隊論的修船碼頭移泊調度系統(tǒng)

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

基于排隊論的修船碼頭移泊調度系統(tǒng)

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

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

修船碼頭；排隊論；系統(tǒng)分析；容量有限排隊模型

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

1 修船碼頭移泊排隊系統(tǒng)的構成

1.1修船碼頭具有排隊系統(tǒng)的典型特征

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

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

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

1.2組成部分

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

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

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

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

1.3系統(tǒng)參數(shù)

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

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

修船碼頭的泊位調度排隊系統(tǒng)如圖1所示。

圖1 修船碼頭排隊系統(tǒng)框圖

排隊系統(tǒng)還存在以下重要參數(shù)。

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

系統(tǒng)中的船舶艘數(shù) = 等待服務的船舶艘數(shù) + 正被服務的船舶艘數(shù)。

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

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

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

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

2 修船碼頭泊位調度系統(tǒng)的排隊模型

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

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

(1)

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

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

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

(2)

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

可以得到系統(tǒng)的狀態(tài)概率平衡方程并由遞推關系可得系統(tǒng)狀態(tài)概率：

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

(3)

(4)

系統(tǒng)的運行指標：

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

(5)

(6)

(7)

Ws=Wq+1/μ,

(8)

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

3 算例

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

由式(3)可知系統(tǒng)的狀態(tài)概率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)表示一定周期內實際進入碼頭的船舶艘數(shù)，在穩(wěn)定狀態(tài)下，即為一定周期內實際完成靠泊的船舶艘數(shù)。系統(tǒng)滿員的損失率：

(9)

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

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

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

4 結束語

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

[1] 王庚，王敏生. 現(xiàn)代數(shù)學建模方法[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