带有服务中断的周期到达队列的模拟仿真

魏焕东 刘建民

关键词： 到达率随时间变化; 周期到达; 多服务队列; 服务中断; 高负荷条件; 模拟仿真

中图分类号： 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

排队是日常生活和工作中经常会遇到的现象，在排队接受服务的过程中经常会出现服务中断的情况。关于服务中断的理论研究前人已经做了很多工作，文献[1?2]研究了服务中断对于单服务队列模型的影响;文献[3]研究了带有服务中断的网络队列模型;文献[4]研究了未刻画的服务中断和渐进可忽略的服务中断两种情况下[G/M/n+M]模型的队长，文献[5]的研究表明，即使很小的服务中断对系统的影响也会很显著，而且系统规模越大越脆弱，服务中断造成的影响越大;文献[6]研究了[G/M/n/m+M]模型在未刻画服务中断和服务中断渐进可忽略条件下模型的高负荷极限。

关于排队系统模拟仿真的研究，文献[7]用蒙特卡洛模拟的方法对[M/M/1]模型进行模拟仿真;文献[8]基于Matlab对[M/M/m]排队模型进行仿真研究;文献[9]对带优先权与不耐烦顾客的排队模型进行模拟仿真。

参考以上研究，本文将周期到达队列模型与服务中断结合起来，在高负荷的条件下，通过Matlab编程，模拟带有服务中断的[Mt/M/n]模型，为带有服务中断的周期到多服务排队模型的进一步研究提供一种仿真算法。

1  模型建立

本文考虑的是[Mt/M/n]队列模型，其到达率函数为一个周期函数[λ（t）]，具有[n]个并联的服务台并且服从先到先服务规则（FCFS），等待空间没有限制。假设服务中断均由外因造成，当发生服务中断时，部分或全部服务台停止工作，而顾客仍持续到达并进入队列，受到服务中断影响正在接受服务的顾客在中断结束后完成剩余服务并离开。假设没有服务中断时，每个服务台的服务率是[μ1>0]，在服务中断时，每个运行服务台的服务率是[μ2≥0]，显然[μ1≥μ2]是合理的，本文假设[μ1=μ2]。

根据到达率函数定义到达过程[A（t）]，表示[[0，t]]时间段内到达的顾客数，[Λ（t）]代表累积到达函数：

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

则有：

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

式中[N]是一个随机计数过程。

2  仿真算法

本文应用连续时间离散化的思想，对带有外源性服务中断的模型进行模拟仿真。首先，根据式（1）可知[0，T]内到达的顾客总数，由于顾客到达过程是单位阶跃的，运用积分的离散化思想可以将整个积分区域看作是一系列面积为1的曲边梯形的面积和。将累积到达过程离散化为每个顾客的到达时间，根据服务时间服从指数分布，模拟出每个顾客的服务时间，从而进行整个系统的模拟仿真。排队系统的模拟仿真是通过系统的到达过程、服务过程将每个顾客的到达、服务、服务完离开系统的时间计算出来，进而判断在各个时刻系统中队列长度等指标。为了方便顾客信息的储存，本文构建信息矩阵用来存储每个顾客的信息，辅助算法的实现。

2.1  信息矩阵state与服务台向量serv_desk

根据系统的到达过程，模拟出[0，T]内到达的顾客总数，假设为[k]，则信息矩阵为一个[5×k]的矩阵，矩阵的行代表顾客的不同信息，见表1。

矩阵的每一列代表一个顾客，用[state（i，j）]代表矩阵第[i]行第[j]列的元素。

系统是多服务系统，具有多个服务台，建立一个向量serv_desk保存每个服务台上最近一个顾客完成服务的离开时间，该向量是一个[1×n]的向量，[n]为服务台数，用[serv_desk（i）]表示serv_desk向量中的第[i]个元素。

2.2  信息矩阵与向量的初始化

对于信息矩阵，根据顾客的累积到达函数和积分离散化思想可以模拟出顾客的到达时间，根据顾客服务服从指数分布，模拟出顾客的服务时间，将其输入矩阵的第一、二行;由于系统具有[n]个服务台，显然前[n]个顾客的等待时间肯定为0，不需要等待就可以进入服务台接受服务，输入矩阵第三行前[n]列;顾客的离开时间等于进入顾客的到达时间、等待时间以及服务时间之和，从而可以得出前[n]个顾客离开系统的时间，输入矩阵的第四行前[n]列。顾客按顺序到达和进入服务台，初始化的服务台向量[serv_desk]保存的数据为前[n-1]个顾客按照到达顺序的离开时间，即令：

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

[serv_desk（n）=0]

并且将服务台位置保存在矩阵的第五行前[n-1]列。

2.3  更新算法

