运筹学第10讲 排队论

1、作为排队系统（随机服务系统）的数学理论和方法，是作为排队系统（随机服务系统）的数学理论和方法，是运筹学的一个重要分支运筹学的一个重要分支。 排队是日常生活中经常遇到的现象，如进餐馆就餐、图排队是日常生活中经常遇到的现象，如进餐馆就餐、图书馆借书、在车站候车、售票处购票等等。排队问题的表现形式往往是拥挤现象，书馆借书、在车站候车、售票处购票等等。排队问题的表现形式往往是拥挤现象，随着生产与服务的日益社会化，由排队引起的拥挤现象会越来越普遍随着生产与服务的日益社会化，由排队引起的拥挤现象会越来越普遍。下面。下面我们列我们列举出部分形形色色的排队举出部分形形色色的排队系统。系统。达到的顾客达到的顾客

2、要求服务的内容要求服务的内容服务的机构服务的机构出故障的机器出故障的机器修理技工修理技工病人病人电话呼叫电话呼叫进港货船进港货船入水库河水入水库河水达到机场上空的飞机达到机场上空的飞机刑事案件刑事案件达到路口的车辆达到路口的车辆来犯敌机来犯敌机修理修理领取修配零件领取修配零件诊断（或治疗）诊断（或治疗）通话通话装（卸）货装（卸）货放水、调整水位放水、调整水位降落降落侦破侦破通过路口通过路口截击截击修理技工修理技工发放发放修配零件修配零件的管理员的管理员医生（或治疗设备）医生（或治疗设备）交换台交换台装（卸）货码头（泊位）装（卸）货码头（泊位）水闸、管理员水闸、管理员跑道跑道刑侦部门刑侦部门交通

3、信号灯交通信号灯我防空部队我防空部队排队排队可以是有形的队列，也可以是无形的队列。排队可以是人，也可以是物。可以是有形的队列，也可以是无形的队列。排队可以是人，也可以是物。 顾客源顾客源排队结构排队结构服服务务机机构构顾客到来顾客到来排队规则排队规则服务规则服务规则顾客离去顾客离去1单队单队 单服务台系统单服务台系统1单队单队多服务台（并联）系统多服务台（并联）系统2S.1S单队单队多服务台（串联）系统多服务台（串联）系统1多队多队多服务台（并联）系统多服务台（并联）系统.2S多队多队多服务台（混联、网络）系统多服务台（混联、网络）系统说明说明顾客按怎样的规律达到系统，通常从顾客按怎样的规律达

4、到系统，通常从 3 个方面刻画个方面刻画：n 顾客顾客总体（顾客源）总体（顾客源）数数n 达到方式达到方式n 顾客顾客相继达到的时间间隔分布相继达到的时间间隔分布。二二、排队及、排队及排队规则排队规则排队排队n 损失损失制制排队排队n 等待等待制制排队排队n 混合混合制制排队排队排队规则排队规则n 先到先服务先到先服务FCFSn 后到先服务后到先服务LCFSn 有有优先权服务优先权服务PSn 随机随机服务服务RF三三、服务、服务机制机制说明说明顾客按怎样的规律接受服务，通常从顾客按怎样的规律接受服务，通常从 3 个方面刻画：个方面刻画：n 服务员服务员的数量及其连接形式（并联或串联的数量及其连

5、接形式（并联或串联）n 顾客顾客接受服务的方式（单个或成批接受服务的方式（单个或成批）n 服务时间分布服务时间分布其中其中服务时间分布是最重要因素，其常见的分布有服务时间分布是最重要因素，其常见的分布有：n 定定长分布（长分布（D）n 负负指数分布（指数分布（M）n k 阶爱尔朗分布（阶爱尔朗分布（Ek）一般一般形式：形式： X / Y / Z / A / B / C X 顾客相继达到时间间隔的顾客相继达到时间间隔的概率分布概率分布 Y 服务时间的服务时间的概率分布概率分布 Z 服务台的服务台的个数个数 A 服务机构的容量（容纳所有顾客的数量服务机构的容量（容纳所有顾客的数量） B 顾客源的容

