运筹学第11章等候线模型

1、第第11章章 等候线模型等候线模型 回想一下上一次称不得不等候的情形回想一下上一次称不得不等候的情形：在超市的收银台等候，在银行等候出纳：在超市的收银台等候，在银行等候出纳员，或者是在快餐店等候服务员。在类似员，或者是在快餐店等候服务员。在类似上述需要排队的情况下，把时间用于等待上述需要排队的情况下，把时间用于等待是令人非常不快的。然而增加更多的收银是令人非常不快的。然而增加更多的收银员、银行出纳员或服务生并不总是改变服员、银行出纳员或服务生并不总是改变服务水平的最经济的策略。因此，各行各业务水平的最经济的策略。因此，各行各业需要采取相应的措施，把等待时间控制在需要采取相应的措施，把等待时间控

2、制在顾客所能容忍的限度内。顾客所能容忍的限度内。 人们已经设计建立了一些模型来帮助管人们已经设计建立了一些模型来帮助管理者理解等候线的运作，并帮助他们做出更理者理解等候线的运作，并帮助他们做出更好的决策。等候线用管理科学的术语来讲也好的决策。等候线用管理科学的术语来讲也称队列，与等候线相关的知识体系称为排队称队列，与等候线相关的知识体系称为排队论。论。20世纪初，丹麦的一个电话工程师世纪初，丹麦的一个电话工程师A.K.阿朗开始对打电话时发生的阻塞和等待时间阿朗开始对打电话时发生的阻塞和等待时间进行研究。之后，排队论的发展已经日趋复进行研究。之后，排队论的发展已经日趋复杂，并广泛的运用到等候线情

3、形中。杂，并广泛的运用到等候线情形中。 等候线模型包括一些数学公式以及可用于确定等等候线模型包括一些数学公式以及可用于确定等候线运行参数（绩效指标）的关系式。相关的一些运候线运行参数（绩效指标）的关系式。相关的一些运行参数如下：行参数如下：(1)系统中没有任何个体的概率；系统中没有任何个体的概率；(2)等候线中等待个体的平均数；等候线中等待个体的平均数；(3)系统中个体的平均数（等候线中个体的平均数加上系统中个体的平均数（等候线中个体的平均数加上接收服务的个体的数目）；接收服务的个体的数目）；(4)一个个体在等候线中所花费的平均时间；一个个体在等候线中所花费的平均时间；(5)一个个体在系统中花

4、费的平均时间（等候时间加上一个个体在系统中花费的平均时间（等候时间加上服务时间）；服务时间）；(6)一个个体到达以后不得不等待以接受服务的概率；一个个体到达以后不得不等待以接受服务的概率； 管理者具备了以上的信息，才能更好的做出使期管理者具备了以上的信息，才能更好的做出使期望服务水平与所花费的成本相平衡的决策。望服务水平与所花费的成本相平衡的决策。11.1等候线系统的结构等候线系统的结构 为了说明等候线系统的基本特征，我们以为了说明等候线系统的基本特征，我们以伯格伯格.度姆快餐店的等候线为例。伯格度姆快餐店的等候线为例。伯格.度姆快度姆快餐店出售火腿汉堡、奶酪汉堡、法式油炸食品餐店出售火腿汉堡

5、、奶酪汉堡、法式油炸食品、软包装饮料和搅拌牛奶，同时还有一些特色、软包装饮料和搅拌牛奶，同时还有一些特色食品和甜点可供选择。虽然伯格食品和甜点可供选择。虽然伯格.度姆快餐店度姆快餐店希望能为每位顾客提供即时的服务，但是很多希望能为每位顾客提供即时的服务，但是很多时候，到达的顾客远远多于伯格时候，到达的顾客远远多于伯格.度姆快餐店度姆快餐店的服务人员所能接待的人数。因此，顾客们不的服务人员所能接待的人数。因此，顾客们不得不排队，以等候所点快餐并取走所点的食品得不排队，以等候所点快餐并取走所点的食品。 伯格伯格.度姆快餐店担心，它目前所用的顾客度姆快餐店担心，它目前所用的顾客服务方式正导致过长的等

6、候时间。管理层已经服务方式正导致过长的等候时间。管理层已经提出要求，需要对等候线进行研究，以开发一提出要求，需要对等候线进行研究，以开发一个能够减少等待时间、提高服务质量的最佳服个能够减少等待时间、提高服务质量的最佳服务方式。务方式。 一般的排队过程可以这样描述：顾客为了一般的排队过程可以这样描述：顾客为了获得某种服务而到达服务台；若因服务台在忙获得某种服务而到达服务台；若因服务台在忙，不能立即获得服务而又被允许排队等待，则，不能立即获得服务而又被允许排队等待，则加入等待队列，获得服务之后离开系统。但实加入等待队列，获得服务之后离开系统。但实际的排队系统千差万别，为了对排队系统进行际的排队系统

7、千差万别，为了对排队系统进行研究，有必要按照排队系统的几个主要特征加研究，有必要按照排队系统的几个主要特征加以分类。这几个主要特征就是：输入过程；服以分类。这几个主要特征就是：输入过程；服务机构；排队规则。务机构；排队规则。 1. 输入过程输入过程输入过程即顾客达到的规律，顾客的到达或者输入过程即顾客达到的规律，顾客的到达或者独立于其他任何因素，或者和某个因素独立于其他任何因素，或者和某个因素(例如例如系统中的队列长度，系统的运行时间系统中的队列长度，系统的运行时间)有关；有关；刻画输入过程需要了解以下几方面的内容：刻画输入过程需要了解以下几方面的内容：（1）顾客或为单个达到，或为成批到达。例

