商业服务系统：排队论

1、排队论,排队系统的基本特征,离开,排队规则,到达过程,排队结构,服务过程,退出,离开,需求群体,排队论是研究排队系统的数学理论和方法，是运筹学的一个重要分支。在日常生活中，人们会遇到各种各样的排队问题。,商业服务系统,系统类型顾客服务台 银行出纳服务人出纳 ATM机服务 人ATM机 商店收银台人收银员 管道服务阻塞的管道 管道工 机场检票处人航空公司代理人 经纪人服务人股票经纪人,内部服务系统,系统类型顾客服务台 秘书服务雇员秘书 复印服务雇员复印机 传真服务雇员传真机 物料处理系统货物物料处理单元 维护系统设备维修工人 质检站物件质检员,运输服务系统,系统类型顾客服务台 公路收费站汽车收费员

2、 卡车装货地卡车装货工人 港口卸货区轮船卸货工人 等待起飞的飞机飞机跑道 航班服务人飞机 出租车服务人出租车 电梯服务人电梯 停车场汽车停车空间,为一致起见，将服务的对象统称为“顾客”(Customer)，将提供服务的服务者称为“服务员”或“服务机构”(Server)。 千差万别的排队系统可以描述为：顾客为了得到某种服务到达系统，若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统。,随机性则是排队系统的一个普遍特点，是指顾客的到达情况（如相继到达的时间间隔）与每个顾客接受服务的时间往往事先无法确切知道，是随机的。一般，排队论所研究的排队系统中，顾客相继到达时间间隔和服务时

3、间两个量中至少有一个是随机的。因此排队论又称为随机服务系统理论。,排队系统的描述,输入过程(Input Source) 排队及排队规则(Queue and Queue discipline) 服务机制(Service Mechanism),输入过程 Input Source,输入过程说明顾客以怎样的规律到达系统。 顾客总体数或顾客源数：有限或无限 顾客的到达方式：单个或成批 顾客相继到达时间间隔的分布:,顾客相继到达时间间隔的分布,定长分布(D)：顾客相继到达时间间隔(Interarrival time)为确定的常数。如，产品通过传送带进入包装箱。,顾客相继到达时间间隔的分布,Poisson流

4、(M): 顾客相继到达时间间隔Xn 相互独立，服从负指数分布(Exponential distribution)，其密度函数为,t,a(t),0,均值,表明低于均值的较小的到达间隔时间有大的可能性.而比均值大的到达时间间隔出现的概率低.,唯一符合随机到达的到达间隔时间分布是负指数分布.,排队及排队规则,等待时间+服务时间,无限排队,损失制排队,混合制排队系统,排队,有限排队,队长有限,等待时间有限,逗留时间有限,等待制系统,排队及排队规则,服务机制,服务台数量 单个或多个 每次服务顾客的数量 单个或成批,服务机制,服务顾客的时间(Service time)分布 负指数分布M. (每个顾客接受服

5、务的时间相互独立,具有相同的负指数分布),负指数分布在大多数情况下适合到达间隔时间,但对服务时间实际上却不全是这样. 如,银行的出纳业务(有的服务时间长,有的服务时间短).这种情况采用负指数分布就显得不合适了.,服务机制,服务顾客的时间分布 定长分布D. ( 每个顾客接受服务的时间是一个确定的常数Constant Service Time). 这类分布常见于排队系统包含一系列固定顺序的操作.对于每个顾客要花费相同的时间.例如,流水线上的操作.,服务机制,k阶爱尔朗Erlang分布,每个顾客接受服务的时间服从k阶Erlang分布,设为平均服务率,其密度函数为,Erlang分布具有比指数分布更广泛

6、的应用性.当k=1时, Erlang分布为指数分布,当k趋于时, Erlang分布为定长分布 一般情况下,参数k决定了其标准差.见下表.,Erlang服务时间分布标准与均值的关系,Erlang分布为许多排队系统提供了更实际的服务时间分布.,排队系统的表示,一个排队系统的特征可以用六个参数表示： ABC：def,其中 A 顾客到达的概率分布，可取M、D、Ek等； B 服务时间的概率分布，可取M、D、Ek等； C 服务台个数，取正整数； d 排队系统的最大容量，可取正整数或； e 顾客源的最大容量，可取正整数或； f 排队规则，可取FCFS、LCFS等。,排队系统的符号表示,M/M/1：/FCFS

