詹曉琳，張 瑜

（上海第二工業(yè)大學(xué)理學(xué)院，上海201209）

單排隊(duì)模型的隨機(jī)模擬

詹曉琳，張 瑜

（上海第二工業(yè)大學(xué)理學(xué)院，上海201209）

單服務(wù)臺(tái)的排隊(duì)模型（M/M/1等待制排隊(duì)模型）是排隊(duì)論中簡(jiǎn)單且重要的排隊(duì)系統(tǒng)。隨機(jī)模擬是求解排隊(duì)系統(tǒng)和分析排隊(duì)系統(tǒng)非常有效的方法。針對(duì)單服務(wù)臺(tái)的排隊(duì)模型，給出了兩種不同隨機(jī)模擬的方法和必要的數(shù)學(xué)算法，并進(jìn)一步比較了兩種算法的優(yōu)劣。

單服務(wù)臺(tái)排隊(duì)模型；隨機(jī)模擬；排隊(duì)系統(tǒng)

0 引言

排隊(duì)論又稱為隨機(jī)服務(wù)系統(tǒng)理論。隨機(jī)服務(wù)系統(tǒng)是指對(duì)隨機(jī)發(fā)生的需求提供服務(wù)的系統(tǒng)。現(xiàn)實(shí)世界中廣泛存在著各種各樣的隨機(jī)服務(wù)系統(tǒng)，如病人候診、飛機(jī)等待起飛、原材料等待加工、電話等待轉(zhuǎn)接等等。這里將要求得到服務(wù)的對(duì)象稱為“顧客”，將提供服務(wù)的服務(wù)者稱為“服務(wù)臺(tái)”。這里“隨機(jī)”是指顧客相繼到達(dá)的時(shí)間間隔和服務(wù)時(shí)間這兩個(gè)量中至少有一個(gè)是隨機(jī)的。排隊(duì)系統(tǒng)研究的主要內(nèi)容是排隊(duì)系統(tǒng)的運(yùn)行指標(biāo)和排隊(duì)系統(tǒng)的優(yōu)化問題。隨機(jī)模擬方法是利用隨機(jī)數(shù)對(duì)隨機(jī)系統(tǒng)的仿真，通常是利用計(jì)算機(jī)并通過建立數(shù)學(xué)邏輯模型對(duì)現(xiàn)實(shí)系統(tǒng)進(jìn)行仿真，最終實(shí)現(xiàn)模擬的目的，又稱為計(jì)算機(jī)模擬方法[1-2]。這是一條解決具有隨機(jī)因素的復(fù)雜實(shí)際問題的有效途徑。因此，隨機(jī)模擬是研究排隊(duì)系統(tǒng)性能、求解排隊(duì)系統(tǒng)運(yùn)行指標(biāo)非常有效的方法。本文針對(duì)單服務(wù)臺(tái)等待制的排隊(duì)模型提供兩種不同的模擬思想，并給出相應(yīng)的具體算法，最終利用Matlab軟件實(shí)現(xiàn)算法。最后，對(duì)兩種算法的優(yōu)劣進(jìn)行比較。

1 排隊(duì)系統(tǒng)及主要運(yùn)行指標(biāo)

實(shí)際的排隊(duì)系統(tǒng)各有不同，但概括起來都由3個(gè)基本部分組成：輸入過程，排隊(duì)及排隊(duì)規(guī)則和服務(wù)機(jī)制。輸入過程是說明顧客按怎樣的規(guī)律到達(dá)系統(tǒng)；排隊(duì)及排隊(duì)規(guī)則是排隊(duì)隊(duì)伍是否有限和服務(wù)臺(tái)對(duì)排隊(duì)顧客進(jìn)行服務(wù)時(shí)所遵循的規(guī)則；服務(wù)機(jī)制主要包括服務(wù)臺(tái)的數(shù)量及其連接形式（串聯(lián)或并聯(lián)）、顧客是單個(gè)還是成批接受服務(wù)及服務(wù)時(shí)間的分布。