8、）顾客或为单个达到，或为成批到达。例如到医院就诊大部分为单个到来的顾客，但也如到医院就诊大部分为单个到来的顾客，但也不排除成批病人的情况，有时成批的可看作单不排除成批病人的情况，有时成批的可看作单个的情形来处理。个的情形来处理。（2）顾客或来自有限的总体，或来自无限的）顾客或来自有限的总体，或来自无限的总体。前者为顾客源有限的情况，如工厂内停总体。前者为顾客源有限的情况，如工厂内停机待修的机器；后者为顾客源无限的情况，如机待修的机器；后者为顾客源无限的情况，如就诊病人可视为总体是无限的。就诊病人可视为总体是无限的。 （3）相继顾客到达间隔时间的分布，这）相继顾客到达间隔时间的分布，这是输入过程

9、最主要的特征。常见的两种分布是输入过程最主要的特征。常见的两种分布有定长分布和负指数分布。如在自动装配线有定长分布和负指数分布。如在自动装配线上装配的各部件就必须按确定的时间间隔到上装配的各部件就必须按确定的时间间隔到达装配点，定期运行的班车、班轮、班机的达装配点，定期运行的班车、班轮、班机的到达间隔时间也都是定长分布。但一般到商到达间隔时间也都是定长分布。但一般到商店购物的顾客、到医院诊病的病人、通过路店购物的顾客、到医院诊病的病人、通过路口的车辆等，它们到达间隔时间一般都服从口的车辆等，它们到达间隔时间一般都服从负指数分布。负指数分布。 （4）顾客的到达一般是相互独立的，就）顾客的到达一般

10、是相互独立的，就是说，以前的到达情况对以后顾客的到来没是说，以前的到达情况对以后顾客的到来没有影响，否则就是有关联的。本章主要讨论有影响，否则就是有关联的。本章主要讨论相互独立的情形。相互独立的情形。 2.排队规则排队规则排队规则首先指的是顾客是否可以排队，若排队规则首先指的是顾客是否可以排队，若可以排队，服务台按什么次序为顾客服务。可以排队，服务台按什么次序为顾客服务。就顾客是否可以排队，又可分为两种情况：就顾客是否可以排队，又可分为两种情况：（1）损失制，顾客到达时，如所有服务台）损失制，顾客到达时，如所有服务台都正被占用，在这种情形下顾客随即离去，都正被占用，在这种情形下顾客随即离去，这

11、种情形称为即时制或称损失制。如打电话这种情形称为即时制或称损失制。如打电话时，发现对方占线，即挂断，即为损失制；时，发现对方占线，即挂断，即为损失制； （2）等待制，顾客到达时，如所有服务）等待制，顾客到达时，如所有服务台都正被占用，顾客则排队等候的称为等待台都正被占用，顾客则排队等候的称为等待制。如到理发店理发，机器发生故障待修都制。如到理发店理发，机器发生故障待修都是等待制。等待制又可分为队长（或等待时是等待制。等待制又可分为队长（或等待时间）有限制的与无限制的两种情况。如理发间）有限制的与无限制的两种情况。如理发店若只能容店若只能容8个顾客排队等候，则为队长有限个顾客排队等候，则为队长有

12、限制的情况；火车站的售票厅可以容纳很多人制的情况；火车站的售票厅可以容纳很多人排队买票，则视为队长无限制的情况。若超排队买票，则视为队长无限制的情况。若超过一定等待时间，顾客即离去，为等待时间过一定等待时间，顾客即离去，为等待时间有限制的情形；若坚持接受服务后再离去，有限制的情形；若坚持接受服务后再离去，则为无限制的情形。，这是最通常的情形，则为无限制的情形。，这是最通常的情形，也是本章要讨论的情形。也是本章要讨论的情形。 先到先服务（先到先服务（FCFS），即按到达次序接），即按到达次序接受服务，这是最通常的情形，也是本章要讨受服务，这是最通常的情形，也是本章要讨论的情形。论的情形。 后到先

13、服务（后到先服务（LCFS），如仓库中存放），如仓库中存放的厚钢板就是后入先出的，在情报系统中，的厚钢板就是后入先出的，在情报系统中，最后到达的信息往往是最有价值的，因而常最后到达的信息往往是最有价值的，因而常被首先分析或采用。被首先分析或采用。 随机服务（随机服务（SIRO），指服务台从等待的），指服务台从等待的顾客中随机地选取一个进行服务，而不管到顾客中随机地选取一个进行服务，而不管到达的先后。如电话交换台接通呼唤的电话就达的先后。如电话交换台接通呼唤的电话就是这种服务方式。是这种服务方式。 有优先权的服务（有优先权的服务（PR），如医院对于病），如医院对于病情严重的患者将给予优先治疗，加

14、急电报或情严重的患者将给予优先治疗，加急电报或特快专递优先发出。特快专递优先发出。 3.服务机构服务机构 服务机构的特征主要包括以下几方面：服务机构的特征主要包括以下几方面：服务台数目；在多个服务台时，是串联还是服务台数目；在多个服务台时，是串联还是并联；服务时间的概率分布。如自动冲洗汽并联；服务时间的概率分布。如自动冲洗汽车的装置对每辆汽车冲洗车的装置对每辆汽车冲洗(服务服务)的时间就是的时间就是确定的，服从定长分布，但大多数情形的服确定的，服从定长分布，但大多数情形的服务时间是随机的。常见的服务时间分布有：务时间是随机的。常见的服务时间分布有：（1）定长分布）定长分布(D)；（；（2）指数

15、分布）指数分布(M)；（；（3）k阶爱尔朗分布阶爱尔朗分布(Ek)；（；（4）一般分布）一般分布(G)。 本章主要利用负指数分布的服务时间：本章主要利用负指数分布的服务时间：负指数分布具有如下的概率密度函数和分布负指数分布具有如下的概率密度函数和分布函数：函数：( ),( )1xxf xeF xe ，假设服务台对顾客的服务时间假设服务台对顾客的服务时间t服从负指数服从负指数分布，即分布，即F(t)=e-t；则对于每一顾客的平均服务时间则对于每一顾客的平均服务时间为为1/ ，而，而自然代表服务率。自然代表服务率。11.1.1排队系统的符号表示排队系统的符号表示 上述排队系统的特征可以有许许多多的

