吉林大学远程教育 运筹学课件8.1

1、运 筹 学 第八章 排队论 1 排队服务系统的基本概念排队服务系统的基本概念n 在生产和日常生活中，经常可以碰到各种各样的服务系统。如上下班乘公共汽车，公共汽车与乘客构成一个服务系统；到商店买东西，售货员与顾客也构成一个服务系统，都有等候服务的问题。n 有些场合下，服务系统的构成没有那么明显。如从长春往北京打电话，由于长春、北京之间同一时间内允许通话对数是有限的，因此，要求通话的人数超过这个限度时，就要排队等候。虽然打电话的人分散在全市各处，彼此互不见面，但他们与长话台一起构成一个服务系统。他们在长话台前排成一个无形的队伍，就如同排队等候公共汽车的乘客队伍一样。n 一般在一个排队服务系统中总是

2、包含一个或若干个 “服务设施” ，有许多“顾客”进入该系统要求得到服务，服务完毕后即自行离去。倘若顾客到达时，服务系统空闲着，则到达的顾客立即得到服务，否则顾客将排队等待服务或离去。 上面说的“顾客”是对要求得到服务的对象的代称，可以是人，也可以是物； “服务设施” 也可以各种各样。如在用自动机床进行生产的车间，一个工人往往要看若干台机床，当机床发生故障或要求加料、更换刀具时，要求工人进行修理或照管。在同一时间内，一个工人只能在一台机床上修理或照管，如这时又有别的机床需要该工人修理或照管，就必须等待。这样，工人与需要修理或照管的机床之间就构成了一个服务系统，这里工人是“服务设施” ，“顾客”是

3、要求修理或照管的机床。又如，一座水库，上游的水滚滚而来，如果调节得好，水库水位保持在安全理想水平，既起到防洪作用，又保证正常发电、航运和灌溉。如调节不好，水库水位过高或过低，就影响水库综合效能的发挥。这里，水库与水构成一个服务系统，水库是“服务设施” ，水就是要求得到服务的“顾客”。 类似例子还可以举出很多，如医院和等待诊治的病人；机场跑道同要求起飞降落的飞机；港口泊位与进港待泊的船只；车站售票口与排队买票的旅客之间都构成了一个个排队服务系统。 如果到达服务系统的顾客完全按固定的间隔时间到达，又服务设施用在每个顾客身上的服务时间也是固定的，就象工厂流水生产线的生产那样有固定的节拍，那么这类服务

4、系统的设计计算是比较方便的。但在大多数的服务系统中，情况不是这样，顾客的到达经常是随机的，并且服务设施用于每个顾客身上的服务时间往往也是随机的，对于这样一类随机服务系统的设计计算就要困难得多。 车站的售票口应开设多少个比较合适呢？开设越多，方便旅客，减少排队时间，但售票口增多了，就要增加服务人员及相应的设施，增加服务费用。这样，顾客排队时间的长短与服务设施规模的大小就构成设计随机服务系统的一对矛盾。有些场合下，如公共汽车的班次可以随季节及顾客到达规律的变化进行调整，但另一些场合，服务设施的规模，如机场跑道、港口泊位、电话线路等一旦建成则变动不易，因此需要有一个进行设计计算遵循的理论依据。到底怎

5、样才能做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾，就是研究随机服务系统的理论排队论所要研究解决的问题。 排队论的理论起源于对电话服务系统的研究。从1909年开始，丹麦的电话工程师爱尔朗（A.K.Eelang）等人在这方面进行了长期的工作，取得了最早的成果。以后排队论陆续应用于陆空交通、机器管理、水库设计和可靠性理论等方面。六十年代，随着电子计算机蓬勃发展的需要，又应用于计算机网络的最优设计。在接近九十年的历史中，排队论无论在理论或应用上都有了飞速进展。由于在电子计算机上进行数字模拟技术的发展，排队论已成为解决工程设计和管理问题的有力