描述一個(gè)排隊(duì)系統(tǒng)運(yùn)行狀況的主要數(shù)量指標(biāo)有：（1）隊(duì)長(zhǎng)和排隊(duì)長(zhǎng)，隊(duì)長(zhǎng)是指系統(tǒng)中的排隊(duì)等待的顧客數(shù)與正在接受服務(wù)的顧客數(shù)之和，排隊(duì)長(zhǎng)是指系統(tǒng)中正在排隊(duì)等待服務(wù)的顧客數(shù)。（2）等待時(shí)間和逗留時(shí)間，等待時(shí)間是指從顧客達(dá)到時(shí)刻起到開始接受服務(wù)止這段時(shí)間，逗留時(shí)間是指顧客到達(dá)時(shí)刻起到他接受服務(wù)完成止這段時(shí)間。（3）忙期和閑期，忙期是指服務(wù)臺(tái)連續(xù)忙碌的時(shí)間，閑期是指服務(wù)臺(tái)連續(xù)保持空閑的時(shí)間。以上6個(gè)量均是隨機(jī)變量，通常排隊(duì)論中關(guān)心的是當(dāng)系統(tǒng)達(dá)到平衡狀態(tài)時(shí)以上6個(gè)變量的平均值，相應(yīng)的符號(hào)定義如下：平均隊(duì)長(zhǎng)L，平均排隊(duì)長(zhǎng)Lq，平均等待時(shí)間Wq，平均逗留時(shí)間W，平均忙期B，平均閑期。

2 M/M/1等待制排隊(duì)模型的數(shù)學(xué)特性

本文中研究的單服務(wù)臺(tái)等待制排隊(duì)模型的定義如下：顧客源無限，顧客單個(gè)到達(dá)，顧客相繼達(dá)到的時(shí)間間隔服從參數(shù)為λ的指數(shù)分布；服務(wù)臺(tái)的數(shù)量是一個(gè)，顧客單個(gè)接受服務(wù)，服務(wù)時(shí)間服從參數(shù)為μ的指數(shù)分布；排隊(duì)系統(tǒng)容量無限，允許無限排隊(duì)，排隊(duì)規(guī)則為先到先服務(wù)（FCFS）。利用排隊(duì)論廣泛采用的“Kendall記號(hào)”，該模型記為M/M/1/∞/∞/FCFS ，根據(jù)排隊(duì)論的約定該模型可以簡(jiǎn)記為M/M/1。

定義ρ= λ/μ，不難得出ρ是指系統(tǒng)中至少有一個(gè)顧客的概率，即服務(wù)臺(tái)處于忙碌狀態(tài)的概率，因而也稱ρ為服務(wù)強(qiáng)度或服務(wù)利用率。此外，只有在ρ<1的條件下才能使系統(tǒng)達(dá)到統(tǒng)計(jì)平衡。由概率統(tǒng)計(jì)的理論分析可以得到M/M/1系統(tǒng)在平衡狀態(tài)時(shí)的6個(gè)重要指標(biāo)的數(shù)學(xué)特性如下[3]

這是6個(gè)指標(biāo)的理論值，由理論值的表達(dá)式不難看出，他們之間有如下關(guān)系：L=λW,Lq=λWq,W=前兩個(gè)關(guān)系稱為L(zhǎng)ittle公式，是排隊(duì)論中一個(gè)非常重要的公式。在M/M/1系統(tǒng)的隨機(jī)模擬中，本文僅關(guān)注其中的3個(gè)指標(biāo)：平均排隊(duì)長(zhǎng)Lq, 平均等待時(shí)間Wq, 平均忙期B, 以及服務(wù)利用率, 期望得到上述4個(gè)指標(biāo)的模擬值。通過模擬值與理論值的誤差大小說明模擬的有效性。其余3個(gè)運(yùn)行指標(biāo)的模擬值可以用類似算法得到。

3 M/M/1等待制排隊(duì)模型的隨機(jī)模擬

M/M/1等待制排隊(duì)模型在現(xiàn)實(shí)生活中隨處可見，它是一種簡(jiǎn)單而重要的排隊(duì)模型，對(duì)于該模型的隨機(jī)模擬的研究可以幫助研究更復(fù)雜的多服務(wù)臺(tái)的排隊(duì)模型的隨機(jī)模擬。當(dāng)多服務(wù)臺(tái)的排隊(duì)系統(tǒng)在輸入過程、排隊(duì)及排隊(duì)規(guī)則或是服務(wù)機(jī)制中的一方面或多方面比較復(fù)雜時(shí)，有關(guān)它的運(yùn)行指標(biāo)的理論值將很難獲得，這時(shí)，隨機(jī)模擬成為一種獲得近似值的唯一方法。同時(shí)，當(dāng)單服務(wù)臺(tái)排隊(duì)系統(tǒng)的1ρ<的條件不滿足時(shí)，系統(tǒng)無法達(dá)到平衡，此時(shí)6個(gè)運(yùn)行指標(biāo)的理論值失效，但這些運(yùn)行指標(biāo)的實(shí)際值可以通過隨機(jī)模擬近似獲得。本文在以下三點(diǎn)假設(shè)下，對(duì)M/M/1系統(tǒng)在兩種不同的模擬思想下提出兩種不同的模擬算法對(duì)該系統(tǒng)進(jìn)行了隨機(jī)模擬。