16、组合，上述排队系统的特征可以有许许多多的组合，从而形成不同的排队模型，这就需要有一个排队模从而形成不同的排队模型，这就需要有一个排队模型的符号表示方法，简明地表示出主要特征，在型的符号表示方法，简明地表示出主要特征，在1971年关于排队论符号标准化会议上决定年关于排队论符号标准化会议上决定,现在国际现在国际通用的形式是通用的形式是: XYZABC式中式中 X相继顾客到达间隔时间的概率分布；相继顾客到达间隔时间的概率分布； Y服务时间的概率分布；服务时间的概率分布； Z服务台数目；服务台数目； A排队系统容量，即可容纳的最大顾客数；排队系统容量，即可容纳的最大顾客数； B顾客源中顾客总体的数目；

17、顾客源中顾客总体的数目； C服务规则。服务规则。 表示相继到达间隔时间和服务时间的各种表示相继到达间隔时间和服务时间的各种分布的符号是：分布的符号是： M负指数分布负指数分布(M是是Markov的字头，的字头，因为负指数分布具有无记忆性，即因为负指数分布具有无记忆性，即Markov性性) D确定型确定型(Deterministic) Ekk阶爱尔朗阶爱尔朗(Erlang)分布分布 G一般一般(General)服务时间的分布服务时间的分布 例如，例如，MM1/FCFS表示相继到表示相继到达间隔时间为负指数分布达间隔时间为负指数分布, 服务时间为负指服务时间为负指数分布数分布, 单服务台，系统容量

18、无限，顾客源单服务台，系统容量无限，顾客源数目无限，先到先服务的模型；数目无限，先到先服务的模型；MMC/N/ m /FCFS则为相继到达间隔时间与服务则为相继到达间隔时间与服务时间均为负指数分布时间均为负指数分布,C个服务台，系统容量个服务台，系统容量为为N，顾客源数目为，顾客源数目为m，先到先服务的模型，先到先服务的模型。并约定，如略去后三项，即指。并约定，如略去后三项，即指XYZFCFS的情形，如略去第六项，则为的情形，如略去第六项，则为先到先服务先到先服务FCFS的情形。的情形。 解排队问题的目的，是研究排队系统解排队问题的目的，是研究排队系统运行的效率，估计服务质量，确定系统参运行的

19、效率，估计服务质量，确定系统参数的最优值，以决定系统结构是否合理、数的最优值，以决定系统结构是否合理、研究设计及改进措施等。所以必须确定用研究设计及改进措施等。所以必须确定用以判断系统运行优劣的基本数量指标，优以判断系统运行优劣的基本数量指标，优化排队问题须首先求出这些数量指标。这化排队问题须首先求出这些数量指标。这些指标通常有：些指标通常有： N(t): t时刻系统中的顾客数，又称系时刻系统中的顾客数，又称系统状态或队长；统状态或队长； Nq(t): t时刻队列中的顾客数，又称排时刻队列中的顾客数，又称排队长；队长； 以上两个指标及其它一些指标均为随机以上两个指标及其它一些指标均为随机变量，

20、且与时刻变量，且与时刻t有关，即为瞬态随机变量，有关，即为瞬态随机变量，因为稳态（与所处时刻无关）是关注的情形因为稳态（与所处时刻无关）是关注的情形，而且大部分排队系统在运行一段时间后，而且大部分排队系统在运行一段时间后，会达到统计平衡状态，即稳态。所以本章关会达到统计平衡状态，即稳态。所以本章关注以下稳态运行指标：注以下稳态运行指标： N: 系统中的顾客数或队长，其均值为系统中的顾客数或队长，其均值为L，即平均队长；，即平均队长； Nq: 排队长，其均值为排队长，其均值为Lq，即平均排队，即平均排队长；长； T：顾客逗留时间，其均值为：顾客逗留时间，其均值为W，即平，即平均逗留时间；均逗留时

21、间； Tq：顾客等待时间，其均值为：顾客等待时间，其均值为Wq，即，即平均等待时间；平均等待时间； n:系统顾客数为系统顾客数为n时的平均到达率时的平均到达率(以单以单位时间内到达的顾客数表示位时间内到达的顾客数表示)，一般情形时，一般情形时， n为常数，令其为为常数，令其为 :顾客的平均到达率；顾客的平均到达率； n:系统顾客数为系统顾客数为n时服务台平均服务率时服务台平均服务率(以单位时间内服务的顾客数表示以单位时间内服务的顾客数表示)，对于不同，对于不同的的n，若，若n为常数，令为为常数，令为 :服务台平均服务服务台平均服务率；率； Pn: 系统内有系统内有n个顾客的概率。个顾客的概率。

22、 此外，还有忙期此外，还有忙期(Busy Period)及平均忙及平均忙期等一些指标，指服务机构连续繁忙的时间期等一些指标，指服务机构连续繁忙的时间长度，它关系到服务员的工作强度。忙期和长度，它关系到服务员的工作强度。忙期和一个忙期中平均完成服务顾客数都是衡量服一个忙期中平均完成服务顾客数都是衡量服务机构效率的指标。在即时制或排队有限制务机构效率的指标。在即时制或排队有限制的情形，还有由于顾客被拒绝而使企业受损的情形，还有由于顾客被拒绝而使企业受损失的损失率等，这些都是很重要的指标。失的损失率等，这些都是很重要的指标。 11.1.2 单列等候线单列等候线 在伯格在伯格.度姆快餐店目前所实行的运