7、 表示： 顾客到达的时间间隔是负指数分布 服务时间是负指数分布 一个服务台 排队系统和顾客源的容量都是无限 实行先到先服务的一个服务系统,排队系统的主要数量指标和记号,研究排队系统的目的是通过了解系统运行的状况,对系统进行调整和控制,使系统处于最优运行状态. 首先需要了解系统的运行状况.描述一个排队系统运行状况的主要数量指标:,排队系统的主要数量指标和记号,平均队长 N (Mean Number of customers in the system) 平均排队长 Nq(Mean Number of customers in the queue) 平均逗留时间 W（Mean Waiting ti

8、me in the system） 平均等待时间 Wq （Mean Waiting time in the queue）,排队系统的主要数量指标和记号,忙期B(服务机构连续忙碌的时间), 这一指标决定了服务人员的服务强度. 闲期 I(服务机构连续保持空闲的时间),忙期与闲期交替出现. n:当系统处于状态n时，新来顾客的平均到达率（即单位时间内来到系统的平均顾客数） n:当系统处于状态n时，整个系统的平均服务率，即单位时间内可以服务完的顾客数）,排队论研究的基本问题,对于排队系统,一般研究系统达到统计平衡状态下有关指标的概率规律.即研究的是系统的整体性质,再进一步探讨系统的优化问题.,生灭过程和

9、Poisson过程,在排队论模型中，以“生灭过程”(Birth-and-Death)模拟顾客到达与离去的随机发生过程。 在排队论中，如果N(t)表示时刻t系统中的顾客数，则N(t),t0就构成了一个随机过程。如果用“生”表示顾客的到达，“灭”表示顾客的离去，则对许多排队过程来说，N(t), t0就是一类特殊的随机过程 - 生灭过程。,生灭过程和Poisson过程,定义: 设N(t),t为一个随机过程.若N(t)的概率分布具有以下的性质: 假设N(t) = n,则从时刻t起到下一个顾客到达时刻止的时间服从参数为n的负指数分布,n=0,1,2 假设N(t) = n,则从时刻t起到下一个顾客离去时刻

10、止的时间服从参数为n的负指数分布,n=0,1,2 同一时刻只有一个顾客到达或离去. 则称N(t),t0为一个生灭过程.,生灭过程和Poisson过程,当系统运行相当时间而达到平稳状态后，对任意一状态n来说，单位时间内进入该状态的平均次数和单位时间内离开该状态的平均次数应该相等，这就是系统在统计平衡下的“流入=流出”原理(Rate In = Rate Out Principle)。根据这一原理，可得到任一状态下的平衡方程(Balance equation)。,生灭过程和Poisson过程,一般情况，我们寻求的是当系统到达平衡状态后的转态分布，记 pn, n = 0, 1, 2.为处于不同状态下的

11、概率。 n为状态n下的顾客的平均达到率, n为状态n下的顾客服务率.,生灭过程和Poisson过程,生灭过程和Poisson过程,由平衡方程进一步计算求得平衡状态的分布为,由概率分布的要求，,队列中无人的概率,生灭过程和Poisson过程,进一步求出系统中的顾客总数的期望值N(平均队长)及队列中等待的顾客总数的期望值Nq(平均排队长),服务台的个数,生灭过程和Poisson过程,进一步算出平均等待时间和逗留时间W,Wq, 其中为平均到达率.,基本排队模型 M/M/1:/FCFS,顾客到达的时间间隔是负指数分布 服务时间是负指数分布 一个服务台s=1 排队系统和顾客源的容量都是无限 实行先到先服

12、务的一个服务系统,M/M/1:/FCFS的状态转移分析,稳定状态下的状态概率,得到,令 称为服务强度，则,是系统中至少有一个顾客的概率,也就是服务台处于忙状态下的概率,因而称为服务强度,反映了系统的繁忙程度.另外, 1的条件下才能使系统达到统计平衡.若,则平均到达率超过平均服务率,排队队长会增加至无限.,M/M/1:/FCFS的系统指标,系统中的平均顾客数N,M/M/1:/FCFS的系统指标,队列中的平均顾客数Nq,M/M/1:/FCFS的系统指标,平均逗留时间W,平均等待时间Wq,M/M/1:/FCFS的系统指标,顾客在系统中的逗留时间w,可说明它服从参数为-的负指数分布*,即 P w t

13、= e -(-)t t 0,顾客在系统中的等待时间Wq,有 P wq t = e -(-)t t 0,M/M/s:/FCFS模型,顾客到达后，进入队列尾端；当某一个服务台空闲时，队列中的第一个顾客即到该服务台接收服务；服务完毕后随即离去。各服务台互相独立且服务速率相同，即1=2=s,分析,系统的服务速率与系统中的顾客数有关。当系统中的顾客数k不大于服务台个数，即1ks时，系统中的顾客全部在服务台中，这时系统的服务速率为k；当系统中的顾客数ks时，服务台中正在接受服务的顾客数仍为s个，其余顾客在队列中等待服务，这时系统的服务速率为s。,则当s1时系统才不会排成无限的队列,状态转移图与状态转移方程

