1.最简单流（泊松分布）
最简单流的一些性质： （1）参数λ代表单位时间内到达顾客的平均数 证 由于考虑单位时间，取t=1，其数学期望为： k k 1 e kPk (1) ke
k 0 k 0
k!
k 1
(k 1)!
（2）在[t,t+Δt] 没有顾客到达的概率为1-λΔt +o(Δt)
S3 S5
(d)单队多台串联
(e)多台混合
11.1.3 排队系统模型的分类
肯德尔（Kendall）于1953年提出了排队服务系统的分类记号 ： 输入/输出/并联的服务站数 1971年国际排队符号标准会上肯德尔将上述分类记号扩充到六项，记 为：输入/输出/并联的服务站数/系统容量（队长）/系统状态（顾客源数） /服务规则
t t 证 在 [t,t+Δt]内恰好有1个顾客到达的概率为 P ，将 e ( t ) e t 1 的麦克劳林级数代入，结论得证。
11.1.2 排队系统的三个特征
2．排队规则 排队规则指到达排队系统的顾客按怎样的规则排队等待。 （1）按顾客到达排队系统时发现服务设施已被占用是否离去可分为损失制， 等待制和混合制三种。当顾客到达时，所有的服务台均被占用，顾客随即 离去，称为损失制（或称即时制、消失制）；当顾客到达时，所有的服务 台均被占用，顾客就排队等待，直到接受完服务才离去，称为等待制，例 如出故障的机器排队等待维修就是这种情况；介于损失制和等待制之间的 是混合制。 对于等待制，有下列服务规则：先到先服务（FCFS） 、先到后服务 （LCFS） 、带优先服务权（PR） 、随机服务（SIRO）等。 在后面研究的问题中均假设采取FCFS服务规则。 （2）按队列长度是否有限，可分为队长有限和队长无限两种情况。在限度 以内就排队等待，超过一定限度就离去。 （3）按排队方式分为单列、多列。对于多列排队的顾客有的可以相互转移， 有的则不能（用栏杆等隔开）；有的排队顾客因等候时间过长而离开，有 的则不能（如在高速公路行驶的汽车必须坚持到高速出口）。我们所讨论 的问题限制在队列间不能相互转移，中途不能退出的情形。
11.1.4 排队系统的主要性能指标
求解排队问题的目的，是研究排队系统运行的效率，估计服务质量，确 定系统参数的最优值，以决定系统结构是否合理、研究设计改进措施等。 因此必须确定用以判断系统运行优劣的基本数量指标。 1．常用指标 （1）队长（Ls）和排队长（Lq）：队长指系统内顾客数，包括正在接 受服务的顾客与排队等待服务的顾客数（排队长），即 系统中的顾客数=排队等候服务的顾客数 + 正在接受服务的顾客数 （2）逗留时间（Ws）和等待时间（Wq）：逗留时间指顾客在排队服 务系统中从进入到服务完毕离去的平均逗留时间；等待时间指顾客排队 等待服务的平均等待时间。这对顾客来讲是最关心的，每个顾客希望逗 留时间或等待时间越短越好。 （3）服务机构工作强度：指服务机构累计的工作时间占全部时间的比 例，是衡量服务机构利用效率的指标。即： 服务机构 用于服务顾客的时间 服务设施总的空闲时间 1 工作强度 服务设施总的服务时间 服务设施总的服务时间
基本概念 系统、特征、分类、指标、输入输出
Kendall 标志：输入/输出/服务台数/队长/顾客源
单服务台排队系统 M/M/1/∞/∞：M/M/1/N/∞；M/M/1/∞/m 生死过程 (方法论) 多服务台排队系统 M/M/s/∞/∞：M/M/s/N/∞；M/M/s/∞/m 其他排队系统 M/G/1；M/D/1 系统运行指标 Ls,Lq,Ws,Wq
11.1.1 排队系统的一般表示
11.1.2 排队系统的三个特征
排除系统的三个特征是指：输入过程、排队规则、服务机构。 1．输入过程 输入是指顾客到达服务系统的情况。可能有下列情况，但并不相互排斥： （1）按顾客源总数划分为有限和无限两大类。如工厂需要检修的机器是有 限的，准备进京观光旅游的游客是无限的。 （2）按顾客到达的人数可以划分为单个到达和成批到达。如到超市购买商 品的顾客是单个的，到港国际航班等待安检的旅客是成批的。 （3）按顾客到达时间间隔是否固定可以划分为确定型和随机型。如定期运 行的班车、班轮、班机是确定的，到加油站加油的汽车是随机的。对随机 的顾客到达需要知道单位时间到达的顾客数或时间间隔的概率分布。 （4）按接受过服务的顾客对顾客到达数是否有影响，划分为相互独立到达 和非相互独立到达。如提供优质服务的餐饮业所产生了大量“回头客”， 就属于非相互独立到达。我们只讨论独立到达情况。 （5）按顾客相继到达间隔时间的分布及其数字特征是否与时间有关可分为 平稳与非平稳的。相继到达的间隔时间分布及其数学期望、方差等数字特 征都与时间无关，称为平稳的，否则是非平稳的。一般非平稳情况的数学 处理很困难，我们只讨论平稳状况。
导入案例：主任医师招聘问题
此类排队现象在日常生活中经常遇到，如客户到银行排队办理存贷款业 务，出纳员为客户提供服务；汽车到加油站排队，加注系统为汽车提供 加油服务；超市顾客到收银台前排队，收款员为顾客提供交款服务；旅 客到公交车站排队，公交车为旅客提供位移服务。 排队论的基本思想是1910年丹麦电话工程师A.K.埃尔朗在解决自动电 话设计问题时开始形成的，当时称为话务理论。他在热力学统计平衡理 论的启发下，成功地建立了电话统计平衡模型，并由此得到一组递推状 态方程，从而导出著名的埃尔朗电话损失率公式。 自20世纪初以来，电话系统的设计一直在应用这个公式。20世纪30年 代前苏联数学家欣钦把处于统计平衡的电话呼叫流称为最简单流；瑞典 数学家巴尔姆又引入有限后效流等概念和定义；美国数学家费勒 (W.Feller)关于生灭过程的研究；20世纪50年代初，英国数学家D.G.肯 德尔提出嵌入马尔可夫链理论，以及对排队队型的分类方法，为排队论 奠定了理论基础；20世纪70年代以来，人们开始研究排队网络和复杂 排队问题的渐近解等，成为研究现代排队论的新趋势。
第11章 排队论
重庆三峡学院 关文忠 /guanwenzhong
教学目标与要求
【教学目标】 1．理解下列基本概念：排队系统构成、特征、分类、主要性能指标及相互关系 2．掌握以下三种排队系统主要性能指标的计算：M/M/C/∞/∞；M/M/C/N/∞； M/M/C/∞/m。 3．了解M/G/1、M/D/1的主要指标计算公式 【知识结构】
11.1.2 排队系统的三个特征
3．服务机构 从机构形式和工作情况来看有以下几种： （1）服务机构可以没有服务员，也可以有一个或多个服务员 （服务台、窗口）。如超市的货架可以没有服务员，但交款时可 能有多个服务员。 （2）多个服务台的情况中，可以是平行排列的（并联），也可 以是前后排列的（串联），也可以是混合的。 （3）服务方式可以对单个顾客进行，也可成批进行。我们只讨 S1 S1 论单个服务情况。 S S2 S2 （4）服务时间可分为确定型的和随机型的。如旅客列车对乘客 S3 S3 的服务是按列车时刻表进行位移服务的，是确定型的；因患者病 (a)单台单队 (b)多队多台并联 (c)单队多台并联 情不同，医生诊断的时间不是确定的，是随机型的。 S1 S4 （5）服务时间的分布总假定是平稳的，即分布的期望值、方差 S1 S2 S2 等参数不受时间的影响。
本章主要内容
11.1 基本概念 11.1.1 排队系统的一般表示 11.1.2 排队系统的三个特征 11.1.3 排队系统模型的分类 11.1.4 排队系统的主要性能指标 11.1.5 排队系统的输入和输出 11.2 生死过程 11.3 单服务台排队系统模型 11.3.1 M/M/1/∞/∞（标准系统） 11.3.2 M/M/1/N/∞（系统容量有限） 11.3.3 M/M/1/∞/m（顾客源有限） 11.4 多服务台排队系统模型 11.4.1 M/M/s/∞/∞系统 11.4.2 M/M/s/N/∞系统 11.4.3 M/M/s/∞/m系统
模型的优化（目的）
导入案例：主任医师招聘问题
某三甲医院肝胆内科有主任医师1名，由于他的存在而使前来诊疗的患 者大增。根据一个月的统计，平均每h到达医院的患者6名，并对各时 间段统计，经回归符合泊松分布；该医生每h可诊疗4名，但患者病情 不同，分布也不是均匀的，对每位患者就诊时间的统计，经回归，符合 指数分布。 医院配备有电子回馈信息系统，及时观察到已挂号排队等候的患者数量。 当排队等候人数少于5人时，挂号系统可以挂号。当前来就诊的患者挂 上号若医生空闲则可直接就诊，否则排队等候。医生采取先到先服务的 规则。若前来就诊的患者挂不上号，则立即到邻近的一家医院就诊。 经统计，经该主任医师诊疗的患者，其诊疗费、检验费、医药费等医院 可获纯收入100元；主任医师可高薪聘请，其薪金及住房和各种福利年 均25万元，医院实行每周5天工作制，年工作日250天，平均每天支付 1000元的成本。当医生过少，由于患者得不到服务离去而产生的损失 增加；当医生过多，由于医生空闲时间的增加也使医院的成本增加。问： 医院应招聘多少名肝胆内科主任医师可使得盈利最大？
1.最简单流（泊松分布）
最简单流需要满足以下三个条件： （1）平稳性 指在一定时间间隔内，来到服务系统有k个顾客的概 率仅与这段时间间隔的长短有关，而与这段时间的起始时刻无关； （2）无后效性 指在不相交的时间区间内到达的顾客数是相互独 立的，或者说在区间[a, a+t]来到k个顾客的概率与时间a之前来到 多少个顾客无关； （3）普通性 指在足够小的时间区间内只能有一个顾客到达，不 可能有两个以上顾客同时到达。
11.5 其他排队系统模型 11.5.1 一般服务时间M/G/1模型 11.5.2 定长服务时间M/D/1模型 11.5.3 埃尔朗服务时间M/Ek/1 模型 11.5.3 具有优先服务权的排队 模型 11.6 排队系统的优化 11.6.1 M/M/1模型中的最优服务 率 11.6.2 M/M/s模型中的最优服务 台数 本章小结
Ls Ws , 或Ws Ls

Lq Wq ,
Ws Wq Βιβλιοθήκη 或Wq Lq