管理运筹学

1,排队论,基本概念输入过程和服务时间分布泊松输入指数服务排队模型排队系统的优化目标与最优化问题,本章内容重点,2,排队论(Queuing Theory)，又称随机服务系统理论(Random Service System Theory),是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。,前 言,3,排队是我们在日常生活和生产中经常遇到的现象。 例如，上、下班搭乘公共汽车；顾客到商店购买物品；病员到医院看病；旅客到售票处购买车票；学生去食堂就餐等就常常出现排队和等待现象。,前 言,4,如：几个顾客打电话到出租汽车站要求派车，如果出租汽车站无足够车辆、则部分顾客只得在各自的要车处等待，他们分散在不同地方，却形成了一个无形队列在等待派车。,前 言,有形 无形,5,例如，通讯卫星与地面若干待传递的信息；生产线上的原料、半成品等待加工；因故障停止运转的机器等待工人修理；码头的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋等等。,前 言,排队的不一定是人 也可以是物,6,上述各种问题虽互不相同，但却都有要求得到某种服务的人或物和提供服务的人或机构。 排队论里把要求服务的对象统称为“顾客”,而把提供服务的人或机构称为“服务台”或“服务员”。不同的顾客与服务组成了各式各样的服务系统。,前 言,7,不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图4-1至图4-5。,图4-1 单服务台排队系统,前 言,8,图4-2 单队列S个服务台并联的排队系统,图4-3 S个队列S个服务台的并联排队系统,前 言,9,图4-4 单队多个服务台的串联排队系统,图4-5 多队多服务台混联、网络系统,前 言,10,图4-6 随机服务系统,前 言,一般的排队系统，都可由下面图4-6加以描述。,11,通常称由图4-6表示的系统为一随机聚散服务系统，任一排队系统都是一个随机聚散服务系统。 “聚”-顾客的到达 “散”-顾客的离去,前 言,12,“随机性”则是排队系统的一个普遍特点，是指顾客的到达情况(如相继到达时间间隔)与每个顾客接受服务的时间往往是事先无法确切知道的，或者说是随机的。 一般地，排队论所研究的排队系统中，顾客到来的时刻和服务台提供服务的时间长短都是随机的，因此这样的服务系统被称为随机服务系统。,前 言,13,面对拥挤现象，人们总是希望尽量设法减少排队，通常的做法是增加服务设施。但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费，如果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响。于是，顾客排队时间的长短与服务设施规模的大小，就构成了设计随机服务系统中的一对矛盾。如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾，这就是随机服务系统理论排队论所要研究解决的问题。,前 言,矛盾,14,如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾，这就是随机服务系统理论排队论所要研究解决的问题。,前 言,15,排队论是1909年由丹麦工程师爱尔朗(A.KErlang)在研究电活系统时创立的，一个世纪以来排队论的应用领域越来越广泛，理论也日渐完善。特别是自二十世纪60年代以来，由于计算机的飞速发展，更为排队论的应用开拓了宽阔的前景。,前 言,16,第一节 基 本 概 念,(3)顾客到达系统的时刻是随机的，为每一位顾客提供服务的时间是随机的，因而整个排队系统的状态也是随机的。,一、排队系统的描述,（一）系统特征和基本排队过程,实际的排队系统虽然千差万别，但是它们有以下的共同特征：,(1)请求服务的人或物顾客；,(2)为顾客服务的人或物，即服务员或服台；,17,(1)顾客总体数，又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。,（二）排队系统的基本组成部分,通常，排队系统都有输入过程、服务规则和服务台等3个组成部分,1输入过程这是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流一般可以从3个方面来描述个输入过程。,18,(3)顾客流的概率分布，或称相继顾客到达的时间间隔的分布。这是求解排队系统有关运行指标问题时，首先需要确定的指标。这也可以理解为在一定的时间间隔内到达K个顾客(K=1、2、)的概率是多大。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等。,(2)顾客到达方式。这是描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。,19,(1)损失制。这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。,2.服务规则。这是指服务台从队列中选取顾客进行服务的顺序。一般可以分为损失制、等待制和混合制等3大类。,20,等待制中，服务台在选择顾客进行服务时，常有如下四种规则：,(2)等待制。这是指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。,先到先服务。按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形。,后到先服务。仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。,21,优先权服务。,随机服务。即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务。,22, 队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。,(3)混合制这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：, 等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。,23, 逗留时间(等待时间与服务时间之和)有限。,损失制和等待制可看成是混合制的特殊情形，如记s为系统中服务台的个数，则当K=s时，混合制即成为损失制；当K=时，混合制即成为等待制。,24,3服务台情况。服务台可以从以下3方面来描述： (1) 服务台数量及构成形式。从数量上说，服务台有单服务台和多服务台之分。从构成形式上看，服务台有： 单队单服务台式； 单队多服务台并联式； 多队多服务台并联式； 单队多服务台串联式； 单队多服务台并串联混合式,以及 多队多服务台并串联混合式等等。见前面图4-1至图4-5所示。,25,(2) 服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客就属于成批服务。,(3) 服务时间的分布。一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K级爱尔良分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。,26,为了区别各种排队系统，根据输入过程、排队规则和服务机制的变化对排队模型进行描述或分类，可给出很多排队模型。为了方便对众多模型的描述，肯道尔（DGKendall）提出了一种目前在排队论中被广泛采用的“Kendall记号”，完整的表达方式通常用到6个符号并取如下固定格式：A/B/C/D/E/F 各符号的意义为：,（三）排队系统的描述符号与分类,27,A表示顾客相继到达间隔时间分布，常用下列符号：M表示到达过程为泊松过程或负指数分布；D表示定长输入；Ek表示k阶爱尔朗分布；G表示一般相互独立的随机分布。,28,B表示服务时间分布，所用符号与表示顾客到达间隔时间分布相同。M表示服务过程为泊松过程或负指数分布；D表示定长分布；Ek 表示k阶爱尔朗分布；G表示一般相互独立的随机分布。,C表示服务台(员)个数：“1”则表示单个服务台，“s”。(s1)表示多个服务台。,29,D表示系统中顾客容量限额，或称等待空间容量；如系统有K个等待位子，则 0K，当 K=0 时，说明系统不允许等待，即为损失制。K= 时为等待制系统，此时一般省略不写。K为有限整数时，表示为混合制系统。,E表示顾客源限额，分有限与无限两种，表示顾客源无限，此时一般也可省略不写。,30,F表示服务规则，常用下列符号： FCFS：表示先到先服务的排队规则； LCFS：表示后到先服务的排队规则； PR：表示优先权服务的排队规则。,例如：某排队问题为MMSFCFS，则表示顾客到达间隔时间为负指数分布(泊松流)；服务时间为负指数分布；有s(s1)个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则。,31,某些情况下，排队问题仅用上述表达形式中的前3个、4个、5个符号。如不特别说明则均理解为系统等待空间容量无限；顾客源无限，先到先服务，单个服务的等待制系统。,32,二、排队系统的主要数量指标 研究排队系统的目的是通过了解系统运行的状况，对系统进行调整和控制，使系统处于最优运行状态。因此，首先需要弄清系统的运行状况。描述一个排队系统运行状况的主要数量指标有：,33,1.队长和排队长（队列长）,队长和排队长一般都是随机变量。 我们希望能确定它们的分布，或至少能确定它们的平均值(即平均队长和平均排队长)及有关的矩(如方差等)。,排队长是指系统中正在排队等待服务的平均顾客数。,队长是指系统中的平均顾客数(排队等待的顾客数与正在接受服务的顾客数之和)，,34,从顾客到达时刻起到他开始接受服务止这段时间称为等待时间，是随机变量，也是顾客最关心的指标，因为顾客通常希望等待时间越短越好。 从顾客到达时刻起到他接受服务完成止这段时间称为逗留时间，也是随机变量，同样为顾客非常关心。,2等待时间和逗留时间,35,此外，还会用到其他一些重要的指标，如在损失制或系统容量有限的情况下，由于顾客被拒绝，而使服务系统受到损失的顾客损失率及服务强度等，也都是十分重要的数量指标。,3忙期和闲期,忙期是指从顾客到达空闲着的服务机构起，到服务机构再次成为空闲止的这段时间，即服务机构连续忙的时间。,与忙期相对的是闲期，即服务机构连续保持空闲的时间。,在排队系统中，忙期和闲期总是交替出现的,36,上面给出的这些数量指标一般都是和系统运行的时间有关的随机变量，求这些随机变量的瞬时分布一般是很困难的。为了分析上的简便，并注意到相当一部分排队系统在运行了一定时间后，都会趋于一个平衡状态(或称平稳状态)。在平衡状态下，队长的分布、等待时间的分布和忙期的分布都和系统所处的时刻无关，而且系统的初始状态的影响也会消失。因此，我们在本章中将主要讨论与系统所处时刻无关的性质，即统计平衡性质。,37,Wq 平均等待时间，即(在任意时刻)进入稳态系统的顾客等待时间的期望值。,L或Ls 平均队长，即稳态系统任一时刻的所有 顾客数的期望值；,Lq 平均等待队长或队列长，即稳态系统任一时刻的等待服务的顾客数的期望值；,W或Ws 平均逗留时间，即(在任意时刻)进入稳态系统的顾客逗留时间的期望值；,38,这四项主要性能指标(又称主要工作指标)的值越小，说明系统排队越少，等待时间越少，因而系统性能越好。 显然，它们是顾客与服务系统的管理者都很关注的。,39,s系统中并联服务台的数目； 平均到达率；1/ 平均到达间隔。 平均服务率；1/ 平均服务时间。服务强度，即每个服务台单位时间内的平均服务时间；一般有=/(s) ；N稳态系统任一时刻的状态(即系统中所有顾客数)；,(2)其他常用数量指标,40,Pn=PN=n：稳态系统任一时刻状态为n的概率；特别当n=0时，Pn即P0，而P0即稳态系统所有服务台全部空闲(因系统中顾客数为0)的概率。 对于损失制和混合制的排队系统，顾客在