魏煥東 劉建民

關(guān)鍵詞： 到達(dá)率隨時(shí)間變化; 周期到達(dá); 多服務(wù)隊(duì)列; 服務(wù)中斷; 高負(fù)荷條件; 模擬仿真

中圖分類號： TN911?34; O226 ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼： A ? ? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2019）05?0169?04

Simulation of periodic arrival queue with service interrupt

WEI Huandong， LIU Jianmin

（College of Science， Changan University， Xian 710064， China）

Abstract： The thought of continuous time discretization is used to design a simulation algorithm of multi?server system with service interrupt. The periodic arrival queue model is combined with service interrupt to simulate the [Mt/M/n] model with service interrupt by means of Matlab programming under heavy load condition. The algorithm provides a new idea for the simulation of multiserver queue model. The random number generation method and restricted condition model are modified to extend the queue to [G/M/n+M] and [G/M/n/K+M] models.

Keywords： time?varying arrival rate; periodic arrival process; multiserver queue; service interrupt; heavy load condition; simulation

排隊(duì)是日常生活和工作中經(jīng)常會遇到的現(xiàn)象，在排隊(duì)接受服務(wù)的過程中經(jīng)常會出現(xiàn)服務(wù)中斷的情況。關(guān)于服務(wù)中斷的理論研究前人已經(jīng)做了很多工作，文獻(xiàn)[1?2]研究了服務(wù)中斷對于單服務(wù)隊(duì)列模型的影響;文獻(xiàn)[3]研究了帶有服務(wù)中斷的網(wǎng)絡(luò)隊(duì)列模型;文獻(xiàn)[4]研究了未刻畫的服務(wù)中斷和漸進(jìn)可忽略的服務(wù)中斷兩種情況下[G/M/n+M]模型的隊(duì)長，文獻(xiàn)[5]的研究表明，即使很小的服務(wù)中斷對系統(tǒng)的影響也會很顯著，而且系統(tǒng)規(guī)模越大越脆弱，服務(wù)中斷造成的影響越大;文獻(xiàn)[6]研究了[G/M/n/m+M]模型在未刻畫服務(wù)中斷和服務(wù)中斷漸進(jìn)可忽略條件下模型的高負(fù)荷極限。

關(guān)于排隊(duì)系統(tǒng)模擬仿真的研究，文獻(xiàn)[7]用蒙特卡洛模擬的方法對[M/M/1]模型進(jìn)行模擬仿真;文獻(xiàn)[8]基于Matlab對[M/M/m]排隊(duì)模型進(jìn)行仿真研究;文獻(xiàn)[9]對帶優(yōu)先權(quán)與不耐煩顧客的排隊(duì)模型進(jìn)行模擬仿真。

參考以上研究，本文將周期到達(dá)隊(duì)列模型與服務(wù)中斷結(jié)合起來，在高負(fù)荷的條件下，通過Matlab編程，模擬帶有服務(wù)中斷的[Mt/M/n]模型，為帶有服務(wù)中斷的周期到多服務(wù)排隊(duì)模型的進(jìn)一步研究提供一種仿真算法。

1 ?模型建立

本文考慮的是[Mt/M/n]隊(duì)列模型，其到達(dá)率函數(shù)為一個(gè)周期函數(shù)[λ（t）]，具有[n]個(gè)并聯(lián)的服務(wù)臺并且服從先到先服務(wù)規(guī)則（FCFS），等待空間沒有限制。假設(shè)服務(wù)中斷均由外因造成，當(dāng)發(fā)生服務(wù)中斷時(shí)，部分或全部服務(wù)臺停止工作，而顧客仍持續(xù)到達(dá)并進(jìn)入隊(duì)列，受到服務(wù)中斷影響正在接受服務(wù)的顧客在中斷結(jié)束后完成剩余服務(wù)并離開。假設(shè)沒有服務(wù)中斷時(shí)，每個(gè)服務(wù)臺的服務(wù)率是[μ1>0]，在服務(wù)中斷時(shí)，每個(gè)運(yùn)行服務(wù)臺的服務(wù)率是[μ2≥0]，顯然[μ1≥μ2]是合理的，本文假設(shè)[μ1=μ2]。

根據(jù)到達(dá)率函數(shù)定義到達(dá)過程[A（t）]，表示[[0，t]]時(shí)間段內(nèi)到達(dá)的顧客數(shù)，[Λ（t）]代表累積到達(dá)函數(shù)：

[Λt=0tλ（s）ds， ? ?t≥0] （1）

則有：