23、作方式中，度姆快餐店目前所实行的运作方式中，首先由一名服务生接受一位顾客的点餐，计算总费首先由一名服务生接受一位顾客的点餐，计算总费用，向顾客收取餐费，然后上菜。为第一位顾客上用，向顾客收取餐费，然后上菜。为第一位顾客上菜之后，这名服务生就可以为下一位等待中的顾客菜之后，这名服务生就可以为下一位等待中的顾客服务。这种运作方式就是一个单列等候线模型的例服务。这种运作方式就是一个单列等候线模型的例子。每位进入伯格子。每位进入伯格.度姆快餐店的顾客都必须通过这度姆快餐店的顾客都必须通过这一条渠道（一个接收点餐和上餐的工作台）以进行一条渠道（一个接收点餐和上餐的工作台）以进行点餐、付款，然后取食品。当

24、到达的顾客人数很多点餐、付款，然后取食品。当到达的顾客人数很多，以至于工作人员不能及时提供服务时，顾客们就，以至于工作人员不能及时提供服务时，顾客们就会形成一条等候队伍，等待这个点餐和上菜的工作会形成一条等候队伍，等待这个点餐和上菜的工作台为其提供服务。有关伯格台为其提供服务。有关伯格.度姆快餐店的单列等候度姆快餐店的单列等候线如图线如图11-1所示。所示。 11.1.3 达到间隔分布达到间隔分布 为等候线确定到达过程，主要包括确为等候线确定到达过程，主要包括确定在某个给定时间段内顾客到达数目的概定在某个给定时间段内顾客到达数目的概率分布。对于有些等候线情形来说，顾客率分布。对于有些等候线情形

25、来说，顾客的到达具有随机性和独立性，我们也不能的到达具有随机性和独立性，我们也不能预测新的顾客会在什么时候到达。在这种预测新的顾客会在什么时候到达。在这种情况下，管理科学家们发现，顾客的到达情况下，管理科学家们发现，顾客的到达规律可以用泊松概率分布来很好地进行描规律可以用泊松概率分布来很好地进行描述。述。 泊松概率函数可以计算出在某个泊松概率函数可以计算出在某个时间段内，有时间段内，有x位顾客到达的概率。该位顾客到达的概率。该概率函数如下：概率函数如下： ,(0,1,2.)!xxeP xxx式中，式中， x-在此时间段内到达的人数在此时间段内到达的人数; -每个时间段内到达的平均人数；每个时间

