3.3　排队服务系统的数学建模

排队是在日常生活中经常遇到的现象，如顾客到商店购买物品、病人到医院看病常常要排队。如果要求服务的数量超过服务机构（服务台、服务员等）的容量，也就是说，到达的顾客不能立即得到服务，就出现了排队现象。这种现象不仅仅在个人日常生活中出现，电话局的占线问题，车站、码头等交通枢纽的车船堵塞和疏导，故障机器的停机待修，水库的存储调节等都是有形或无形的排队现象。由于顾客到达和服务时间的随机性，可以说排队现象几乎是不可避免的。

排队论起源于1909年丹麦电话工程师A．K.爱尔朗的工作，他对电话通话拥挤问题进行了研究。1917年，爱尔朗发表了他的著名文章“自动电话交换中的概率理论的几个问题的解决”。目前，排队论已广泛应用于军事、运输、维修、生产、服务、库存、医疗卫生、教育、水利灌溉等，显示了其强大的生命力。

3.3.1　基本要素

排队服务系统有到达、排队等候处理（服务）、离去三个环节，描述排队服务系统模型的基本要素包括到达模式、排队规则、服务规则。排对服务系统的组成及其基本要素如图3.8所示。

1．到达模式

到达模式即描述顾客来源及顾客是按怎样的规律抵达排队系统。到达模式又称为系统输入过程，以随机到达时间表示。常见的到达模式有定长分布、泊松分布、爱尔朗分布、指数分布及超指数分布等。需要从三个方面来描述一个到达过程：

（1）顾客源总体：顾客的来源可能是有限的，也可能是无限的。

（2）到达的类型：顾客是单个到达，还是成批到达。

（3）顾客相继到达的间隔时间：按照顾客随机到达时间间隔可以分为确定型和随机型。通常假定时间间隔是相互独立、同分布的，有的是等距间隔时间，有的服从泊松分布，有的服从k阶爱尔朗分布。

2．排队规则

排队规则是指服务是否允许排队，顾客是否愿意排队。由于顾客到达和服务时间的随机性而产生了多种排队规则。常见的排队规则有以下几种情况：

1）损失制（Lossing system）

当顾客到达服务机构时，如果所有服务机构都正在被使用，那么他将自动离开，并且永远不再回来（这个只是为了我们在进行数学处理时比较方便才做出的一种假定，是对实际问题的一种近似处理）。

2）等待制（Waiting system）

当顾客到达服务机构时，如果所有服务机构都正在被使用，那么他就加入排队等待的队列，等待接受服务。服务员在选取顾客进行服务时，所需要遵守的服务规则有下面几种：

（1）先到先服务规则。这是指按照顾客到达服务系统的先后次序服务。这也是一种最普遍的服务规则。

（2）后到先服务规则。这是指后到达服务系统的顾客要首先接受服务。这种服务规则在许多库存系统中都是比较常见的。另外，在情报系统中，越是后来的信息，往往就越重要，所以就更应该先处理，也就是首先进行服务处理。

（3）随机服务规则。这是指在一个服务结束的时候，服务系统从等待的顾客中随机地选取一个出来进行服务。

（4）优先权服务规则。在这种规则下，进入服务系统的顾客本身具有不同等级的优先权（优先权取决于重要程度或者花钱购买等方式），在选择服务对象的时候，不去管顾客到达的先后次序，而是具有较高等级优先权的顾客要优先于优先权等级较低的顾客接受服务。这种优先权的等级可以有许多种。如果在一个服务系统中，同时存在多于一个的具有相同等级优先权的顾客的时候，相应的服务规则也必须要进行规定，而这个就可以是上述几种规则中的任何一种。例如，计算机中通信网络的优先级，交通管理中的专车、警车、救火车，医务就诊中的急诊，电话交换中的火警、匪警、战备通信等都享有优先权服务。

优先权规则又分为两种类型。第一种类型是强拆型。也就是说，如果当刚刚到达的顾客的优先权等级高于正在接受服务的顾客的优先权等级，那么就立即终止正在进行的服务，系统直接服务这个具有较高优先权等级的新顾客；只有在具有较高优先权等级的顾客服务完成，并且系统中也不存在其他较高优先权等级的顾客时，才会再次让被强拆的顾客接受服务。第二种类型是无强拆型。也就是在有较高优先权等级的顾客出现时，如果优先权等级较低的顾客正在接受服务，那么，就等服务结束之后，才从等待的顾客之中选择出优先权等级最高的顾客进行服务。

（5）几个服务机构的情形。顾客在接受服务的过程中，需要经过多个服务机构，同时，可以有多种排队规则。

（6）循环排队。这是指每个顾客在服务台接受服务后，经过一段时间又要求服务的情况。

3）混合制（损失制与等待制的混合）

（1）队长有限。在一个等待空间有限制的条件下，在该服务系统之中，最多只能够允许k个顾客。当顾客到达的时候，如果队长小于k个，那么他就进入该队列；如果队长等于k个，那么该顾客就选择离开，并且以后不会再回来。

