• 1. 随机服务系统理论 排队论及其应用
  • 2. 排队论的基本概念 排队系统描述 基本概念 M / M / 1 模型 M / M / S 模型
  • 3. 第一节 排队系统描述顾客---要求服务的对象统称为“顾客” 服务台---把提供服务的人或机构称为“服务台”或“服务员”
  • 4. 各种形式的排队系统
  • 5. 各种形式的排队系统
  • 6. 各种形式的排队系统
  • 7. 各种形式的排队系统
  • 8. 各种形式的排队系统
  • 9. 随机服务系统
  • 10. 排队论所要研究解决的问题 面对拥挤现象,人们通常的做法是增加服务设施,但是增加的数量越多,人力、物力的支出就越大,甚至会出现空闲浪费,如果服务设施太少,顾客排队等待的时间就会很长,这样对顾客会带来不良影响。如何做到既保证一定的服务质量指标,又使服务设施费用经济合理,恰当地解决顾客排队时间与服务设施费用大小这对矛盾,就是随机服务系统理论——排队论所要研究解决的问题。
  • 11. 第一节 基本概念; 一、排队系统的描述 二、排队系统的主要数量指标
  • 12. 一、排队系统的描述 (一)系统特征和基本排队过程 (二)排队系统的基本组成部分 (三)排队系统的描述符号
  • 13. (一)系统特征和基本排队过程相似的特征及数学抽象: (1)请求服务的人或者物——顾客; (2)有为顾客服务的人或者物,即服务员或服务台; (3)顾客到达系统的时刻是随机的,为每一位顾客提供服务的时间是随机的,因而整个排队系统的状态也是随机的。
  • 14. (一)系统特征和基本排队过程 基本排队过程 可以用图6—6表示。从图6—6可知,每个顾客由顾客源按一定方式到达服务系统,首先加入队列排队等待接受服务,然后服务台按一定规则从队列中选择顾客进行服务,获得服务的顾客立即离开。
  • 15. (二)排队系统的基本组成部分 排队系统由3个部分组成 1、输入过程 2、服务规则 3、服务台
  • 16. 1.输入过程 这是指要求服务的顾客是按怎样的规律到达排队系统的过程,有时也把它称为顾客流。一般可以从3个方面来描述—个输入过程。 (1)顾客总体数,又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的,也可以是无限的。 (2)顾客到达方式。这是描述顾客是怎样来到系统的,是单个到达,还是成批到达。 (3)顾客流的概率分布,或称相继顾客到达的时间间隔的分布。这是求解排队系统有关运行指标问题时,首先需要确定的指标。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。
  • 17. 2.服务规则 这是指服务台从队列中选取顾客进行服务的顺序。一般可以分为损失制、等待制和混合制等3大类。 (1)损失制。这是指如果顾客到达排队系统时,所有服务台都被先到的顾客占用,那么他们就自动离开系统永不再来。
  • 18. 2.服务规则 (2)等待制 这是指当顾客来到系统时,所有服务台都不空,顾客加入排队行列等待服务。等待制中,服务台在选择顾客进行服务时常有如下四种规则: 1)先到先服务。按顾客到达的先后顺序对顾客进行服务。 2)后到先服务。 3)随机服务。即当服务台空闲时,不按照排队序列而随意指定某个顾客接受服务。 4)优先权服务。
  • 19. 2.服务规则 (3)混合制 这是等待制与损失制相结合的一种服务规则,一般是指允许排队,但又不允许队列无限长下去。具体说来,大致有三种: 1)队长有限。当排队等待服务的顾客人数超过规定数量时,后来的顾客就自动离去,另求服务,即系统的等待空间是有限的。 2)等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T,当等待时间超过T时,顾客将自动离去,并不再回来。 3)逗留时间(等待时间与服务时间之和)有限。
  • 20. 3.服务台 (1)服务台数量及构成形式。从数量上说,服务台有单服务台和多服务台之分。从构成形式上看,服务台有:①单队—-单服务台式;②单队--多服务台并联式;③多队—-多服务台并联式;④单队—-多服务台串联式;⑤单队—-多服务台并串联混合式,以及多队多服务台并串联混合式等等。 (2)服务方式。这是指在某一时刻接受服务的顾客数,它有单个服务和成批服务两种。 (3)服务时间的分布。在多数情况下,对每一个顾客的服务时间是一随机变量。
  • 21. (三)排队系统的符号表述 描述符号:①/②/③/④/⑤/⑥ 各符号的意义: ①——表示顾客相继到达间隔时间分布,常用下列符号: M——表示到达的过程为泊松过程或负指数分布; D——表示定长输入; EK——表示K阶爱尔朗分布; G——表示一般相互独立的随机分布。
  • 22. 各符号的意义: ②——表示服务时间分布,所用符号与表示顾客到达间隔时间分布相同。 ③——表示服务台(员)个数:“1”表示单个服务台,“s”(s>1)表示多个服务台。 ④——表示系统中顾客容量限额,或称等待空间容量。如系统有K个等待位子,则,0
  • 23. 各符号的意义:⑤——表示顾客源限额,分有限与无限两种,∞表示顾客源无限,一般∞也可省略不写。 ⑥——表示服务规则,常用下列符号 FCFS:表示先到先服务的排队规则; LCFS:表示后到先服务的排队规则; PR:表示优先权服务的排队规则。
  • 24. 各符号的意义: 例如,某排队问题为M/M/S/∞/∞/FCFS,则表示顾客到达间隔时间为负指数分布(泊松流);服务时间为负指数分布;有s(s>1)个服务台;系统等待空间容量无限(等待制);顾客源无限,采用先到先服务规则。 某些情况下,排队问题仅用上述表达形式中的前3个符号。例如,某排队问题为M/M/S, 如不特别说明则均理解为系统等待空间容量无限;顾客源无限,先到先服务,单个服务的等待制系统。
  • 25. 二,排队系统的主要数量指标 描述一个排队系统运行状况的主要数量指标有: 1.队长和排队长(队列长) 队长是指系统中的顾客数(排队等待的顾客数与正在接受服务的顾客数之和);排队长是指系统中正在排队等待服务的顾客数。队长和排队长一般都是随机变量。
  • 26. 二、排队系统的主要数量指标 2.等待时间和逗留时间 从顾客到达时刻起到他开始接受服务止这段时间称为等待时间。等待时间是个随机变量。从顾客到达时刻起到他接受服务完成止这段时间称为逗留时间,也是随机变量。 3. 忙期和闲期 忙期是指从顾客到达空闲着的服务机构起,到服务机构再次成为空闲止的这段时间,即服务机构连续忙的时间。这是个随机变量,是服务员最为关心的指标,因为它关系到服务员的服务强度。与忙期相对的是闲期,即服务机构连续保持空闲的时间。在排队系统中,忙期和闲期总是交替出现的。
  • 27. 二、排队系统的主要数量指标 4.数量指标的常用记号 (1)主要数量指标 L——平均队长,即稳态系统任一时刻的所有顾客数 的期望值; Lq——平均等待队长,即稳态系统任一时刻等待服务的顾客数的期望值; W——平均逗留时间,即(在任意时刻)进入稳态系统的顾客逗留时间的期望值; Wq——平均等待时间,即(在任意时刻)进入稳态系统的顾客等待时间的期望值。
  • 28. 4.数量指标的常用记号 (2)其他常用数量指标 s——系统中并联服务台的数目; λ——平均到达率; 1/λ——平均到达间隔; μ——平均服务率; 1/μ——平均服务时间; N――稳态系统任一时刻的状态(即系统中所有顾客数); U――任一顾客在稳态系统中的逗留时间; Q――任一顾客在稳态系统中的等待时间;
  • 29. (2)其他常用数量指标
  • 30. (2)其他常用数量指标ρ——服务强度,即每个服务台单位时间内的平均服务时间,—般有ρ=λ/(sμ),这是衡量排队系统繁忙程度的重要尺度,当ρ趋近于0时,表明对期望服务的数量来说,服务能力相对地说是很大的。这时,等待时间一定很短,服务台有大量的空闲时间;如服务强度ρ趋近于1,那么服务台空闲时间较少而顾客等待时间较多。我们一般都假定平均服务率μ大于平均到达率λ,即λ/μ<1,否则排队的人数会越来越多,以后总是保持这个假设而不再声明。
  • 31. 李特尔公式 在系统达到稳态时,假定平均到达率为常数λ,平均服务时间为常数1/μ,则有下面的李特尔公式: L=λ W Lq=λ Wq W= Wq +1/μ L= Lq +λ/μ
  • 32. 排队系统运行情况的分析 排队系统运行情况的分析,就是在给定输人与服务条件下,通过求解系统状态为n(有n个顾客)的概率Pn,再进行计算其主要的运行指标: ①系统中顾客数(队长)的期望值L; ②排队等待的顾客数(排队长)的期望值Lq; ③顾客在系统中全部时间(逗留时间)的期望值W; ④顾客排队等待时间的期望值Wq。
  • 33. 第二节 M/ M /1模型 模型的条件是: 1、输入过程――顾客源是无限的,顾客到达完全是随机的,单个到来,到达过程服从普阿松分布,且是平稳的; 2、排队规则――单队,且队长没有限制,先到先服务; 3、服务机构――单服务台,服务时间的长短是随机的,服从相同的指数分布 。
  • 34. 对于M/ M/1模型有如下公式:
  • 35. 例1 某医院急诊室同时只能诊治一个病人,诊治时间服从指数分布,每个病人平均需要15分钟。病人按泊松分布到达,平均每小时到达3人。试对此排队队系统进行分析。 解 对此排队队系统分析如下: (1)先确定参数值:这是单服务台系统,有: 故服务强度为:
  • 36. (2)计算稳态概率: 这就是急诊室空闲的概率,也是病人不必等待立即就能就诊的概率。 而病人需要等待的概率则为: 这也是急诊室繁忙的概率。
  • 37. (3)计算系统主要工作指标。 急诊室内外的病人平均数: 急诊室外排队等待的病人平均数: 病人在急诊室内外平均逗留时间: 病人平均等候时间:
  • 38. (4)为使病人平均逗留时间不超过半小时,那么平均服务时间应减少多少? 由于 代入λ=3,解得μ≥5,平均服务时间为: 15-12=3min 即平均服务时间至少应减少3min
  • 39. (5)若医院希望候诊的病人90% 以上都能有座位,则候诊室至少应安置多少座位? 设应该安置χ个座位,加上急诊室的一个座位,共有χ+1个。要使90% 以上的候诊病人有座位,相当于使“来诊的病人数不多于χ+1个”的概率不少于90%,即
  • 40. 两边取对数 (x+2)lgρ ≤ lg0.1 因 ρ < 1,故 所以 ⅹ≥6 即候诊室至少应安置6个座位。
  • 41. 第三节      M / M / S 模型 此模型与M/M/1模型不同之处在于有S个服务台,各服务台的工作相互独立,服务率相等,如果顾客到达时,S个服务台都忙着,则排成一队等待,先到先服务的单队模型。 整个系统的平均服务率为sμ,ρ*=λ/sμ,(ρ*<1)为该系统的服务强度。
  • 42. 1、状态概率
  • 43. 2、主要运行指标 3、系统状态N ≥S的概率
  • 44. 例2 承接例1,假设医院增强急诊室的服务能力,使其同时能诊治两个病人,且平均服务率相同,试分析该系统工作情况,并且,例1、例2的结果进行比较。 解 这相当于增加了一个服务台,故有: S=2,λ=3人/h,μ=4人/h
  • 45. 病人必须等候的概率,即系统状态N≥2的概率:
  • 46. 表6-1 两个系统的比较 指 标 S=1系统 S=2系统 P(Q>0) 0.75 0.20 Lq 2.25人 0.12人 L 3人 0.87人 W 60min 17.4min Wq 45min 2.4min
  • 47. 例3 某医院挂号室有三个窗口,就诊者的到达服从泊松分布,平均到达率为每分钟0.9人,挂号员服务时间服从指数分布,平均服务率每分钟04人,现假设就诊者到达后排成一队,依次向空闲的窗口挂号,显然系统的容量和顾客源是不限的,属于M/M/1型的排队服务模型。求:该系统的运行指标 解
  • 48. (本页无文本内容)
  • 49. (本页无文本内容)
  • 50. 如果在例3中,就诊者到达后在每个挂号窗口各自排成一队,即排成3队,且进入队列后不离开,各列间也互不串换,这就形成3个队列,而例3中的其它条件不变。假设每个队列平均到达率相等且为: λ1=λ2=λ3=0.9/3=0.3(人/分钟) 这样,原来的M/M/3系统就变成了3个M/M/1型的子系统。 现按M/M/1型计算主要运行指标,并与上面的例子进行对比分析,结果见表6-2
  • 51. 表6-2 两个模型的比较 指标 (1)M/M/3型 (2)M/M/1型 挂号间空闲 的概率 0.0748 0.25(各子系统) 就诊者必须等待的概率 P(N>3)= 0.57 0.75 平均队列长 1.7(人) 2.25(人) (各子系统) 平均队长 3.95(人) 9(人) (整个系统) 平均逗留时间 4.39(分钟) 10(分钟) 平均等待时间 1.89(分钟) 7.5(分钟)
  • 52. 练 习 1.思考题 (1)排队论主要研究的问题是什么? (2)试述排队系统的基本组成部分。 (3)理解平均到达率、平均服务率、平均服务时间和顾客到达间隔时间等概念。 (4)试述队长和排队长、等待时间和逗留时间、忙期和闲期等概念。
  • 53. 练 习 2.设有一个医院门诊,只有一个值班医生。病人的到达过程为泊松流,平均到达时间间隔为20min,诊断时间服从负指数分布,平均需12min,求: (1)病人到来不用等待的概率; (2)门诊部内顾客的平均数; (3)病人在门诊部的平均逗留时间; (4)若病人在门诊部内的平均逗留时间超过1h,则院方将考虑增加值班医生。问病人平均到达率为多少时,医院才会增加医生?
  • 54. 练 习 3.某售票处有3个售票口,顾客的到达服从泊松分布,平均每分钟到达λ= 0.9人,3个窗口售票的时间都服从负指数分布,平均每分钟卖给μ= 0.4人,设可以归纳为M/M/3模型,试求: (1)整个售票处空闲的概率; (2)平均队长; (3)平均逗留时间; (4)平均等待时间; (5)顾客到达后的等待概率。