排队论课件1

排队论(QueueingTheory)§1基本概念§2到达间隔的分布和服务时间的分布§3单服务台负指数分布排队系统的分析§4多服务台负指数分布排队系统地分析§5一般服务时间M/G/1模型§6经济分析——排队系统的最优化重点和难点一、重点1、排队论(系统)的基本问题–排队系统的效率评价问题–排队系统的最优设计问题–排队系统的识别(辨识或推断)问题2、排队系统的基本组成(1)输入过程•顾客的总体(个数)•顾客到达的方式(单个或成批)•顾客相继到达的间隔时间(确定型或随机型)•顾客到达时独立的或关联的•输入过程是平稳的或非平稳的(2)排队规则–即时制或等待制–等待制的服务次序•先到先服务•后到先服务•随机服务•有优先权的服务–排队的队列有形的或无形的–排队的容量是有限的还是无限的–队列的数目是单列还是队列(3)服务机构–有形的服务员或无形的服务员–一个服务员(服务台)或多个服务员–多个服务台并列或串列–服务方式是单个服务或是成批服务–服务时间是确定型或随机型–服务时间的分布式平稳的或非平稳的3、排队系统的分类与表示：X/Y/Z/A/B/C4、排队系统的指标：队长Ls,排队长Lq,逗留时间Ws,等待时间Wq,忙期，服务强度5、平均到达率，平均服务率，平均间隔时间、平均服务时间6、泊松流的性质7、泊松分布的概率分布和数字特征8、负指数分布的分布和密度函数与数字特征9、k阶爱尔朗分布的性质与特征§1基本概念•排队论起源于1909年丹麦电话工程师A.K．爱尔朗的工作，他对电话通话拥挤问题进行了研究。1917年，爱尔朗发表了他的著名的文章—“自动电话交换中的概率理论的几个问题的解决”。•排队论已广泛应用于解决军事、运输、维修、生产、服务、库存、医疗卫生、教育、水利灌溉之类的排队系统的问题，显示了强大的生命力。1．1排队过程的一般表示图12-1就是排队过程的一般模型。•各个顾客由顾客源（总体）出发，到达服务机构（服务台、服务员）前排队等侯接受服务，服务完了后就离开。•排队结构指队列的数目和排列方式，排队规则和服务规则是说明顾客在排队系统中按怎样的规则、次序接受服务的。•我们所说的排队系统就指图中虚线所包括的部分。顾客源顾客到达排队规则服务规则排队结构服务机构顾客离去在现实中的排队现象是多种多样的•在现实中的排队现象是多种多样的，对上面所说的“顾客”和“服务员”，要作广泛地理解，它现可以是人，也可以是非生物；•队列可以是具体地排列，也可以是无形的（例如向电话交换台要求通话的呼唤）；•顾客可以走向服务机构，也可以相反（如送货上门）。•下面举一些例子说明实现中形形色色的排队系统（见表12-1）表12-1到达的顾客要求服务内容服务机构1．不能运转的机器2．修理技工3．病人4．电话呼唤5．文件稿6．提货单7．到达机场上空的飞机8．驶入港口的货船9．上游河水进入水库10．进入我方阵地的敌机修理领取修配零件诊断或动手术通话打字提取存货降落装（卸）货放水，调整水位我方高射炮进行射击修理技工发放修配零件的管理员医生（或包括手术台）交换台打字员仓为管理员跑道装（卸）货码头(泊位)水闸管理员我方高射炮1．2排队系统的组成和特征•一般的排队系统都有三个基本组成部分•1.输入过程；•2.排队规则；•3.服务机构。输入过程•现在分别说明各部分的特征：•（1）输入过程：输入即指顾客到达排队系统。可能有下列各种不同情况，当然这些情况并不是彼此排斥的。•（a）顾客的总体（称为顾客源）的组成可能是有限的，也可能是无限的。工厂内停机待修的机器显然是有限的总体。•（b）顾客到来的方式可能是一个一个的，也可能是成批的。例如到餐厅就餐就有单个到来的顾客和受邀请来参加宴会的成批顾客，我们将只研究单个至来的情形。输入过程•（c）顾客相继到达的间隔时间可以是确定型的，也可以是随机型的。•如在自动装配线上装配的各部件就必须按确定的时间间隔到达装配点，定期运行的班车、班轮、班机的到达也都是确定型的。•但一般到商店购物的顾客、到医院诊病的病人、通过路口的车辆等，它们的到达都是随机型的。•对于随机型的情形，要知道单位时间内的顾客到达数或相继到达的间隔时间的概率分布（图12-2）顾客到达时间ti-1titi+1输入过程•(d)顾客的到达可以是相互独立的。•就是说，以前的到达情况对以后顾客的到来没有影响，否则就是有关联的。•例如，工厂内的机器在一个短的时间内出现停机（顾客到达）的概率就受已经待修或被修理的机器数目的影响。•我们主要讨论的是相互独立的情形。输入过程•（e）输入过程可以是平衡的，或称对时间是齐次的，是指描述相继到达间隔时间分布和所含参数（如期望值、方差等）都是与时间无关的，否则称为非平衡的，非平稳情形的数学处理是很困难的。（2）排队规则•（a）顾客到达时，如所有服务台都正被占用，在这种情形下顾客可以随即离去，也可以排队等侯。•随即离去的称为即时制或称损失制，因为这将失掉许多顾客；•排队等侯的称为等待制。排队规则•对于等待制，为顾客进行服务的次序可以采用下列各种规则：•先到先服务，后到先服务，随机服务，有优先权的服务等。•先到先服务(FCFS)，即按到达次序接受服务，这是通常的情形。•后到先服务(LCFS)，如乘用电梯的顾客常是后人先出的。仓库中存放的厚钢板也是如此。在情报系统中，最后到达的信息往往是最有价值的，因而常采用后到先服务（指被采用）的规则。排队规则•随机服务，指服务员从等待的顾客中随机地选取其一进行服务，而不管到达的先后，如电话交换台接通呼唤的电话就是如此。•有优先权的服务，如医院对于病情严重的患者将给予优先治疗。•（b）从占有的空间来看，队列可以排在具体的处所（如售票处、候诊室等），也可以是抽象的（如向电话交换台要求通话的呼唤）。•由于空间的限制或其它原因，有的系统要规定容量（即允许进入排队系统的顾客数）的最大限；有的没有这种限制（即认为容量可以是无限的）。排队规则•（c）从队列的数目看，可以是单列，也可以是多列。•在多列的情形，各列间的顾客有的可以互相转移，有的不能（如用绳子或栏杆隔开）。•有的排队顾客因等候时间过长而中途退出，有的不能退出（如高速公路上的汽车流），必须坚持到被服务为止。•我们将只讨论各列间不能互相转移、也不能中途退出的情形。3）服务机构•从服务机构的形式和工作情况来看有以下几种情况。•（a）服务机构可以没有服务员，也可以有一个或多个服务员（服务台、通道、窗口等）.•例如，在敞架售书的书店，顾客选书时就没有服务员，但交款时可能有多个服务员。服务机构•（b）在有多个服务台的情形中，它们可以是平行排列（并列）的，可以是前后排列（串列）的，也可以是混合的。图12-3说明这些情形。•图a是单队—单服务台，图b是多队—多服务台，图c是单队—多服务台（并列）的情形，图d是多服务台（串列）的情形，图e是多服务台（混合）的情形。112c…c12…12…cabcd111e服务机构•(d)服务方式可以对单个顾客进行，也可以对成批顾客进行，公共汽车对站台等候的顾客就成批进行服务，我们将只研究单个单个地服务方式。•（e）和输入过程一样，服务时间也分确定型的和随机型的。自动冲洗（服务）的时间就是确定，但大多数情形的服务时间是随机型的。对于随机型的服务时间，需要知道它的概率分布。•（f）和输入过程一样，服务时间的分布我们总假定是平稳的，即分布的期望值、方差等参数都不受时间的影响。1.3排队模型的分类•D.G.Kendall在1953年提出一个分类方法，按照上述各部分的特征中最主要的、影响最大的三个，即•1．相继顾客到达间隔时间的分布；•2．服务时间的分布；•3．服务台个数。排队模型的分类•按照这三个特征分类，并用一定符号表示，称为Kendall记号。这只对并列的服务台（如果服务台是多于一个的话）的情形，他用的符号形式是：•X/Y/Z•其中X处填写表示相继到达间隔时间的分布，•Y处填写表示服务时间的分布，•Z处填写并列的服务台数目。排队模型的分类•表示相继到达间隔时间和服务时间的各种分布的符号是：•M――负指数分布（M是Markov的字头，因为负指数分布具有无记忆性，即Markov性）•D――确定定型（Deterministic）•Ek――k阶受尔朗(Frlang)分布•GI――般相互独立（GeneralIndependent）的时间间隔的分布•G――一般（General）服务时间的分布排队模型的分类•例如：•M／M／l表示相继到达间隔时间为负指数分布、服务时间负指数分布、单服务台的模型；•D／M／c表示确定的到达间隔、服务时间为负指数分布、c个平行服务台（但顾客是一队）的模型。排队模型的分类•以后，在1971年一次关于排队论符号标准化会议上决定，将Kendall符号扩充成为：•X／Y／Z／A／B／C•形式，其中前三项意义不变，•A处填写系统容量限制N，•B处填写顾客源数目m，•C处填写服务规则，如先到服务FCFS，后到先服务LCFS等。•并约定，如略去后三项，即指X／Y／Z／∞／∞／FCFS的情形。在本书中，因只讨论先到先服务FCFS的情形，所以略去第六项。1．4排队问题的求解•一个实际问题作为排队问题求解时，首先要研究它属于哪个模型，其中只有顾客到达的间隔时间分布和服务时间的分布需要实测的数据来确定，其它因素都是在问题提出时给定的。解排队问题的目的•解排队问题的目的，是研究排队系统运行的效率，估计服务质量，确定系统参数的最优值，以决定系统结构是否合理、研究设计改进措施等。•所以必须确定用以判断系统运行优劣的基本数量指标，解排队问题就是首先求出这些数量指标的概率分布或特征数。排队系统的指标•这些指标通常是：•（1）队长，指在系统中的顾客数，它的期望值记作Ls；•排队长（队列长，指在系统中排队等待服务的顾客数，它的期望值记作Lq;••一般情形，Ls（或Lq）越大，说明服务率越低，排队成龙，是顾客最厌烦的。的顾客数正被服务＋服务的顾客数在队列中等待＝顾客数系统中排队系统的指标•（2）逗留时间，指一个顾客在系统中的停留时间，它的期望值记作Ws；•（3）等待时间，指一个顾客在系统中排队等待的时间，它的期望值记作Wq，•服务时间＋等待时间＝逗留时间排队系统的指标•在机器故障问题中，无论是等待修理或正在修理都使工厂受到停工的损失，所以逗留时间（停工时间）是主要的；但一般购物、诊病等问题中仅仅等待时间常是顾客们所关心的。排队系统的指标•此外，还有忙期(BusyPeriod)指从顾客到达空闲服务机构起到服务机构再次为空闲止这段时间长度，即服务机构连续繁忙的时间长度，它关系到服务员的工作强度，忙期和一个忙期中平均完成服务顾客都是衡量服务机构效率的指标。排队系统的指标•在即时制或排队有限缺点情形，还有由于顾客被拒绝而使企业受到损失的损失率以及以后经常遇到的服务强度等，这些都是很重要的指标。排队系统的状态•计算这些指标的基础是表达系统状态的概率，所谓系统的状态即指系统中顾客数，如系统中有n个顾客就说系统的状态是n，它的可能值是•（1）队长没有限制时，n＝0，1，2…•（2）队长有限制，最大数为N时，n＝0，1，2，…，N,•（3）即时制，服务台个数是c时，n=0，1，2，…，c。•后者，状态n又表示正在工作（繁忙）的服务台数。排队系统的状态•这些状态的概率一般是随时刻t而变化，所以在时刻t、系统状态为n的概率用Pn（t）表示。•求状态概率Pn(t)的方法，首先要建立含Pn（t）的关系式见图12-4,因t为是连续变量，而n只取非负整数，所以建立的Pn（t）的关系式一般是微分差分方程（关于t微分瞬态解是不容易的，一般地，即使求出也很难利用，因此我们常用它的极限（如果存在的话）••称为稳态（Steadystate），或称统计平衡状态(StatisticalEquilibriumState)的解。nntPtP)(lim排队系统的状态•稳态的物理含义是，当系统运行了无限长的时间之后，初始(t=0)出发状态的概率分布（Pn(0)，n≥0）的影响将消失，而