[A（t）=NΛt， ? ?t≥0] （2）

式中[N]是一個(gè)隨機(jī)計(jì)數(shù)過程。

2 ?仿真算法

本文應(yīng)用連續(xù)時(shí)間離散化的思想，對帶有外源性服務(wù)中斷的模型進(jìn)行模擬仿真。首先，根據(jù)式（1）可知[0，T]內(nèi)到達(dá)的顧客總數(shù)，由于顧客到達(dá)過程是單位階躍的，運(yùn)用積分的離散化思想可以將整個(gè)積分區(qū)域看作是一系列面積為1的曲邊梯形的面積和。將累積到達(dá)過程離散化為每個(gè)顧客的到達(dá)時(shí)間，根據(jù)服務(wù)時(shí)間服從指數(shù)分布，模擬出每個(gè)顧客的服務(wù)時(shí)間，從而進(jìn)行整個(gè)系統(tǒng)的模擬仿真。排隊(duì)系統(tǒng)的模擬仿真是通過系統(tǒng)的到達(dá)過程、服務(wù)過程將每個(gè)顧客的到達(dá)、服務(wù)、服務(wù)完離開系統(tǒng)的時(shí)間計(jì)算出來，進(jìn)而判斷在各個(gè)時(shí)刻系統(tǒng)中隊(duì)列長度等指標(biāo)。為了方便顧客信息的儲存，本文構(gòu)建信息矩陣用來存儲每個(gè)顧客的信息，輔助算法的實(shí)現(xiàn)。

2.1 ?信息矩陣state與服務(wù)臺向量serv_desk

根據(jù)系統(tǒng)的到達(dá)過程，模擬出[0，T]內(nèi)到達(dá)的顧客總數(shù)，假設(shè)為[k]，則信息矩陣為一個(gè)[5×k]的矩陣，矩陣的行代表顧客的不同信息，見表1。

矩陣的每一列代表一個(gè)顧客，用[state（i，j）]代表矩陣第[i]行第[j]列的元素。

系統(tǒng)是多服務(wù)系統(tǒng)，具有多個(gè)服務(wù)臺，建立一個(gè)向量serv_desk保存每個(gè)服務(wù)臺上最近一個(gè)顧客完成服務(wù)的離開時(shí)間，該向量是一個(gè)[1×n]的向量，[n]為服務(wù)臺數(shù)，用[serv_desk（i）]表示serv_desk向量中的第[i]個(gè)元素。

2.2 ?信息矩陣與向量的初始化

對于信息矩陣，根據(jù)顧客的累積到達(dá)函數(shù)和積分離散化思想可以模擬出顧客的到達(dá)時(shí)間，根據(jù)顧客服務(wù)服從指數(shù)分布，模擬出顧客的服務(wù)時(shí)間，將其輸入矩陣的第一、二行;由于系統(tǒng)具有[n]個(gè)服務(wù)臺，顯然前[n]個(gè)顧客的等待時(shí)間肯定為0，不需要等待就可以進(jìn)入服務(wù)臺接受服務(wù)，輸入矩陣第三行前[n]列;顧客的離開時(shí)間等于進(jìn)入顧客的到達(dá)時(shí)間、等待時(shí)間以及服務(wù)時(shí)間之和，從而可以得出前[n]個(gè)顧客離開系統(tǒng)的時(shí)間，輸入矩陣的第四行前[n]列。顧客按順序到達(dá)和進(jìn)入服務(wù)臺，初始化的服務(wù)臺向量[serv_desk]保存的數(shù)據(jù)為前[n-1]個(gè)顧客按照到達(dá)順序的離開時(shí)間，即令：

[serv_desk（i）=state（4，i）， ? 1≤i≤n-1]

[serv_desk（n）=0]

并且將服務(wù)臺位置保存在矩陣的第五行前[n-1]列。

2.3 ?更新算法

為了簡化模型，本文假設(shè)顧客進(jìn)入服務(wù)臺會優(yōu)先選擇最早已完成服務(wù)空閑下來的服務(wù)臺。根據(jù)初始矩陣，當(dāng)?shù)赱i（n

[wait_time=wait_time1+wait_time2] （3）

式中：[wait_time1]為顧客從進(jìn)入隊(duì)列到到達(dá)隊(duì)列排頭的等待時(shí)間;[wait_time 2]為顧客在排頭等待進(jìn)入服務(wù)的等待時(shí)間。對于[wait_time1]，很容易得出第[i]個(gè)顧客從進(jìn)入系統(tǒng)到到達(dá)隊(duì)列排頭的等待時(shí)間為：