6、量顾客源的容量 C 排队规则排队规则衡量衡量一个排队系统的好坏以及对一个排队系统作经济分析，需要一系列描述排队系一个排队系统的好坏以及对一个排队系统作经济分析，需要一系列描述排队系统特征的数量指标，主要的数量指标通常有：统特征的数量指标，主要的数量指标通常有：n Ls：系统：系统中中顾客数顾客数的期望（平均）值。的期望（平均）值。n Lq：系统：系统中中排队顾客数排队顾客数的期望（平均）值。的期望（平均）值。n Ws：顾客：顾客在系统中在系统中逗留时间逗留时间的期望（平均）值。的期望（平均）值。n Wq：顾客：顾客在系统中在系统中排队等待时间排队等待时间的期望（平均）值。的期望（平均）值。n

7、Pl：系统：系统损失概率（系统满容量的概率）。损失概率（系统满容量的概率）。n A：占用：占用服务台的平均数。服务台的平均数。n ：服务台服务台的利用率。的利用率。研究研究主要数量指标在瞬时或平稳状态下的概率分布及其数字特征，主要数量指标在瞬时或平稳状态下的概率分布及其数字特征，了解系统的基本运行特征。了解系统的基本运行特征。检验检验系统是否达到平稳状态；检验顾客达到间隔的独立性；确定服系统是否达到平稳状态；检验顾客达到间隔的独立性；确定服务时间分布及参数。务时间分布及参数。：系统：系统的最优设计和最优运营问题。的最优设计和最优运营问题。一类一类重要且广泛存在的排队系统是重要且广泛存在的排队系

8、统是生灭过程生灭过程排队系统。排队系统。生灭过程生灭过程是一类特殊的随机是一类特殊的随机过程。在排队论中，过程。在排队论中，“生生”表示顾客的达到，表示顾客的达到，“灭灭”表示顾客的离去。表示顾客的离去。定义：定义：设设N（t），），t 0 是一个随机过程（其中是一个随机过程（其中N（t）表示时刻）表示时刻 t 系统中的顾系统中的顾客数）。若的概率分布具有如下性质：客数）。若的概率分布具有如下性质：n 假设假设N（t） = n ，则从时刻，则从时刻 t 起到下一个顾客起到下一个顾客达到达到时刻止的时间服从参数为时刻止的时间服从参数为 n 的负指数的负指数分布，分布，n = 0，1，2，。n 假

9、设假设N（t） = n ，则从时刻，则从时刻 t 起到下一个顾客起到下一个顾客离去离去时刻止的时间服从参数为时刻止的时间服从参数为 n 的负指数的负指数分布，分布，n = 0，1，2，。n 同一时刻只有一个顾客同一时刻只有一个顾客达到达到或或离去离去。则称则称N（t），），t 0 是一个生灭过程。是一个生灭过程。 N n+1 n n-1 n N-1 0 1 01n-1nn+1NN-1有限状态有限状态生灭过程：生灭过程：p0p1pn-1pnpn+1pN-1pN稳态方程组：稳态方程组： 0 p0 - 1 p1 = 0 ( n = 0 ) N-1 pN-1 - N pN = 0 ( n = N )(

10、 n-1 pn-1 + n+1 pn+1 ) ( n pn + n pn ) = 0 ( 1 n N-1 ) n n-1 n 0 1 01n-1nn+1N n+1p0p1pn-1pnpn+1pN稳态方程组：稳态方程组： 0 p0 - 1 p1 = 0 ( j = 0 ) ( n-1 pn-1 + n+1 pn+1 ) ( n pn + n pn ) = 0 ( j 1 )无限状态无限状态生灭过程：生灭过程：排队论排队论 Queuing Theory（QT）生灭过程简介生灭过程简介无限状态无限状态生灭过程的解生灭过程的解 记记 Cn = n-1 n-2 1 0 n n-1 2 1 n = 1，2

11、，则平稳状态时则平稳状态时生灭过程的解为：生灭过程的解为： Pn = CnP0 n = 1，2，其中其中 P0 = 11 + Cn n=1注意！无穷级数注意！无穷级数Cn 收敛时上式方有意义，这点可由系统进入平收敛时上式方有意义，这点可由系统进入平稳状态得到保证。稳状态得到保证。排队论排队论 Queuing Theory（QT）Poisson 过程和负指数分布过程和负指数分布Poisson 过程过程 Poisson 过程（又称为过程（又称为 Poisson 流、最简流）是排队论中最为常流、最简流）是排队论中最为常见的一种描述顾客达到规律的特殊随机过程。见的一种描述顾客达到规律的特殊随机过程。定