14、,对状态0:P0=P1 对状态1:P0+2P2=(+)P1 对状态s：Ps-1+sPs+1=(+s)Ps 对状态nPn-1+sPn+1=(+s)Pn,状态概率,根据,M/M/s:/FCFS模型,Pn为平衡条件下系统中顾客数为n的概率,当ns时,即系统中顾客数大于或等于服务台个数,这时再来的顾客必须等待,因此记为,运行指标,M/G/1排队模型,顾客到达为Poisson流(平均到达率为) 单服务台 服务时间为一般分布的排队系统 (服务时间的均值为1/,方差为2) 当= / 1时,系统可达到平衡,有以下结果:,M/G/1排队模型,Nq, N, W, Wq等依赖于和服务时间的方差2, 与分布的类型没有

15、关系.当给定后,方差2减少时,平均队长和等待时间都将减少.因此可以通过改变服务时间的方差来缩短平均队长.当且仅当2=0,即服务时间为定长时,平均队长可减少到最少的水平.,排队论的案例研究,Dupit公司的售后服务问题 背景: Dupit公司是一家生产办公复印机的企业,该公司一向以良好的服务获得客户声誉.为此公司非常重视售后服务部门的工作状态. 公司目前有10,000(年总薪金约为6亿美圆)的技术服务代表,承担设备的售后维护,每个服务代表负责一个区域,这使公司能够提供个性化的服务.,排队论的案例研究,Dupit公司的售后服务问题 服务现状: 每位服务代表的服务区域内约有150台设备,使其在大约7

16、5%的时间里处于维修状态.当连续工作时,每个技术代表应能够平均一天修4台设备(2小时/台).为了使顾客的等待时间最短,每个工作日平均要接到3个维修电话.,排队论的案例研究,Dupit公司的售后服务问题 问题: 公司推出了新产品,十分畅销.但销售量增加的同时, 客户的服务要求也提高了.反映在客户平均等待时间这一指标上,以前是6小时.而现在更多的客户表示等待时间太长了, 抱怨不断.为了保持公司的声誉,公司决定准备制定新的服务水平标准(顾客的平均等待时间不超过2小时), 从而提高服务质量.,排队论的案例研究,Dupit公司的售后服务问题 具体的举措: 为达到新的服务标准,提出了四个可选方案. 1.降

17、低服务代表的工作强度,这涉及简单地减少每个代表负责的设备台数及增加技术代表的数量.从而提高服务水平,满足市场新需求.,排队论的案例研究,Dupit公司的售后服务问题 具体的举措: 2.为每个代表配备新装备,提高工作效率,缩短平均维修时间.尽管增加的成本不低,但可以有效减少维修的平均等待时间.,排队论的案例研究,Dupit公司的售后服务问题 具体的举措: 3.将单个技术服务代表负责的区域转变为较大区域,由多个技术服务代表提供服务.在忙的时候通过团队的支持可以大大缩短平均维修等待的时间而无需雇用新的代表.,排队论的案例研究,Dupit公司的售后服务问题 具体的举措: 4. 授予拥有新产品的客户优先

18、服务权.因为对服务不满的抱怨主要来自于这类客户.这个做法可能可以带给他们所需的服务并能满足其它客户的要求.,排队论的案例研究,Dupit公司的售后服务问题 研究分析:分析比较这四个方案, 哪一种最为经济可行?,排队论的案例研究,排队论是分析该问题的关键技术, 建立Dupit公司的售后服务的排队系统: 1.顾客: 需要维修的设备 2.顾客到达: 打给每个代表要求维修的电话 3.队列: 等待修理的设备 4.服务者: 技术服务代表 5.服务时间: 花在设备维修上的时间,排队论的案例研究,分析: 技术服务代表平均每天接到3个电话, 因此平均到达率 = 3. 每个修理任务2小时,按一天8小时工作时算,

19、平均服务率 = 8/2 = 4. 即平均每天维修4台复印设备. 服务强度 = / = 75% 一次维修一台设备,因此s = 1.,排队论的案例研究,假设: 顾客到达(打电话要求维修)是随机发生的, 符合负指数分布,平均到达的时间间隔为1/. 假设服务时间也符合负指数分布,平均服务率为. 该排队系统的模型设为M / M / 1,.案例案例(杜皮特公司问题).xls,建立该问题的Excel求解模型,结果分析,.在该系统中平均需要维修N=3台设备 .等待维修的设备平均数为Nq = 2.25台 .设备从报修到维修完毕平均需要W = 1天时间 .设备从保修到维修前平均需要Wq =0.75天，按小时工作制

