运筹学讲义 §11排队论 本章来介绍排队论( queuing theory). 1909年,丹麦哥本哈根电话公司的A.K. Erlang对电话拥挤现象进行了研究,并发表了《概率 与电话通话理论》( Probability and Theory of Telephone),开创了排队论的研究 排队论,亦称随机服务系统理论或等待线理论,是研究因随机因素的影响而产生的排队现象,以 便对随机服务系统进行最优设计和控制的理论 关于排队,队列可能是有形的,如在火车站售票处买票,也可能是无形的,如电话订票;顾客可 能是人,如在银行等待取款的顾客,也可能是物,如等待进港的船只:服务台可能是人,如售票员 也可能是物,如机场跑道:顾客数可能有限,如等待买票的人,也可能无限,如泄洪问题中的上游来 随机服务系统又称为排队系统. 排队系统的描述:顾客到达服务台是随机的顾客到达服务台时,若服务台空闲,则立刻接受服 务:否则,顾客应等待至服务台空闲时,再接受服务.顾客接受服务后即离开服务台. 排队系统的三要素: (1)输入过程:指顾客到达的规律,如顾客数(有限或无限),顾客到达的方式(批量或单个), 相继到达的顾客之间的时间间隔的分布 (2)排队规则:包括服务台是否允许排队,顾客的排队意愿,服务顺序(先到先服务,后到先 服务,随机服务,优先权服务)等 (3)服务机制:服务台的数目,多服务台服务时的连结方式(串连或并连),服务时间的分布 平稳状态:正常的,稳定的运行状态.如当储蓄所早上开门时,顾客很少,是为过渡期:此后, 业务活动渐渐进入平稳状态 显然,当排队系统处于平稳状态时,任意时刻时的顾客的数目的变化率(导数)等于0 排队论的研究对象是平稳状态时的排队系统 1953年,D.G. Kendall引入了排队系统的符号模型: 顾客到达的时间间隔的分布/服务时间的分布/服务台的数目/排队系统允许的最大顾客容量 如排队模型M/M/1/∞,其中M表示顾客到达的时间间隔相互独立,且都服从指数分布,M 表示服务台对顾客的服务时间相互独立,且都服从指数分布,1为服务台的数目,∞表示排队系统允 许的最大顾客数无限制 排队系统的主要数量指标 (1)平均排队队长:排队等待的平均顾客数Lq (2)平均队长:平均顾客数L 显然,L=Lq+正在接受服务的顾客数如对排队模型M/M/1/∞,有L=Lq+1 (3)平均排队时间:顾客排队等待接受服务的平均时间W。运 筹 学 讲 义 1 §11 排队论 本章来介绍排队论（queuing theory）. 1909 年，丹麦哥本哈根电话公司的 A. K. Erlang 对电话拥挤现象进行了研究，并发表了《概率 与电话通话理论》（Probability and Theory of Telephone），开创了排队论的研究. 排队论，亦称随机服务系统理论或等待线理论，是研究因随机因素的影响而产生的排队现象，以 便对随机服务系统进行最优设计和控制的理论. 关于排队，队列可能是有形的，如在火车站售票处买票，也可能是无形的，如电话订票；顾客可 能是人，如在银行等待取款的顾客，也可能是物，如等待进港的船只；服务台可能是人，如售票员， 也可能是物，如机场跑道；顾客数可能有限，如等待买票的人，也可能无限，如泄洪问题中的上游来 水. 随机服务系统又称为排队系统. 排队系统的描述：顾客到达服务台是随机的.顾客到达服务台时，若服务台空闲，则立刻接受服 务；否则，顾客应等待至服务台空闲时，再接受服务.顾客接受服务后即离开服务台. 排队系统的三要素： （1）输入过程：指顾客到达的规律，如顾客数（有限或无限），顾客到达的方式（批量或单个）， 相继到达的顾客之间的时间间隔的分布. （2）排队规则：包括服务台是否允许排队，顾客的排队意愿，服务顺序（先到先服务，后到先 服务，随机服务，优先权服务）等. （3）服务机制：服务台的数目，多服务台服务时的连结方式（串连或并连），服务时间的分布. 平稳状态：正常的，稳定的运行状态.如当储蓄所早上开门时，顾客很少，是为过渡期；此后， 业务活动渐渐进入平稳状态. 显然，当排队系统处于平稳状态时，任意时刻时的顾客的数目的变化率（导数）等于 0. 排队论的研究对象是平稳状态时的排队系统. 1953 年，D. G. Kendall 引入了排队系统的符号模型： 顾客到达的时间间隔的分布/服务时间的分布/服务台的数目/排队系统允许的最大顾客容量 如排队模型 M / M /1/  ，其中 M 表示顾客到达的时间间隔相互独立，且都服从指数分布， M 表示服务台对顾客的服务时间相互独立，且都服从指数分布，1 为服务台的数目，  表示排队系统允 许的最大顾客数无限制. 排队系统的主要数量指标： （1）平均排队队长：排队等待的平均顾客数 Lq ； （2）平均队长：平均顾客数 L ； 显然， L = Lq + 正在接受服务的顾客数.如对排队模型 M / M /1/  ，有 L = Lq +1. （3）平均排队时间：顾客排队等待接受服务的平均时间 Wq ；