12、义：设定义：设 N（t）为时间）为时间 0，t 内达到系统的顾客数，如果满足下内达到系统的顾客数，如果满足下面三个条件：面三个条件：1.平稳性：在平稳性：在 t ， t + t 内有一个内有一个顾客达到的概率为顾客达到的概率为 t + ( t ) ；2.独立性：在任意两个不相交时间区间独立性：在任意两个不相交时间区间内内顾客达到相互独立；顾客达到相互独立；3.普通性：在普通性：在 t ， t + t 内多于一个内多于一个顾客达到的概率为顾客达到的概率为 ( t ) 。则称则称 N（t），），t 0 为为Poisson 过程。过程。排队论排队论 Queuing Theory（QT）Poisson

13、 过程和负指数分布过程和负指数分布Poisson 过程与负指数分布过程与负指数分布定理定理1 设设 N（t）为时间）为时间 0，t 内达到系统的顾客数，则内达到系统的顾客数，则N（t），t 0 为为Poisson 过程的充要条件是：过程的充要条件是： PN（t）= n = （ t ）n / n！ e- t n = 1，2，定理定理2 设设 N（t）为时间）为时间 0，t 内达到系统的顾客数，则内达到系统的顾客数，则N（t），t 0 为参数为为参数为 的的Poisson 过程的充要条件是：过程的充要条件是： 相继达到时间间隔服从相互独立的相继达到时间间隔服从相互独立的参数为参数为 的负指数分布。

14、的负指数分布。上述定理阐述了上述定理阐述了Poisson 过程与过程与负指数分布的等价性。负指数分布的等价性。排队论排队论 Queuing Theory（QT）常见常见排队系统排队系统生灭过程生灭过程排队系统排队系统 M / M / n / n 损失制损失制排队系统排队系统 M / M / n / 等待制等待制排队系统排队系统 M / M / n / N 混合制混合制排队系统排队系统 M / M / n / N 顾客源有限顾客源有限排队系统排队系统排队论排队论 Queuing Theory（QT）常见常见排队系统排队系统单服务台模型单服务台模型M / M / 1 （M / M / 1 / ）

15、01n-1nn+1N p0p1pn-1pnpn+1pN解为：解为： P0 = 1- ， （ = / ） Pn =（1- ） n ， （n 1 ）排队论排队论 Queuing Theory（QT）常见常见排队系统排队系统M / M / 1 （M / M / 1 / ）主要系统指标主要系统指标1.Ls = /（ 1- ）= /（ - ） 其中其中 0 12.Lq = Ls - = 2 /（ 1- ）3.Ws = Ls / = 1 /（ - ） 4.Wq = Lq / = Ws - 1 / = /（ - ） 排队论排队论 Queuing Theory（QT）常见常见排队系统排队系统多服务台模型多服务

16、台模型M / M / s （M / M / s / ）s 01s-1ss+1Ns p0p1ps-1psps+1pN解为：解为：排队论排队论 Queuing Theory（QT）常见常见排队系统排队系统多服务台系统与单多服务台系统的比较多服务台系统与单多服务台系统的比较一个一个M / M / 3 与三个与三个M / M / 1 的比较的比较 台台1 台台2 台台3 台台1 台台2 台台3 一个一个M / M / 3三个三个M / M / 1 从这两个系统的主要指标比较可以看出混合排队比独立排队具有显著的优越性，这一点从这两个系统的主要指标比较可以看出混合排队比独立排队具有显著的优越性，这一点是在

17、排队系统的排队方式的设计时应该注意的。是在排队系统的排队方式的设计时应该注意的。排队论排队论 Queuing Theory（QT）常见常见排队系统排队系统非生灭过程非生灭过程排队系统排队系统 一个排队系统的特征是由输入过程、服务机制和排队规则三大一个排队系统的特征是由输入过程、服务机制和排队规则三大要素决定的。前面所讨论的排队模型要素决定的。前面所讨论的排队模型 “M / M /” 型的，这类排队系型的，这类排队系统的一个主要特征是马尔可夫性，而马尔可夫性的一个主要性质是统的一个主要特征是马尔可夫性，而马尔可夫性的一个主要性质是由系统当前的状态可以推断未来的状态。但是，当系统不是由系统当前的状