（2）等待时间有限制。该种情况是指顾客在一个系统中等待的时间不能够超出限定的一个时间t。如果等待时间超过了t，那么，该顾客就会选择自动离开，并且永远不会再回来。

（3）逗留时间（等待时间与服务时间之和）是有限制的。该情形下要求顾客在一个系统中的逗留时间不能够超出已经事先给定的一个时间to。如果超过这个时间to，那么，该顾客就会选择离开。

需要特别说明的一点是，损失制与等待制可以被看成混合制的一种特殊形式。当k=C（C为系统中的服务台的个数）时，混合制就变为了损失制；当k>C时，混合制就变为了等待制。

3．服务规则

服务规则是指可提供特定类型服务的一定数量的服务员及服务员之间的配置形式。系统可以一个窗口或多个窗口为顾客进行服务，并且各窗口的服务时间可以是确定型或随机型，通常有单队列-单服务台排队系统、单队列-多服务台并联排队系统等。

服务过程是指对各个顾客服务所需时间形成的服务过程。它描述了服务过程的统计特性，同样具有一定的分布特性。通常有如下分布：

（1）定长分布服务时间：所有顾客服务时间均为常数，以D表示。

（2）负指数分布服务时间：每个顾客服务时间彼此独立，具有相同负指数分布，其均值为平均服务时间，以M表示。

（3）爱尔朗分布服务时间：如果顾客的服务必须经过k个串联服务台，每个服务台的服务时间彼此相互独立，且均服从均值为的负指数分布，则该顾客的总服务时间为。显然，它服从于均值为、方差为的爱尔朗分布，以表示。

（4）一般随机分布服务时间：每个顾客的服务时间相互独立，具有相同分布的非负随机变量，对分布函数的分布形式做进一步假设，以表示。

（5）其他分布服务时间：如各服务员可具有不同的服务时间分布、服务时间分布依赖队长等。

3.3.2　符号表示

根据到达模式、排队规则和服务规则的变化对排队模型进行描述或分类，可给出很多排队模型。为了方便对众多模型的描述，20世纪50年代初，D.G.Kendall提出了一种目前在排队论中普遍使用的“Kendall记号”，其一般形式为

其中，X表示顾客相继到达时间间隔的分布；Y表示服务时间的分布；Z表示并联服务台的个数；A表示系统的容量，即可容纳的最多顾客数；B表示顾客源的数目；C表示服务规则。各种到达模式和服务时间分布的符号为：M—负指数分布；D—确定型分布（定长分布）；Ek—k阶爱尔朗分布；GI—一般相互独立随机分布；G—一般随机分布。例如，表示一个顾客的到达时间间隔服从相同的负指数分布、服务时间为负指数分布、单个服务台、系统容量为无限、顾客源无限、排队规则为先来先服务的排队模型。一般约定如下：如果Kendall记号中略去后三项，即表示为，则表示一个顾客相继到达时间间隔服从相同的负指数分布、服务时间为负指数分布、1个服务台的排队模型。

3.3.3　数学建模方法

排队服务系统常用的数学建模方法有两种，即一般描述法和仿真语言描述法。一般描述法是排队服务系统建模的根本方法，其实质是对系统的基本要素进行如下具体数学描述：

1．到达模式的数学模型

到达模式的数学模型借助相互到达时间来描述。所谓相互到达时间是指相邻两个实体到达服务机构的先后间隔时间。若时间是恒定的，则时间间隔为常数；若到达是随机的，则采用概率函数来描述。此概率函数有两种：①到达分布函数—到达时间间隔大于给定时间的概率；②累积分布函数—到达时间间隔小于给定时间的概率。这里，，且，随着t的增大，将减小。

常见到达分布函数及数学描述如下：

（1）定长到达分布：实体在等距离时间间隔到达。其数学表达式为

（2）泊松到达分布：实体在给定时间长度为t的时间内发生有n个到达的概率。泊松分布是排队服务系统中典型的到达分布，其数学表达式为

（3）指数到达分布：是一种有普遍实用意义的到达分布，其累积函数为

若随机数y均匀分布，上式可简化为，式中为平均相互到达时间。

（4）爱尔朗到达分布：这种到达分布常用于电话和通信交换系统中，其密度函数是

到达分布函数为。

（5）超指数到达分布：这是方差大于均值的一类分布。其主要特点是数据更频繁地出现低值和高值。一般来讲，当变异系数大于1时，该数据即可用超指数分布拟合。它的分布函数为

其方差为；变异系数为。其中，。

（6）一般独立随机到达分布：这类分布的特点是到达时间间隔互相独立，分布函数A(t)是任意随机分布的。

2．服务过程的数学描述

服务过程以时间表示，通常考虑为常数。若作随机变量考虑时，需要用概率来描述。

在实际排队服务系统中，服务时间有如下规律：