[wait_time1（i）=max 0，state1，i-1+state3，i-1-state1，i] （4）

式中：[state（1，i-1）]為第[i-1]個(gè)顧客的到達(dá)時(shí)間;[state（3，i-1）]為第[i-1]個(gè)顧客的等待時(shí)間;[state（1，i-1）+state（3，i-1）]表示第[i-1]個(gè)顧客進(jìn)入服務(wù)臺的時(shí)間。第[i-1]個(gè)顧客進(jìn)入服務(wù)臺，若此時(shí)第[i]個(gè)顧客已經(jīng)在系統(tǒng)中到達(dá)隊(duì)列的排頭，[wait_time 1（i）]就為第[i-1]個(gè)顧客進(jìn)入服務(wù)臺的時(shí)間與第[i]個(gè)顧客到達(dá)時(shí)間之差;當(dāng)?shù)赱i]個(gè)顧客在第[i-1]個(gè)顧客進(jìn)入服務(wù)臺之后到達(dá)，此時(shí)[wait_time1（i）]為0。

第[i]個(gè)顧客到達(dá)排頭說明第[i-1]個(gè)顧客已經(jīng)進(jìn)入了服務(wù)臺，此時(shí)需要更新serv_desk向量，令：

[min （serv_desk） =state（4，i-1）] （5）

式中[min （serv_desk）]為serv_desk向量的[n]個(gè)元素中的最小值，用第[i-1]個(gè)顧客的離開時(shí)間替換serv_desk向量中最小的元素，得到新的serv_desk向量，并且保存serv_desk向量更新元素的位置，更新state矩陣第五行。

初始化以后第一個(gè)到達(dá)的顧客，即第[n+1]個(gè)顧客到達(dá)時(shí)，根據(jù)假設(shè)可知，第[n+1]個(gè)顧客到達(dá)時(shí)若服務(wù)臺有空位可以直接服務(wù)，若無空位也可以直接在隊(duì)列排頭，因此第[n+1]個(gè)顧客到達(dá)排頭的等待時(shí)間[wait_time1=0]，此時(shí)更新服務(wù)臺向量，令：

[min （serv_desk） =state（4，n）]

即：

[serv_desk（n）=state（4，n）]

更新后的服務(wù)臺向量為當(dāng)?shù)赱n+1]個(gè)顧客在隊(duì)列排頭時(shí)所面對的服務(wù)臺情況，即前[n]個(gè)顧客按照順序到達(dá)和進(jìn)入服務(wù)臺，這就是服務(wù)臺向量[serv_desk]初始化的原因。

接下來計(jì)算[wait_time2（i）]，即第[i]個(gè)顧客在排頭等待進(jìn)入服務(wù)的等待時(shí)間：

[wait_time2（i）=max （0，min （serv_desk）-state（1，i）-wait_time1（i））] （6）

式中：[state（1，i）]為第[i]個(gè)顧客的到達(dá)時(shí)間;[state1，i+wait_time1（i）]為第[i]個(gè)顧客到達(dá)隊(duì)列排頭的時(shí)間。當(dāng)：

[min （serv_desk）≤state（1，i）+wait_time1（i）] （7）

成立說明第[i]個(gè)顧客到達(dá)隊(duì)列排頭時(shí)服務(wù)臺有空位;反之，說明沒有空位需要等待，此時(shí)等待時(shí)間為服務(wù)臺有空位時(shí)間與顧客到達(dá)排頭時(shí)間之差。

計(jì)算出顧客的等待時(shí)間，更新信息矩陣state第三行，令：

[state4，i=state1，i+state2，i+state（3，i）] （8）

即顧客的離開時(shí)間等于顧客的到達(dá)時(shí)間、等待時(shí)間與服務(wù)時(shí)間之和。更新信息矩陣state第四行。

2.4 ?對服務(wù)中斷的處理

對服務(wù)中斷的處理關(guān)鍵是判斷哪些顧客直接受到服務(wù)中斷的影響，需要在服務(wù)臺上等待，未直接受到服務(wù)中斷影響的顧客在隊(duì)列中的等待時(shí)間與前文中對于等待時(shí)間的分析是一致的。在所有的[k]個(gè)顧客中，有一部分顧客不會受到服務(wù)中斷的影響，即在服務(wù)中斷開始前便已完成服務(wù)并離開的顧客。當(dāng)服務(wù)中斷開始時(shí)，在受到影響的服務(wù)臺上正在接受服務(wù)的顧客中斷服務(wù)，等待中斷結(jié)束后繼續(xù)服務(wù)。