假設(shè)3 時(shí)間單位為分鐘，一個(gè)工作日的服務(wù)時(shí)間為8小時(shí)，即480分鐘，服務(wù)滿480分鐘時(shí)不再服務(wù)下一位顧客，無論是否有顧客排隊(duì)。

3.1 “下一顧客法”的隨機(jī)模擬

“下一顧客法”的建模思想是以顧客為主線。首先，隨機(jī)產(chǎn)生若干位顧客的到達(dá)間隔和服務(wù)時(shí)間；其次，在服務(wù)時(shí)間內(nèi)逐個(gè)討論并記錄每個(gè)顧客的到達(dá)時(shí)間、離開時(shí)間、開始服務(wù)時(shí)間、等待時(shí)間；最后利用這些時(shí)間記錄，分別設(shè)計(jì)算法模擬出4個(gè)運(yùn)行指標(biāo)。在記錄時(shí)間和模擬運(yùn)行指標(biāo)的過程中，都是按照先到先服務(wù)的規(guī)則，分析好前一個(gè)顧客再分析下一個(gè)顧客，一個(gè)顧客一個(gè)顧客地逐一清點(diǎn)，直到服務(wù)時(shí)間結(jié)束。因此，稱這種模擬方法為“下一顧客法”。

參數(shù)說明：ix為第i個(gè)顧客的到達(dá)間隔；iy為第i個(gè)顧客的服務(wù)時(shí)間；ia為第i個(gè)顧客到達(dá)的時(shí)刻；ib為第i個(gè)顧客服務(wù)開始的時(shí)刻；iw為第i個(gè)顧客等待的時(shí)間；il為第i個(gè)顧客的離開時(shí)刻；iaq為第i個(gè)顧客到達(dá)時(shí)的隊(duì)長(zhǎng)；ilq為第i個(gè)顧客離開時(shí)的隊(duì)長(zhǎng)。

具體算法如下：

1）首先獲得關(guān)于4個(gè)時(shí)間的遞推算法

2）其次分別討論關(guān)于4個(gè)運(yùn)行指標(biāo)的算法

(4) Lq的算法相對(duì)復(fù)雜

首先，將ai, li, i=1,…,n按時(shí)間先后排列起來；

其次，逐一清點(diǎn)第i個(gè)顧客到達(dá)時(shí)的隊(duì)伍長(zhǎng)度, aqi=i?1?前(i?1)人中離開系統(tǒng)的人數(shù)；

然后，逐一清點(diǎn)第i個(gè)顧客離開時(shí)的隊(duì)伍長(zhǎng)度, lqi=max (前一時(shí)刻的隊(duì)長(zhǎng)?1, 0)；

3.2 “下一事件法”的隨機(jī)模擬

“下一事件法”的建模思想是以時(shí)間為主線，所以這個(gè)算法在實(shí)現(xiàn)時(shí)為系統(tǒng)設(shè)置了一個(gè)系統(tǒng)時(shí)鐘t，這個(gè)時(shí)鐘記錄著時(shí)刻的變化，并根據(jù)改變系統(tǒng)狀態(tài)的事件的發(fā)生依次向前推進(jìn)，直到服務(wù)時(shí)間結(jié)束。這里的系統(tǒng)狀態(tài)是指顧客排隊(duì)長(zhǎng)度和服務(wù)臺(tái)是否空閑。在這個(gè)系統(tǒng)中，顯然“顧客到達(dá)”和“顧客離開”這兩個(gè)事件是改變系統(tǒng)狀態(tài)的事件。

參數(shù)說明：t為當(dāng)前時(shí)鐘；tA為有顧客到達(dá)的時(shí)刻；tD為有顧客離開的時(shí)刻；lW為顧客的排隊(duì)長(zhǎng)度；S為服務(wù)臺(tái)的狀態(tài)（=0S時(shí)定義服務(wù)臺(tái)空閑，=1S時(shí)定義服務(wù)臺(tái)忙）；x為顧客到達(dá)的時(shí)間間隔；y為顧客的服務(wù)時(shí)間。

具體算法如下：