（1）若服务时间是随机的，则可以用上述指数分布表示。

（2）若求得变异系数与1差别很大，则服务时间可用爱尔朗分布或超指数分布描述。

（3）最普遍的随机服务时间为正态分布，其密度函数为

3．排队规则的数学描述

该描述即排队服务系统的等待体制，主要有以下四种：

（1）先入先出规则：这是一种常规服务方式，在这种方式下，服务将首先提供给等待时间最长的一个顾客。

（2）后到先出规则：这种规则犹如计算机控制中的堆栈概念，在这种方式下，服务将首先提供给最后一个到达的顾客。

（3）随机规则：在提供服务时间内，对所有等待顾客均进行随机选择服务。在这种方式下，被选择者具有均等被服务的机会，且服从正态分布。

（4）优先服务规则：一种常见的规则。

综上所述，排队服务系统的数学建模关键在于利用大量观测数据获得概率分布函数，并借助该函数正确地描述到达模型和服务过程。除一般描述法建模外，还有仿真语言描述法。在面向结构的仿真语言中，排队是由语言实现程序自动处理完成统计运算的。

3.3.4　防空导弹武器系统的排队论建模案例

为了提高突防和打击能力，现代空袭兵力、兵器主要采用多目标、多群、多方向、多波次、多类型的密集攻击。而我方防空火力主要由若干个火力单元组成，一个火力单元只包含一个火力通道，每个火力通道可以在同一时间内以单射和齐射等发射方式对一个目标进行射击。火力单元部署符合最优化原则，如果目标被击毁，分配给该目标的火力单元立刻转向其他目标；如果目标未被击毁，火力单元则继续向该目标射击，直到该目标被击毁或飞离火力单元的火力杀伤区为止。火力单元构成一定纵深和宽度的杀伤区。根据目标飞行高度的不同、目标航路捷径不同，导弹与目标在杀伤区内的遭遇点坐标不同，以及受一些随机因素的影响，火力单元的射击时间也不同。由于目标飞行方向的差别，以及受一些随机因素的影响，目标在杀伤区内逗留的时间也不同。

根据顾客（空袭目标）到达情况、服务系统（火力单元）的服务能力、顾客的耐心程度与排队情况（目标在杀伤区内逗留时间分布），做如下假设：

（1）每个编队有目标m个，各编队按照参数为的泊松分布随机地进入武器系统的杀伤区内，即在t时刻内有k个空袭编队进入武器系统火力杀伤区事件出现的概率为

式中，t为火力单元对一个目标射击所用的随机时间。

（2）对一个目标的射击时间服从参数为的负指数分布，即

式中，为单个目标在杀伤区内逗留的随机时间。

（3）由于在实际过程中目标在杀伤区上空的飞行时间很短，因此可以将系统视为无等待系统（消失制系统）。

根据基本假设可知，有n个火力单元的防空系统可能出现的状态有：

（1），所有n个火力单元都不射击。

（2），n个火力单元中有k（k=1,2,…,n-1）个正在射击。

（3），所有n个火力单元都在射击。

利用排队论状态分析过程：

（1）过程中，状态的转移仅限于从一个状态向其临近状态转移。

（2）如果在t时刻过程处于k状态，则在（t,t+）内由k状态转移到k+1状态的概率为，由k状态转移到（k-1）状态的概率为，其中、为t的函数。

（3）在（t,t+）内转移两个或两个以上状态的概率为o(t)，可忽略不计。

状态N(t)=0为下列两个互不相容的事件之和：

（1）在时刻t所有n个武器都不射击，而在时间间隔内未出现任何目标群。

（2）在时刻t有一个武器在射击，而在时间间隔内，此武器射击完毕，这时未出现新的目标群，因此可得

式中，为目标群的空袭密度；、为防空武器对一个目标的平均射击时间。

状态N(t)=k(0<k<m)为下列两个互不相容的事件之和：

（1）在时刻t防空系统处于状态N(t)=k，而在时间间隔内已开火的武器仍然继续射击，这时未出现新的目标群。

（2）在时刻t防空系统处于状态N(t)=k+1，而在时间间隔内未出现新的目标群，这时有一个武器结束了对原来目标的射击。因此可得

当时，还应增添一个事件，即

状态为下列两个互不相容的事件之和：

（1）在时刻t防空系统处于状态N(t)=n，而在时间间隔内，所有n个武器都未结束射击。

（2）在时刻t防空系统处于状态N(t)=n-m，或N(t)=n-m+1,…，或N(t)=n-1，而在时间间隔内已开火的武器都未结束射击，这时，出现一个新的目标群（由m枚导弹组成），因此可得

于是可得最后的代数方程组：

式中，，显然有。将式（3.40）的解写成，则有 ，从而可得

可以根据式（3.40）递推公式求得。

根据以上公式的推导，被导弹击毁的概率为

式中，为目标受到拦截的概率，即所有火力单元都被占用的概率为；为目标火力抗击下单发导弹毁伤的概率。