20、度， Wq = 6 小时 5P0 = 0.25,即系统中没有等待维修的设备的概率说明服务代表大约一天中有6个小时忙，2个小时空闲即其服务强度为75%. 6P0+P1+P2 = 58%. 即技术代表在超过一半的时间中不会有多于2台设备要维修.,排队论的案例研究,结果分析： 7有的时候技术代表会很忙,因为P0+P1+P7 = 0.9,即在系统中有至少8台设备等待维修的概率占到10%,这大概是两天或更多的工作量.说明,虽然服务人员的工作强度达到了75%, 也会偶然出现大量的积压现象,导致顾客的不满.,排队论的案例研究,8. 由P(w 1) = 0.368可知顾客在损坏的设备能够继续工作之前需要等待超

21、过一天的概率为36.8%. 9. 由P(wq1) = 0.276可知在维修前需要等待超过一天的概率为27.6%. 这些结果说明, 顾客需要等待超过1天才能使设备得以维修的概率占到30%左右.这也就是为什么顾客抱怨不断,服务质量下降的主要原因了.,方案1 降低服务代表的工作强度,这涉及简单地减少每个代表负责的设备台数及增加技术代表的数量. 分析: 按原标准, 服务代表负责区域150台设备.若每一台设备每50个工作日修理一次,则平均到达率为 = 150/50 = 3. 现负责的设备台数降低至100台,则新标准下 = 100/50 = 2, 若服务率不变=4, 则服务强度 = /=50%,方案1 将

22、M/M/1模型应用于方案1,计算,方案1 分析: 1. 服务代表的服务强度降至50%,使顾客的平均等待时间达到0.25天(约2小时). 顾客需要等待1天方能得到维修的概率降至6.7%. 可见,降低服务代表的工作强度能够很好地满足新标准.,方案1 分析: 2. 降低服务代表的服务强度意味着需要增加新雇员约5000名. 工资成本=2.7亿, 管理培训及设施配备所需费用=0.3亿. 总成本=3亿. 总结: 方案1可很好地满足新标准的要求,增加成本3亿元.,方案2为每个代表配备新装备,提高工作效率,缩短平均维修时间.,分析: 提高工作效率意味着降低平均服务时间经过分析，服务时间建议均值1/由1/4降至

23、1/5天，标准差建议从1/4天降低到1/10天将M/G/1模型应用于该方案,方案2 M/G/1模型的Excel模板,M/M/1模型 1/=1/4,方案2 M/G/1模型的Excel模板,分析: 采用M/M/1模型，均值1/由1/4降至1/5可使得Wq = 0.3. 进一步的降低标准差从1/4减至1/10, 得Wq = 0.188。可见，从目前政策下的Wq =0.75降至0.188归功于均值与标准差 （服务时间的波动）的大大下降该方案能够满足新的标准Wq0.25.,方案2 增加的成本: 为每个技术服务代表提供价值万美圆的新装备，一次性总成本投资亿圆 总结: 方案2可很好地满足新标准的要求,但需增

24、加成本5亿元.,方案3将单个技术服务代表负责的区域转变为较大区域,由多个技术服务代表提供服务.在忙的时候通过团队的支持可以大大缩短平均维修等待的时间而无需雇用新的代表. 分析: 合并服务区域,同时服务代表以小组形式提供维修服务. 排队模型为M/M/s, 分别取s=2或3, 比较结果.,方案3,S =2, 将两个区域合并为一个大区域, 则平均达到率 = 2*3 = 6, 平均服务率 仍为4, 但服务强度为=/s = 0.75,方案3,S =3, 将三个区域合并为一个大区域, 则平均达到率 = 3*3 = 9, 平均服务率 仍为4, 服务强度仍为为=/s = 0.75.,方案3杜皮特公司问题不同大小区域对应Wq值的比较.,方案3 分析: 结果表明通过合并区域的做法,可以有效地降低平均等待时间. 当取s=3时间,甚至可达到wq = 0.189天(1.512 小时),不到两个小时的等待时间. 且无需更多的成本.,方案3 分析: 然而,增大区域的做法也有不足之处 (1)增大区域使技术服务代表将花费更多的时间在前往维修的途中, 因此平均服务时间1/将产生变化,即服务率可能会有所下降. (2)区域合并导致技术服务代表间的协调更加困