26、段内到达的平均人数； e=2.718 28e-的值可以利用计算器或通过书末附录的值可以利用计算器或通过书末附录B计计算得出。算得出。(11-1)0.750.75( )!xxxeeP xxx4724. 0! 075. 0)0(75. 075. 00ee 假设伯格假设伯格. .度姆快餐店已经对相关的度姆快餐店已经对相关的顾客到达数据进行了分析，并得知平均每顾客到达数据进行了分析，并得知平均每小时到达的顾客人数为小时到达的顾客人数为4545人。也就是说，人。也就是说，平均平均1 1分钟内到达人数为分钟内到达人数为=45=45名顾客名顾客/60/60分钟分钟=0.75=0.75名顾客名顾客/ /分钟。

27、因此，我们可以分钟。因此，我们可以利用下面的泊松概率函数计算利用下面的泊松概率函数计算1 1分钟内有分钟内有x x为顾客到达的概率：为顾客到达的概率： 从而，从而，1 1分钟内有分钟内有0 0为、为、1 1位和位和2 2位顾客到位顾客到达的概率分别为：达的概率分别为：3543. 04724. 075. 075. 0! 175. 0) 1 (75. 075. 01ee1329. 024724. 05625. 0! 275. 0)2(75. 02e可见，可见，1分钟内没有顾客到达的概率为分钟内没有顾客到达的概率为0.472 4， 有有1位顾客到达的概率为位顾客到达的概率为0.354 3，有有2位顾

28、客到达的概率为位顾客到达的概率为0.132 9.表表11-1表表示偶尔一分钟内到达的顾客数的概率。示偶尔一分钟内到达的顾客数的概率。 表表 11-1 1分钟内到达伯格分钟内到达伯格.度姆快餐店度姆快餐店的顾客人数概率分布的顾客人数概率分布 到达顾客数到达顾客数 概率概率 0 0.472 4 0 0.472 4 1 0.354 3 1 0.354 3 2 0.132 9 2 0.132 9 3 0.033 2 3 0.033 2 4 0.006 2 4 0.006 2 5 0.001 0 5 0.001 0 在第在第11.2节和第节和第11.3节中，我们将要讨节中，我们将要讨论到等待线模型，其中

29、伯格论到等待线模型，其中伯格.度姆快餐店的度姆快餐店的顾客到达人数是用泊松分布描述的。在实顾客到达人数是用泊松分布描述的。在实际应用中，我们要记录几天或几个星期内际应用中，我们要记录几天或几个星期内每个时间段的实际到达人数，并将观察到每个时间段的实际到达人数，并将观察到的到达人数概率分布与泊松概率分布相比的到达人数概率分布与泊松概率分布相比较，以确定由泊松概率分布计算得出的值较，以确定由泊松概率分布计算得出的值是否是实际到达人数分布的合理的近似值是否是实际到达人数分布的合理的近似值。 tet1)(服务时间11.1.4服务时间分布服务时间分布 服务时间是指从服务开始，某位顾客在服务服务时间是指从

30、服务开始，某位顾客在服务台所花费的时间。对于伯格台所花费的时间。对于伯格.度姆快餐店而言，服度姆快餐店而言，服务时间是从顾客开始向服务生点餐开始，并持续务时间是从顾客开始向服务生点餐开始，并持续到顾客拿到所点的食品为止。服务时间通常不是到顾客拿到所点的食品为止。服务时间通常不是固定的。在伯格固定的。在伯格.度姆快餐店，每位顾客所点的食度姆快餐店，每位顾客所点的食品数目和品种有很大的不同。点餐少的顾客可能品数目和品种有很大的不同。点餐少的顾客可能在几秒钟内完成，但点餐多的顾客的可能要花在几秒钟内完成，但点餐多的顾客的可能要花2分分钟甚至更长的时间才能完成。钟甚至更长的时间才能完成。 管理科学学家

31、们发现，如果服务时间的概率管理科学学家们发现，如果服务时间的概率分布可以用指数概率分布来表示，那么可以用公分布可以用指数概率分布来表示，那么可以用公式计算等候线运作所需的有用信息。利用指数概式计算等候线运作所需的有用信息。利用指数概率分布来计算服务时间小于或等于时间长度率分布来计算服务时间小于或等于时间长度t时的时的概率如下：概率如下：其中，其中，-每个时间段内可接受服务的个每个时间段内可接受服务的个体的均值；体的均值；e=2.718 28。 假设伯格假设伯格.度姆快餐店已经研究了接受度姆快餐店已经研究了接受点餐和上菜的过程，并发现每个服务生平点餐和上菜的过程，并发现每个服务生平均每小时能为均

32、每小时能为60位顾客提供点餐服务。在位顾客提供点餐服务。在此基础上，可以得出平均服务率为此基础上，可以得出平均服务率为=60名名顾客顾客/60分钟分钟=一名顾客一名顾客/分钟。例如，当分钟。例如，当=1时，我们可以用式（时，我们可以用式（11-3）来计算在）来计算在0.5分分钟内、钟内、1分钟内分钟内以及以及2分钟内可以处理一个点餐要求的概率分钟内可以处理一个点餐要求的概率。计算分别如下：。计算分别如下：1 0.5(0.511 0.60650.3935Pe 服务时间分钟）1 1.0(1.011 0.36790.6321Pe 服务时间分钟）1 2.0(2.011 0.13530.8647e 服务

33、时间分钟） 因此，我们可以得出结论：因此，我们可以得出结论：0.5分钟内分钟内能处理一个点餐要求的概率为能处理一个点餐要求的概率为0.393 5，1分分钟内能处理一个点餐要求的概率为钟内能处理一个点餐要求的概率为0.632 1，2分钟内能处理一个点餐要求的概率为分钟内能处理一个点餐要求的概率为0.864 7。 本章所述的几个等候线模型中，我们假本章所述的几个等候线模型中，我们假定服务时间的概率分布服从指数分布。在定服务时间的概率分布服从指数分布。在实践中，我们应该收集相关的实际服务时实践中，我们应该收集相关的实际服务时间的数据，以确定由指数分布得出的值是间的数据，以确定由指数分布得出的值是否是

34、实践中服务时间的合理近似值。否是实践中服务时间的合理近似值。11.1.5 稳态运行稳态运行 当伯格当伯格.度姆快餐店早上开始营业时，度姆快餐店早上开始营业时，店里没有顾客。渐渐地，营业开始正常或店里没有顾客。渐渐地，营业开始正常或呈稳定状态。我们将开始或起始阶段成为呈稳定状态。我们将开始或起始阶段成为过渡（瞬时）阶段。当系统正常或稳态运过渡（瞬时）阶段。当系统正常或稳态运行时，过渡（瞬时）阶段结束。等候线模行时，过渡（瞬时）阶段结束。等候线模型描述了等候线的稳态运行参数。型描述了等候线的稳态运行参数。11.2 到达服从泊松分布、服务时间服从指到达服从泊松分布、服务时间服从指数分布的单列等候线模

35、型数分布的单列等候线模型(M/M/1 ) 在本节中，为了确定标准在本节中，为了确定标准MM1/模模型（即型（即MM1/模型）的稳态运行数模型）的稳态运行数据，我们将引进一些相关的公式。如果顾客据，我们将引进一些相关的公式。如果顾客到达服从泊松分布，并且服务时间服从指数到达服从泊松分布，并且服务时间服从指数分布，则我们就可以应用这些公式。因为上分布，则我们就可以应用这些公式。因为上述假设符合第述假设符合第11.1节中讨论的伯格节中讨论的伯格.度姆快餐度姆快餐店问题，因此，我们将解释如何应用这些公店问题，因此，我们将解释如何应用这些公式来确定伯格式来确定伯格.度姆快餐店的运行参数，并度姆快餐店的运

36、行参数，并据此为管理层提供有益的决策信息。据此为管理层提供有益的决策信息。11.2.111.2.1运行参数运行参数 我们可以用下述公式来计算到达服从我们可以用下述公式来计算到达服从泊松分布、服务时间服从指数分布的单列泊松分布、服务时间服从指数分布的单列等候线的运行参数，其中，等候线的运行参数，其中， -每个时间段内到达的平均数（平每个时间段内到达的平均数（平均到达率）；均到达率）； -每个时间段内服务的平均数（平每个时间段内服务的平均数（平均服务率）；均服务率）；1. 1. 系统中没有任何个体的概率：系统中没有任何个体的概率： 10（11-411-4）qLLqqLW 1qWW3 3 系统中个体

37、的平均数：系统中个体的平均数：4 4 一个个体在等候线中所花费的平均时间：一个个体在等候线中所花费的平均时间：5 5 一个个体在系统中花费的平均时间：一个个体在系统中花费的平均时间：2 2等候线中个体的平均数：等候线中个体的平均数：)(2qL (11-5) (11-5)(11-6)(11-7)(11-8)11 9很明显，平均到达率 和平均服务时间 的值是决定运行参数的重要因素。通过式（）可以看出，平均到达率和平均服务时间的比值表示一个到达的个体由于服务设施处于被使用的状态而不得不等候的概率。因此，通常将看作服务设施的利用系数。0)(nn7 7 系统中同时有系统中同时有n n个个体的概率：个个体

38、的概率：(11-10)(11-10)w6 6 某位刚到达的个体必须等待的概率：某位刚到达的个体必须等待的概率：(11-9)111 411 10111 411 10只有当平均服务率 大于平均到达率（即 ）时，式（） （）所求的运行参数才适用。如果不存在上述情况，则等候线将会无限期增长，因为服务设施没有足够的能力接待新到达的个体。因此，必须要求当 时，我们才能利用式（）式（）来计算。11.2.2伯格伯格.度姆快餐店问题的运行参数度姆快餐店问题的运行参数 回顾一下，在伯格回顾一下，在伯格.度姆快餐店的问题度姆快餐店的问题中，我们已经得到一个平均到达率中，我们已经得到一个平均到达率=0.75和一个平均

39、服务率和一个平均服务率=1。111411 10.因此，在的情况下，可以利用式（） （）来计算伯格度姆快餐店的单列等候线的运行参数。75. 0175. 0(41131( 375. 025. 2( 3175. 025. 2(25. 2)75. 01 (175. 0)(250. 0175. 011220wqqqqqWWLWLLLP分钟）分钟）位顾客）位顾客）我们可以用式（我们可以用式（11-10）确定系统中任何数）确定系统中任何数目顾客的概率。表目顾客的概率。表11-2提供了应用式（提供了应用式（11-10）得出的概率。）得出的概率。 表11-2 伯格.度姆快餐店的等候线系统中有n位顾客的率顾客人数

40、顾客人数 概率概率 0 0.250 0 0 0.250 0 1 0.187 5 1 0.187 5 2 0.140 6 2 0.140 6 3 0.105 5 3 0.105 5 4 0.079 1 4 0.079 1 5 0.059 3 5 0.059 3 6 0.044 5 6 0.044 5 7 7个或更多个或更多 0.133 50.133 5 11.2.3管理者对等候线模型的应用管理者对等候线模型的应用 伯格伯格.度姆快餐店的单列等候线的计算结果给出了度姆快餐店的单列等候线的计算结果给出了一些关于等候线运作的重要信息。特别值得注意的是一些关于等候线运作的重要信息。特别值得注意的是，顾客

41、们在点餐前的平均等待时间为，顾客们在点餐前的平均等待时间为3分钟，这对以分钟，这对以快速服务为宗旨的快餐行业来说，多少有些长了点。快速服务为宗旨的快餐行业来说，多少有些长了点。此外，我们还注意到，等待中的顾客平均人数为此外，我们还注意到，等待中的顾客平均人数为2.25位，且顾客不得不等待的概率为位，且顾客不得不等待的概率为75%，这也要求我们，这也要求我们必须采取措施来改善等候线的运作。通过表必须采取措施来改善等候线的运作。通过表11-2，我，我们知道，在伯格们知道，在伯格.度姆快餐店的系统中，同时有度姆快餐店的系统中，同时有7个或个或7个以上顾客等待的概率为个以上顾客等待的概率为0.1335

42、.这一数字表明，如果这一数字表明，如果伯格伯格.度姆快餐店继续使用单列等候线运作方式，则很度姆快餐店继续使用单列等候线运作方式，则很可能会出现较长的等待队伍。可能会出现较长的等待队伍。 如果相对于公司的服务标准来讲，伯格如果相对于公司的服务标准来讲，伯格.度姆快餐度姆快餐店的运作参数并不令人满意。因此，快餐店的管理者店的运作参数并不令人满意。因此，快餐店的管理者应当考虑采取其他设计或计划来改善等候线的运作。应当考虑采取其他设计或计划来改善等候线的运作。11.2.4改进等候线运作改进等候线运作 等候线模型通常会显示出哪些运作参数需要改等候线模型通常会显示出哪些运作参数需要改善。然而，要就怎样改变

43、等候线结构来改善运行参善。然而，要就怎样改变等候线结构来改善运行参数做出决策，必须依靠分析家的洞察力和创造力。数做出决策，必须依靠分析家的洞察力和创造力。 考察了等候线模型所提供的运行参数之后，伯考察了等候线模型所提供的运行参数之后，伯格格.度姆快餐店的管理者认为有必要改善等候线的度姆快餐店的管理者认为有必要改善等候线的运作从而减少顾客的等候时间。为了改善等候线的运作从而减少顾客的等候时间。为了改善等候线的运作，分析家们常常侧重于采用提高服务率的方法运作，分析家们常常侧重于采用提高服务率的方法。一般来讲，要提高服务率，需要做出下面一两种。一般来讲，要提高服务率，需要做出下面一两种改变：改变：

44、(1)通过创造性的设计变更或利用新技术来提通过创造性的设计变更或利用新技术来提高平均服务率高平均服务率。 (2)增加服务渠道，这样能够使更多的顾客得增加服务渠道，这样能够使更多的顾客得到即时服务。到即时服务。 假设在考虑方案假设在考虑方案1时，伯格时，伯格.度姆快餐店的管理度姆快餐店的管理者决定雇用一名上菜员来帮助收银台旁的点餐员。者决定雇用一名上菜员来帮助收银台旁的点餐员。从点餐员点餐开始，顾客开始接受服务。点餐后，从点餐员点餐开始，顾客开始接受服务。点餐后，点餐员通过一个内部通讯系统报出菜名，然后由上点餐员通过一个内部通讯系统报出菜名，然后由上菜员开始上菜。点餐完毕后，点餐员处理付款事宜菜

45、员开始上菜。点餐完毕后，点餐员处理付款事宜，上菜员继续上菜。按照这一设计，伯格，上菜员继续上菜。按照这一设计，伯格.度姆快餐度姆快餐店的管理者预测，平均服务率可以从现在的每小时店的管理者预测，平均服务率可以从现在的每小时60位顾客上升到每小时位顾客上升到每小时75位顾客。也就是说，改变位顾客。也就是说，改变后的系统的平均服务率为后的系统的平均服务率为=75位顾客位顾客/60分钟分钟=1.25位顾客位顾客/分钟。在分钟。在=0.75位顾客位顾客/分钟且分钟且=1.25位顾客位顾客/分钟的情况下，我们可以利用式（分钟的情况下，我们可以利用式（11-4）式（式（11-10）重新计算伯格度姆快餐店的等

46、候线的新的运）重新计算伯格度姆快餐店的等候线的新的运行参数。计算得到的运行参数如表行参数。计算得到的运行参数如表11-3所示。所示。 系统中没有顾客的概率系统中没有顾客的概率等候线中顾客的平均人数等候线中顾客的平均人数系统中顾客的平均人数系统中顾客的平均人数一位顾客的等候线中花费一位顾客的等候线中花费的平均时间的平均时间分钟分钟一位顾客在系统中花费的一位顾客在系统中花费的平均时间平均时间分钟分钟一位到达的顾客必须等候一位到达的顾客必须等候的概率的概率系统中有系统中有7位以上（含位以上（含7位）位）顾客的概率顾客的概率表表11-3 平均服务率上升到平均服务率上升到=1.25位顾客位顾客/分钟时，

47、伯分钟时，伯格度姆快餐店系统的运行参数格度姆快餐店系统的运行参数 从表从表11-3中我们可以看出，服务率的提中我们可以看出，服务率的提高改善了所有的运行参数。特别地，顾客排高改善了所有的运行参数。特别地，顾客排队等候所花费的平均时间从队等候所花费的平均时间从3分钟下降到了分钟下降到了1.2分钟；顾客在系统中所花的平均时间从分钟；顾客在系统中所花的平均时间从4分钟减少到分钟减少到2分钟。然而，还没有其他的方分钟。然而，还没有其他的方法可以让伯格度姆的快餐店提高服务率呢？法可以让伯格度姆的快餐店提高服务率呢？如果有，并且每种方法中的平均服务率如果有，并且每种方法中的平均服务率都都能确定，则可以利用

48、式（能确定，则可以利用式（11-4）式（式（11-10）来计算改变后的运行参数以及等候线系统）来计算改变后的运行参数以及等候线系统中的所有改善。我们可以将实施改进方案所中的所有改善。我们可以将实施改进方案所增加的成本与提高的服务质量进行比较，从增加的成本与提高的服务质量进行比较，从而帮助管理者决定实行改善方案的服务改善而帮助管理者决定实行改善方案的服务改善策略是否有价值。策略是否有价值。 正如前面所提到的，方案正如前面所提到的，方案2可以提供一个可以提供一个或多个额外的服务梁道。从而可以在同一时间或多个额外的服务梁道。从而可以在同一时间内为多位顾客服务。下一界讨论的主题就是把内为多位顾客服务。

49、下一界讨论的主题就是把单列等候线模型扩展到多位等候线模型。单列等候线模型扩展到多位等候线模型。11.2.5等候线模型的等候线模型的Excel解法解法 在工作表的帮助下，我们可以很容易的实在工作表的帮助下，我们可以很容易的实施等候线模型。伯格度姆快餐店单列等候线的施等候线模型。伯格度姆快餐店单列等候线的Excel工作表如图工作表如图11-2所示。阴影部分是输入所示。阴影部分是输入了公式的单元格，明亮的部分是输入了数值的了公式的单元格，明亮的部分是输入了数值的单元格。在单元格单元格。在单元格B7和和B8中分别输入平均到中分别输入平均到达率和平均服务率，然后将等候线相关运行参达率和平均服务率，然后将

50、等候线相关运行参数的公式输入到单元格数的公式输入到单元格C13到到C18中。中。通过该工作表得到的结果与我们前面得到的通过该工作表得到的结果与我们前面得到的运行参数的值是相同的。我们可以通过在单运行参数的值是相同的。我们可以通过在单元格元格B7和和B8输入不同的平均到达率和（或）输入不同的平均到达率和（或）平均服务率，来得出等候线设计的变更。如平均服务率，来得出等候线设计的变更。如此就可以立刻得到等候线的新的运行参数。此就可以立刻得到等候线的新的运行参数。 图图11-2所示的工作表是一个模板，可以所示的工作表是一个模板，可以用于所有到达服从泊松分布、服务时间服从用于所有到达服从泊松分布、服务时

51、间服从指数分布的单列等候线模型。该工作表及本指数分布的单列等候线模型。该工作表及本章中提到的其他的一些等候线模型的类似工章中提到的其他的一些等候线模型的类似工作表，可以参见在本书附带的作表，可以参见在本书附带的CD盘中的内容盘中的内容。例：某修理店只有一个修理工，来修理的顾例：某修理店只有一个修理工，来修理的顾客到达过程为客到达过程为Poisson流，平均流，平均4人人/h；修理；修理时间服从负指数分布，平均需要时间服从负指数分布，平均需要6min.试求试求：（：（1）修理店空闲的概率；（）修理店空闲的概率；（2）店内恰有）店内恰有3个顾客的概率；（个顾客的概率；（3）店内至少有一个顾客）店内

52、至少有一个顾客的概率；（的概率；（4）在店内的平均顾客数；（）在店内的平均顾客数；（5）每位顾客在店内的平均逗留时间；（每位顾客在店内的平均逗留时间；（6）等）等待服务的平均顾客数；（待服务的平均顾客数；（7）每位顾客平均）每位顾客平均等待服务时间；（等待服务时间；（8）顾客在店内等待时间）顾客在店内等待时间超过超过10min的概率。的概率。4101 . 01526 . 052110p038. 0)521 ()52()1 (333p解解 本例可看成一个本例可看成一个M/M/1/排队问题，其中排队问题，其中 修理店空闲的概率修理店空闲的概率店内恰有店内恰有3个顾客的概率个顾客的概率 4 . 05

53、2110pNP（人）67. 0521521L(min)10)(467. 0hLW店内至少有店内至少有1个顾客的概率个顾客的概率在店内的平均顾客数在店内的平均顾客数每位顾客在店内的平均逗留时间每位顾客在店内的平均逗留时间)(267. 052152122人LLq(min)4)(4267. 0hLWq3679. 01011516110eeTP等待服务的平均顾客数等待服务的平均顾客数每位顾客平均等待服务时间每位顾客平均等待服务时间顾客在店内逗留时间超过顾客在店内逗留时间超过10min的概率的概率11.3 到达服从泊松分布、服务时间服从指到达服从泊松分布、服务时间服从指数分布的多列等候线模型数分布的多列

54、等候线模型(M/M/k ) 一个多列等候线包括两个或两个以上的一个多列等候线包括两个或两个以上的服务梁道，假设这些服务渠道就服务能力而服务梁道，假设这些服务渠道就服务能力而言是相同的。在多列系统中，到达的个体在言是相同的。在多列系统中，到达的个体在单列等候线中等待，然后移动到第一个可用单列等候线中等待，然后移动到第一个可用的梁道接收服务。图的梁道接收服务。图11-3为伯格度姆快餐店为伯格度姆快餐店的一个双梁道示意图。的一个双梁道示意图。 本节中，我们将介绍确定多列等候线本节中，我们将介绍确定多列等候线稳态运行参数的公式。这些公式的应用前稳态运行参数的公式。这些公式的应用前提为下列条件成立：提为

55、下列条件成立：到达服从泊松分布；到达服从泊松分布；各个梁道的服从时间服从指数分布；各个梁道的服从时间服从指数分布；各个梁道的平均服务率各个梁道的平均服务率相同；相同；到达者在单列等候先中等候，然后移动到到达者在单列等候先中等候，然后移动到第一个可用的梁道接受服务。第一个可用的梁道接受服务。02101/!kknPknkk （11-1111-11） 02/1 !kqLPkk (11-12)(11-12)11.3.1运行参数运行参数 我们可以用下列公式来计算多列等候我们可以用下列公式来计算多列等候线的稳态运行参数线的稳态运行参数,其中其中, 表示系统中的平表示系统中的平均到达率均到达率;表示每个两道

56、的平均服务率表示每个两道的平均服务率;k表表示渠道数示渠道数.1.系统中没有任何个体的概率系统中没有任何个体的概率:2.等候线中个体的平均数等候线中个体的平均数:qLLqqLW1qWW (11-15) (11-15)3.系统中个体的平均数系统中个体的平均数:(11-13)4.一个个体在等候线中所花费的平均时间一个个体在等候线中所花费的平均时间:(11-14)5.一个个体在系统中花费的平均时间一个个体在系统中花费的平均时间:01!kwkPPkk 0/!nnPPn 0/!nnn kPPk k (对于对于nk) （11-17） （对于（对于n nk k）（）（11-1811-18）6.某位刚到达的个

57、体必须等待的概率某位刚到达的个体必须等待的概率:(11-16)7.系统中同时有系统中同时有n个个体的概率：个个体的概率： 因为因为为每个渠道的平均服务率，所以为每个渠道的平均服务率，所以k就就是多列系统的平均服务率。我们已经知道上述公是多列系统的平均服务率。我们已经知道上述公式适用与单列等候线模型，但只有当系统的平均式适用与单列等候线模型，但只有当系统的平均服务率大于系统的平均到达率时，这些公式才能服务率大于系统的平均到达率时，这些公式才能使用于多列等候线模型的运行参数。也就是说，使用于多列等候线模型的运行参数。也就是说，对于多列等候线模型，只有当对于多列等候线模型，只有当k时，才可以时，才可

58、以应用上述公式。应用上述公式。 对于多列等候线，有些运行参数的表达式比对于多列等候线，有些运行参数的表达式比单列等候线的要复杂。但是，式（单列等候线的要复杂。但是，式（11-11）式（式（11-18）给出了与单列等候线模型相同的信息。）给出了与单列等候线模型相同的信息。为了帮助简化多列等候线模型中的公式的运用，为了帮助简化多列等候线模型中的公式的运用，表表11-4给出了根据所选定的一些给出了根据所选定的一些和的值所和的值所计算出的计算出的0 的值。表中的数值都对应着的值。表中的数值都对应着k的情况，即服务率足够处理到达的顾客。的情况，即服务率足够处理到达的顾客。11.3.2 伯格伯格度姆快餐店

59、问题的运行参数度姆快餐店问题的运行参数 为了说明多列等候线模型，我们仍然以为了说明多列等候线模型，我们仍然以伯格度姆快餐店的等候线为例。如果管理者伯格度姆快餐店的等候线为例。如果管理者想对增开第二个点餐工作台（以便能同时为想对增开第二个点餐工作台（以便能同时为2位顾客提供服务）的可行性进行评估。假位顾客提供服务）的可行性进行评估。假设在单列等候线中排在第一位的顾客首先到设在单列等候线中排在第一位的顾客首先到达空闲的服务生处接受服务。下面我们来计达空闲的服务生处接受服务。下面我们来计算这个双梁道系统的运行参数：算这个双梁道系统的运行参数：P0 =0.4545（见表（见表11-4，其中，其中，/=

60、0.75）22(0.75/1)0.75 10.45450.1227(2 1)!(2 1 0.75)qL 0.750.12270.87271qLL0.12270.16360.75qqLW110.16361.16361qWW21 0.752 1()0.45450.20452!12 1 0.75WP （位顾客）（位顾客）（位顾客）（位顾客）（分钟）（分钟）（分钟）（分钟）利用式（利用式（11-17）和式（）和式（11-18），我们可以计算出系），我们可以计算出系统中有统中有n位顾客的概率。计算结果如表位顾客的概率。计算结果如表11-5所示。所示。 现在，我们可以将双梁道系统的稳态运行参数现在，我们可