为了简化模型，本文假设顾客进入服务台会优先选择最早已完成服务空闲下来的服务台。根据初始矩阵，当第[i（n

[wait_time=wait_time1+wait_time2] （3）

式中：[wait_time1]为顾客从进入队列到到达队列排头的等待时间;[wait_time 2]为顾客在排头等待进入服务的等待时间。对于[wait_time1]，很容易得出第[i]个顾客从进入系统到到达队列排头的等待时间为：

[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]个顾客已经在系统中到达队列的排头，[wait_time 1（i）]就为第[i-1]个顾客进入服务台的时间与第[i]个顾客到达时间之差;当第[i]个顾客在第[i-1]个顾客进入服务台之后到达，此时[wait_time1（i）]为0。

第[i]个顾客到达排头说明第[i-1]个顾客已经进入了服务台，此时需要更新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]个顾客到达时，根据假设可知，第[n+1]个顾客到达时若服务台有空位可以直接服务，若无空位也可以直接在队列排头，因此第[n+1]个顾客到达排头的等待时间[wait_time1=0]，此时更新服务台向量，令：

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

即：

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

更新后的服务台向量为当第[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  对服务中断的处理

对服务中断的处理关键是判断哪些顾客直接受到服务中断的影响，需要在服务台上等待，未直接受到服务中断影响的顾客在队列中的等待时間与前文中对于等待时间的分析是一致的。在所有的[k]个顾客中，有一部分顾客不会受到服务中断的影响，即在服务中断开始前便已完成服务并离开的顾客。当服务中断开始时，在受到影响的服务台上正在接受服务的顾客中断服务，等待中断结束后继续服务。

假设服务中断在[t（0

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

假设第[i]个顾客位于受到中断影响的服务台，当：

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

表明第[i]个顾客在服务中断开始前便已进入服务台并且在服务中断发生之前并不能完成服务离开，此时第[i]个顾客会直接受到服务中断的影响。式中[state1，i+state3，i]表示第[i]个顾客进入服务台的时间。根据式（9）更新信息矩阵state第四行，加入服务中断的影响。

2.5  模拟系统的队长过程及服务过程

队长过程即每个时刻系统中的顾客数，包括在队列中等待的顾客数以及在服务台上正在接受服务的顾客数。通过对每个顾客的分析，得到每个顾客的到达、服务、等待、离开时间，将信息保存在信息矩阵state。对于时刻[t]，当顾客在时刻[t]之前到达，并且在时刻[t]之后才能离开系统，说明在[t]时刻该顾客在系统中，即：

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

式（11）成立时顾客[i]在[t]时刻处于系统中。

服务过程，即每个时刻已服务完成离开系统的顾客数。对于时刻[t]，当顾客在时刻[t]之前离开系统，说明在[t]时刻顾客已经离开系统，即：

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

式（12）成立时顾客[i]在[t]时刻已服务完成。

3  模拟仿真

假设系统初始为空，服务台的个数为[n]，到达率为[nλ（t）]，[λt=1+0.6×sin （x）]，根据到达率函数模拟出顾客的到达时间，服务时间服从指数分布，仿真时间为[0，T，T=16]。

首先定义外源性服务中断，由于模拟仍旧较小，所以取一个比较大的中断时间令模拟效果更明显。假设系统在[[7，12]]之间发生服务中断，发生中断时只有一半的服务台继续运行，当系统运行到时刻7时，系统发生服务中断，中断时间为5，中断服务台上的顾客的剩余服务在服务中断结束以后再继续进行，本文假设由serv_desk向量前一半元素所代表的服务台为中断时停止服务的服务台，下面对系统的运行队长和服务进行模拟仿真。

1） 取[n=10]，[μ1=μ2=1]，首先给出顾客到达过程，如图1所示。顾客带有服务中断和无服务中断的队长过程以及服务过程如图2，图3所示。

由图2，图3可以看出，当服务中断发生时，相较于没有服务中断影响的系统，队长会受到影响而变长，相同的时间内服务的顾客数减少，若考虑到顾客不耐烦，服务中断导致系统队列延长，顾客等待时间增加进而导致顾客流失的增加;同样，过长的队列会影响潜在顾客进入系统的欲望，若系统等待空间有限也会使得阻塞流失的顾客数增加，从而增大了系统的潜在损失。

2） 取[n=20]，[μ1=μ2=1]，顾客到达过程，如图4所示，顾客带有服务中断和无服务中断的队长过程及服务过程如图5，图6所示。

通过对比图2，图5可以看出，[n=20]时比[n=10]时服务中断对于系统队长过程的影响更大，图5中有服务中断影响的曲线偏离无服务中断曲线的程度更高，这也验证了文献[5]的研究，即系统规模越大对服务中断越敏感，服务中断造成的影响越大。

4  结  语

本文运用连续时间离散化的思想，设计了一种带有服务中断的多服务器系统的仿真算法，研究了带有服务中断的周期到达队列系统运行状况的模拟仿真，通过与理论算法比较证明是可行的。仿真算法的思想应用广泛，对顾客等待时间的分解处理与服务台向量的运用同样可以应用于其他任意的多服务台系统的模拟仿真，为多服务台排队模型的模拟仿真提供了一种可行而简便的算法思路，通过修改随机数产生方法和限制条件模型可以拓展到[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].现代电子技术，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].现代电子技术，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] 秦海林，刘建民.带优先权与不耐烦顾客排队模型的模拟仿真[J].现代电子技术，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] 熊光楞，肖田元，张燕立.连续系统仿真与离散事件系统仿真[M].北京：清华大学出版社，1999.

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