首先，在服務(wù)開始時(shí)刻，將系統(tǒng)時(shí)鐘置為t=0，Dt=999（至少大于一個(gè)工作日的服務(wù)時(shí)間480分鐘），S=0（系統(tǒng)當(dāng)前處于空閑狀態(tài)），Wl=0（當(dāng)前隊(duì)列中無人排隊(duì)）。讓系統(tǒng)產(chǎn)生一個(gè)到達(dá)間隔x和服務(wù)時(shí)間y,更新At。其次，對(duì)系統(tǒng)進(jìn)行判斷，如果當(dāng)前服務(wù)臺(tái)為空，則直接為顧客提供服務(wù)，并產(chǎn)生一個(gè)服務(wù)時(shí)間y, 同時(shí)更新顧客離開時(shí)刻Dt；若服務(wù)臺(tái)忙，則讓顧客排隊(duì)，因?yàn)閷?shí)施的是等待制。之后繼續(xù)比較At、Dt大小，并讓系統(tǒng)時(shí)鐘t調(diào)至較小的時(shí)刻，若是At較小，則按照有顧客到達(dá)的情況處理；反之，則按照有顧客離開的情況處理。若At, Dt相等，則同時(shí)處理顧客到達(dá)事件和顧客離開事件。在處理過程中，一旦出現(xiàn)服務(wù)臺(tái)空閑就需要令Dt=999，這樣可以保證系統(tǒng)時(shí)鐘t在下一刻跳到“顧客到達(dá)”時(shí)刻。因?yàn)樵谀M過程中，讓t依事件發(fā)生的先后順序，從一個(gè)事件的發(fā)生跳到下一個(gè)事件的發(fā)生時(shí)刻。所以稱這種模擬方法為“下一事件法”。

圖1 “下一事件法”算法流程圖Fig. 1 “Next event” algorithm flowchart

4 結(jié)論

通過Matlab軟件編程，分別實(shí)現(xiàn)兩種算法，并將1 000個(gè)工作日的模擬值的平均值作為最終運(yùn)行指標(biāo)的模擬值，同時(shí)計(jì)算1 000個(gè)工作日模擬值的均方差?，F(xiàn)將兩種算法的理論值、模擬值和模擬值的均方差列于表1。

表1 兩種算法的結(jié)果比較Tab. 1 Comparison of results of the two algorithms

通過模擬值的比較，可以看出“下一顧客法”對(duì)于服務(wù)利用率和平均忙期的模擬結(jié)果較優(yōu)，“下一顧客法”對(duì)于平均排隊(duì)長(zhǎng)度和平均等待時(shí)間的模擬結(jié)果較優(yōu)。在建模思想上，“下一顧客法”的建模思想比較簡(jiǎn)單，“下一事件法”的建模思想比較巧妙。在算法的復(fù)雜性方面，“下一顧客法”因?yàn)槿菀子涗浢恳粋€(gè)顧客等待的時(shí)間，所以“平均等待時(shí)間”的算法相對(duì)簡(jiǎn)單；“下一事件法”因?yàn)槿菀子涗涱櫩偷竭_(dá)和顧客離開時(shí)的隊(duì)長(zhǎng)，所以關(guān)于“平均排隊(duì)長(zhǎng)”的算法相對(duì)簡(jiǎn)單。在算法的可推廣方面，利用“下一顧客法”和“下一事件法”的建模思想都可以推廣到多服務(wù)臺(tái)的排隊(duì)模型，且推廣后的算法復(fù)雜程度基本相當(dāng)。

[1] 高惠璇. 統(tǒng)計(jì)計(jì)算[M]. 北京: 北京大學(xué)出版社, 1995.

[2] 徐仲濟(jì). 蒙特卡洛方法[M]. 上海: 上海科學(xué)技術(shù)出版社, 1985.

[3] 胡運(yùn)權(quán), 郭耀煌. 運(yùn)籌學(xué)教程[M]. 北京: 清華大學(xué)出版社, 2007.

[4] 嚴(yán)剛峰, 黃顯核, 李思明. 排隊(duì)過程的仿真研究[J]. 成都信息工程學(xué)院學(xué)報(bào), 2008, 23(4): 393-400.

[5] 白濤, 曾建潮. 用MATLAB對(duì)離散系統(tǒng)進(jìn)行仿真[J]. 計(jì)算機(jī)工程與應(yīng)用, 2000, 36(9): 98-99.

[6] 董臻圃. 數(shù)學(xué)建模方法與實(shí)踐[M]. 北京: 國(guó)防工業(yè)出版社, 2006.

Stochastic Simulation of Single-Server Queuing Model

ZHAN Xiao-lin, ZHANG Yu
( School of Science, Shanghai Second Polytechnic University, Shanghai 201209, P. R. China )

Single-server queuing model (i.e. M/M/1 waiting queuing model) is the simplest and most important queuing system in the queuing theory. Stochastic simulation is a very effective method to analyze and solve queuing problems. Two different stochastic simulation approaches and according algorithms are given to the single-server queuing model. Advantages and disadvantages of these two approaches are also analyzed.

single-server queuing model; stochastic simulation; queuing system

O212

A

1001-4543(2012)04-0302-05

2012-10-15;

2012-12-18

詹曉琳（1978－），女，安徽蚌埠人，副教授，碩士，主要研究方向?yàn)楦怕式y(tǒng)計(jì)，電子郵箱xlzhan@sf.sspu.cn。