魏煥東 劉建民

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

中圖分類號： TN911?34; O226 ? ? ? ? ? ? ? ? ? ? 文獻標識碼： 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

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

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

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

1 ?模型建立

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

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

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

則有：

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

式中[N]是一個隨機計數(shù)過程。

2 ?仿真算法

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

2.1 ?信息矩陣state與服務臺向量serv_desk

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

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

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

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

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

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

[serv_desk（n）=0]

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

2.3 ?更新算法

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

[wait_time=wait_time1+wait_time2] （3）

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

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

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

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

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

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

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

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

即：

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

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

接下來計算[wait_time2（i）]，即第[i]個顧客在排頭等待進入服務的等待時間：

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

式中：[state（1，i）]為第[i]個顧客的到達時間;[state1，i+wait_time1（i）]為第[i]個顧客到達隊列排頭的時間。當：

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

成立說明第[i]個顧客到達隊列排頭時服務臺有空位;反之，說明沒有空位需要等待，此時等待時間為服務臺有空位時間與顧客到達排頭時間之差。

計算出顧客的等待時間，更新信息矩陣state第三行，令：

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

即顧客的離開時間等于顧客的到達時間、等待時間與服務時間之和。更新信息矩陣state第四行。

2.4 ?對服務中斷的處理

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

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

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

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

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

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

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

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

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

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

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

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

式（12）成立時顧客[i]在[t]時刻已服務完成。

3 ?模擬仿真

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

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

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

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

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

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

4 ?結(jié) ?語

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

參考文獻

[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] 王利妙.帶有服務中斷且等待空間有限的隊列的高負荷極限[D].西安：長安大學，2013.

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

[7] 張建航，李宗成，宋曉峰.單服務員排隊模型及其蒙特卡洛模擬[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]排隊模型的仿真[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)與不耐煩顧客排隊模型的模擬仿真[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].北京：清華大學出版社，1999.

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