18、态可以推断未来的状态。但是，当系统不是“M/M/”型时，仅仅知道系统内当前的顾客数，对于推断系统未来型时，仅仅知道系统内当前的顾客数，对于推断系统未来的状态是不充足的，因为正在接受服务的顾客，已经被服务了多长的状态是不充足的，因为正在接受服务的顾客，已经被服务了多长时间，将影响其离开系统的时间。因此，须引入新的方法来分析具时间，将影响其离开系统的时间。因此，须引入新的方法来分析具有有非非负指数分布的排队系统。负指数分布的排队系统。 一般而言，具有一般而言，具有非非负指数分布的排队系统的分析是非常困难的负指数分布的排队系统的分析是非常困难的。排队论排队论 Queuing Theory（QT）常见

19、常见排队系统排队系统非生灭过程非生灭过程排队系统排队系统一般服务时间模型一般服务时间模型 M / G / 1 模型模型 M / G / 1 系统是顾客达到为系统是顾客达到为Poisson流，单服务台，服务时间为流，单服务台，服务时间为一般分布的排队系统。一般分布的排队系统。设：设： 顾客的平均达到率；顾客的平均达到率； T 服务时间；服务时间； E T 平均服务时间；平均服务时间； 2 Var T 方差；方差； E T ，为使系统达到稳态，必须有，为使系统达到稳态，必须有 1。 当时，系统可以达到平稳状态，而要给出平稳分布的显示是比当时，系统可以达到平稳状态，而要给出平稳分布的显示是比较困难的

20、。已有的几个结果是：较困难的。已有的几个结果是：排队论排队论 Queuing Theory（QT）常见常见排队系统排队系统非生灭过程非生灭过程排队系统排队系统波拉切克（波拉切克（Pollaczek） 欣钦（欣钦（Khintchine）公式）公式 （P- K）公式：）公式：Lq = 2 + 2 2 2（1- ）此外有：此外有： Ls = Lq + Ws = Ls / Wq = Lq / 排队论排队论 Queuing Theory（QT）常见常见排队系统排队系统非生灭过程非生灭过程排队系统排队系统波拉切克（波拉切克（Pollaczek） 欣钦（欣钦（Khintchine）公式）公式 由以上的（由以

21、上的（P K）公式可以看出）公式可以看出 Ls、Lq、Ws、Wq 等排队系等排队系统的重要指标仅仅依赖于统的重要指标仅仅依赖于 和服务时间的方差和服务时间的方差 2 ，而与分布的类型，而与分布的类型无关，这是排队论中一个无关，这是排队论中一个非常重要而又令人惊奇的结果！非常重要而又令人惊奇的结果！ 从（从（P K）公式不难看出，当公式不难看出，当 确定后，当方差确定后，当方差 2 减少时，减少时，平均队长和等待时间都将减少。因此，可通过服务时间的平均队长和等待时间都将减少。因此，可通过服务时间的方差来缩方差来缩短短平均队长，当且仅当平均队长，当且仅当 2 = 0 ，即服务时间为定长时，平均队长

22、和，即服务时间为定长时，平均队长和等待时间可减少到最少水平，这一点是符号直观的，因为服务时间等待时间可减少到最少水平，这一点是符号直观的，因为服务时间越有规律，等待的时间也就越短。越有规律，等待的时间也就越短。排队论排队论 Queuing Theory（QT）排队系统的优化排队系统的优化排队系统的最优化设计排队系统的最优化设计1、 以最少的以最少的“设备设备”获得最大的效益，或者说，在一定的服务质获得最大的效益，或者说，在一定的服务质量指标下要求服务机构最为经济。量指标下要求服务机构最为经济。2、 给出排队系统的某种费用结构，要求总费用最优的情况下对系给出排队系统的某种费用结构，要求总费用最优的情况下对系统的服务率统的服务率 、服务台数服务台数n、系统容量、系统容量N、以及排队规则等等进行设、以及排队规则等等进行