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

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

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

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

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

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

1 修船碼頭移泊排隊(duì)系統(tǒng)的構(gòu)成

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

1)有請(qǐng)求服務(wù)的人或物——請(qǐng)求進(jìn)廠的船舶，我們將此稱為“顧客”。

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

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

1.2組成部分

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

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

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

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

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

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

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

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

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

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

1)隊(duì)長(zhǎng)：指碼頭移泊調(diào)度系統(tǒng)中的船舶艘數(shù)，它的期望值記為L(zhǎng)s；排隊(duì)長(zhǎng)，指在系統(tǒng)中排隊(duì)等待作業(yè)的船舶艘數(shù)，其期望值記為L(zhǎng)q。

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

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

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

船舶逗留時(shí)間 = 船舶等待時(shí)間 +船舶被服務(wù)時(shí)間。

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

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

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

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

(1)

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

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

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

(2)

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

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

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

(3)

(4)

系統(tǒng)的運(yùn)行指標(biāo)：

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

(5)

(6)

(7)

Ws=Wq+1/μ,

(8)

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

3 算例

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

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

當(dāng)n=5時(shí)，0≤n≤C，Pn=4.5×10-9；

當(dāng)n=10時(shí)，0≤n≤C，Pn=4.8×10-7；

當(dāng)n=20時(shí)，C≤n≤N，Pn=4.9×10-4；

當(dāng)n=30時(shí)，C≤n≤N，Pn=PN=0.5。

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

(9)

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

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

即船舶平均排隊(duì)時(shí)間為19天，船舶平均逗留時(shí)間為29天。

4 結(jié)束語

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

[1] 王庚，王敏生. 現(xiàn)代數(shù)學(xué)建模方法[M]. 北京：科學(xué)出版社，2010.

[2] 唐應(yīng)輝，唐小我. 排隊(duì)論一基礎(chǔ)與分析技術(shù)[M]. 北京：科學(xué)出版社，2006.

[3] 孫榮恒,李建平.排隊(duì)論基礎(chǔ)[M].北京：科學(xué)出版社，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-)，女，天津人，在讀博士研究生，研究方向?yàn)榇芭c海洋結(jié)構(gòu)物設(shè)計(jì)制造。

2015-06-01