6、工具。 1.1 排队系统排队系统n 现实中的排队现象是多种多样的，一般排队系统都有下述三个基本组成部分（图10-1）。顾客源顾客到来排队规则排队结构服务规则服务机构离去排队系统图10-1 1.输入过程输入过程指顾客到达服务系统情况。 顾客总体（顾客源）的组成可能是有限的，也可能是无限的。上游河水流入水库可以认为总体是无限的；工厂内停机待修的机器，显然是有限的总体。 顾客相继到达的时间间隔可以是确定的，也可以是随机的。如自动装配线上装配的各部件一般按确定的时间间隔到达装配点；但到医院就诊的病人，到餐厅就餐的顾客等，他们的到达都是随机的。 顾客的到达方式可能是一个一个的，也可能是成批的。我们将只研

7、究单个到达的情形。 2.排队规则排队规则 顾客到达时，如果所有服务台都被占用，则顾客离开服务系统，这种方式称为即时制即时制或损失制损失制。例如旅客到旅店住宿就属于这种方式。另外一种情形，当服务台被占用时，后来的顾客就排队等待服务，称为等待制等待制。 有的服务系统对进入排队系统的顾客数有一定限制，象理发店供等待服务的顾客坐的椅子的座位数是有限的。大多数服务系统可以认为系统对顾客是没有限制的。 在多服务台情况下，队列的数目可以是单列，也可以是多列。 等待服务的次序，最常见的是先到先服务先到先服务；还有带优先权的服务带优先权的服务，如加急电报、医院的急诊等；随机服随机服务务，指服务台随机对等待的顾客

8、进行服务；后到先服务后到先服务，如乘坐电梯的顾客先入后出，后入先出。 3.服务机构服务机构n 从服务设施的数量上可分为单服务台与多服务台。n 在多服务台情形，服务台可能是并列的，也可能是串列的。并列服务系统可以同时对多个顾客进行服务，而串列情况下，每个顾客要依次经过各个服务台的服务才能离开系统。图10-2中（a）是多队多台并列情形；（b）是单队多台并列情形；（c）是单队多台串列情形。n 服务时间可以分成确定型和随机型两种情形。自动机床对零件的加工时间是确定型的，大多数情况服务时间是随机型的。图图1010-2-2（a）（b）（c）121122nnn 1.2 排队模型的分类排队模型的分类n 按照排

9、队系统组成部分的主要特征可以对排队模型进行分类。1971年排队论符号标准化会议决定，排队模型分类符号为：n X/Y/Z/A/B/Cn其中 X处填写顾客相继到达时间间隔的分布；n Y处填写服务时间的分布；n Z处填写并列的服务台数量；n A处填写系统容量限制；n B处填写顾客源数量；n C处填写服务次序，如先到先服务FCFS；后到先服务LCFS等，如果略去该项则表示先到先服务。先到先服务。n 表示相继到达间隔时间和服务时间的各种分布符号是：n M 负指数分布（Markov）n D 确定型分布（Deterministic） n Ekk阶爱尔朗分布（Erlang）n GI一般独立分布的时间间隔（Ge

10、neral Independent）n G一般服务时间的分布（ General ） 例如：M/M/1/表示顾客相继到达的间隔时间为负指数分布，服务时间为负指数分布，单服务台，系统对顾客无限制，顾客源无限，先到先服务的服务模型。 1.3 排队模型的参数排队模型的参数 在排队系统的分析计算中，要用到下面一些概念和符号：n Pn（t）在时刻t系统中恰好有n个顾客的概率。n N（t）在时刻t服务系统中的顾客数。n 稳定状态当一个排队服务系统开始运转时，系统状态很大程度上取决于系统的初始状态和运转经历的时间，但过去一段时间后，系统的状态将独立于初始状态及经历的时间，这时称系统处于稳定状态。在稳定状态下，

11、系统处于某一状态的概率是一个常数。所以Pn（t）可写为Pn。由于对系统的瞬时状态分析比较困难，所以排队论中主要研究系统处于稳定状态的工作情况。n n当系统有n个顾客时，新来顾客的平均到达率（单位时间到达的顾客数），则1/ n表示相邻两个顾客到达的平均间隔时间。如60分钟内到达30个顾客，则平均到达率n=3060=1/2（人/分钟），平均间隔时间为1/ n =2（分钟），即平均每隔2分钟来1人。n n当系统有n个顾客时，整个系统的服务率（单位时间服务完的顾客数），则1/ n表示对每个顾客的平均服务时间。如60分钟内服务完3个顾客，则平均服务率n=360=0.05（人/分钟），对每个顾客的平均服务时间为1/ n=20（分钟），即平均每20分钟服务