假設(shè)服務(wù)中斷在[t（0

[state4，i=state4，i+Δt] （9）

假設(shè)第[i]個(gè)顧客位于受到中斷影響的服務(wù)臺，當(dāng)：

[state1，i+state3，i≤t且state（4，i）>t] （10）

表明第[i]個(gè)顧客在服務(wù)中斷開始前便已進(jìn)入服務(wù)臺并且在服務(wù)中斷發(fā)生之前并不能完成服務(wù)離開，此時(shí)第[i]個(gè)顧客會直接受到服務(wù)中斷的影響。式中[state1，i+state3，i]表示第[i]個(gè)顧客進(jìn)入服務(wù)臺的時(shí)間。根據(jù)式（9）更新信息矩陣state第四行，加入服務(wù)中斷的影響。

2.5 ?模擬系統(tǒng)的隊(duì)長過程及服務(wù)過程

隊(duì)長過程即每個(gè)時(shí)刻系統(tǒng)中的顧客數(shù)，包括在隊(duì)列中等待的顧客數(shù)以及在服務(wù)臺上正在接受服務(wù)的顧客數(shù)。通過對每個(gè)顧客的分析，得到每個(gè)顧客的到達(dá)、服務(wù)、等待、離開時(shí)間，將信息保存在信息矩陣state。對于時(shí)刻[t]，當(dāng)顧客在時(shí)刻[t]之前到達(dá)，并且在時(shí)刻[t]之后才能離開系統(tǒng)，說明在[t]時(shí)刻該顧客在系統(tǒng)中，即：

[state（1，i）≤t且state（4，i）>t] （11）

式（11）成立時(shí)顧客[i]在[t]時(shí)刻處于系統(tǒng)中。

服務(wù)過程，即每個(gè)時(shí)刻已服務(wù)完成離開系統(tǒng)的顧客數(shù)。對于時(shí)刻[t]，當(dāng)顧客在時(shí)刻[t]之前離開系統(tǒng)，說明在[t]時(shí)刻顧客已經(jīng)離開系統(tǒng)，即：

[state（4，i）≥t] （12）

式（12）成立時(shí)顧客[i]在[t]時(shí)刻已服務(wù)完成。

3 ?模擬仿真

假設(shè)系統(tǒng)初始為空，服務(wù)臺的個(gè)數(shù)為[n]，到達(dá)率為[nλ（t）]，[λt=1+0.6×sin （x）]，根據(jù)到達(dá)率函數(shù)模擬出顧客的到達(dá)時(shí)間，服務(wù)時(shí)間服從指數(shù)分布，仿真時(shí)間為[0，T，T=16]。

首先定義外源性服務(wù)中斷，由于模擬仍舊較小，所以取一個(gè)比較大的中斷時(shí)間令模擬效果更明顯。假設(shè)系統(tǒng)在[[7，12]]之間發(fā)生服務(wù)中斷，發(fā)生中斷時(shí)只有一半的服務(wù)臺繼續(xù)運(yùn)行，當(dāng)系統(tǒng)運(yùn)行到時(shí)刻7時(shí)，系統(tǒng)發(fā)生服務(wù)中斷，中斷時(shí)間為5，中斷服務(wù)臺上的顧客的剩余服務(wù)在服務(wù)中斷結(jié)束以后再繼續(xù)進(jìn)行，本文假設(shè)由serv_desk向量前一半元素所代表的服務(wù)臺為中斷時(shí)停止服務(wù)的服務(wù)臺，下面對系統(tǒng)的運(yùn)行隊(duì)長和服務(wù)進(jìn)行模擬仿真。

1） 取[n=10]，[μ1=μ2=1]，首先給出顧客到達(dá)過程，如圖1所示。顧客帶有服務(wù)中斷和無服務(wù)中斷的隊(duì)長過程以及服務(wù)過程如圖2，圖3所示。

由圖2，圖3可以看出，當(dāng)服務(wù)中斷發(fā)生時(shí)，相較于沒有服務(wù)中斷影響的系統(tǒng)，隊(duì)長會受到影響而變長，相同的時(shí)間內(nèi)服務(wù)的顧客數(shù)減少，若考慮到顧客不耐煩，服務(wù)中斷導(dǎo)致系統(tǒng)隊(duì)列延長，顧客等待時(shí)間增加進(jìn)而導(dǎo)致顧客流失的增加;同樣，過長的隊(duì)列會影響潛在顧客進(jìn)入系統(tǒng)的欲望，若系統(tǒng)等待空間有限也會使得阻塞流失的顧客數(shù)增加，從而增大了系統(tǒng)的潛在損失。

2） 取[n=20]，[μ1=μ2=1]，顧客到達(dá)過程，如圖4所示，顧客帶有服務(wù)中斷和無服務(wù)中斷的隊(duì)長過程及服務(wù)過程如圖5，圖6所示。

通過對比圖2，圖5可以看出，[n=20]時(shí)比[n=10]時(shí)服務(wù)中斷對于系統(tǒng)隊(duì)長過程的影響更大，圖5中有服務(wù)中斷影響的曲線偏離無服務(wù)中斷曲線的程度更高，這也驗(yàn)證了文獻(xiàn)[5]的研究，即系統(tǒng)規(guī)模越大對服務(wù)中斷越敏感，服務(wù)中斷造成的影響越大。

4 ?結(jié) ?語

本文運(yùn)用連續(xù)時(shí)間離散化的思想，設(shè)計(jì)了一種帶有服務(wù)中斷的多服務(wù)器系統(tǒng)的仿真算法，研究了帶有服務(wù)中斷的周期到達(dá)隊(duì)列系統(tǒng)運(yùn)行狀況的模擬仿真，通過與理論算法比較證明是可行的。仿真算法的思想應(yīng)用廣泛，對顧客等待時(shí)間的分解處理與服務(wù)臺向量的運(yùn)用同樣可以應(yīng)用于其他任意的多服務(wù)臺系統(tǒng)的模擬仿真，為多服務(wù)臺排隊(duì)模型的模擬仿真提供了一種可行而簡便的算法思路，通過修改隨機(jī)數(shù)產(chǎn)生方法和限制條件模型可以拓展到[G/M/n+M]，[G/M/n/K+M]模型等。

參考文獻(xiàn)

[1] KELLA Offer， WHITT Ward. Diffusion approximations for queues with server vacations [J]. Advances in applied probability， 1990， 22（3）： 706?729.

[2] CHEN Hong， WHITT Ward. Diffusion approximation for multiclass feedforward queueing network [J]. Annals of applied pro?bability， 2000， 10（3）： 828?836.

[3] WHITT Ward. Stochastic?process limits [M]. New York： Sprin?ger， 2002.

[4] PANG Guodong， WHITT Ward. Heavy?traffic limits for many?server queues with service interruptions [J]. Queueing systems， 2009， 61（2/3）： 167?202.

[5] PANG Guodong， WHITT Ward. Service interruptions in large?scale service systems [J]. Management science， 2009， 55（9）： 1499?1512.

[6] 王利妙.帶有服務(wù)中斷且等待空間有限的隊(duì)列的高負(fù)荷極限[D].西安：長安大學(xué)，2013.

WANG Limiao. Heavy?traffic for queueing models with service interruptions and finite waiting room [D]. Xian： Changan University， 2013.

[7] 張建航，李宗成，宋曉峰.單服務(wù)員排隊(duì)模型及其蒙特卡洛模擬[J].現(xiàn)代電子技術(shù)，2006，29（24）：44?46.

ZHANG Jianhang， LI Zongcheng， SONG Xiaofeng. [M/M/1] model and the solving by using the Monte?Carlo method [J]. Modern electronics technique， 2006， 29（24）： 44?46.

[8] 宋振峰，席志紅，劉飛.基于Matlab的[M/M/m]排隊(duì)模型的仿真[J].現(xiàn)代電子技術(shù)，2005，28（6）：29?30.

SONG Zhenfeng， XI Zhihong， LIU Fei. Simulation of [M/M/m] queue model based on Matlab [J]. Modern electronics technique， 2005， 28（6）： 29?30.

[9] 秦海林，劉建民.帶優(yōu)先權(quán)與不耐煩顧客排隊(duì)模型的模擬仿真[J].現(xiàn)代電子技術(shù)，2012，35（20）：91?94.

QIN Hailin， LIU Jianmin. Simulation of queueing model with preemption and impatience customers [J]. Modern electronics technique， 2012， 35（20）： 91?94.

[10] 熊光楞，肖田元，張燕立.連續(xù)系統(tǒng)仿真與離散事件系統(tǒng)仿真[M].北京：清華大學(xué)出版社，1999.

XIONG Guangleng， XIAO Tianyuan， ZHANG Yanli. Simulation of continuous systems and discrete?event system [M]. Beijing： Tsinghua University Press， 1999.