又称随机服务系统理论课件.ppt

1、Chapter 14.Queuing Models第十四章第十四章.排队模型排队模型运筹学运筹学排队模型排队模型Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 2现实生活中的排队模型现实生活中的排队模型BankAirportHospitalRoadManufacturingHotelRestaurantWC运筹学运筹学排队模型排队模型Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 3排队模型存在的问题排队模型存在的问题如何以最经济的方式控制排队如何以最经济的方式控制排队系统，使其达到特定的要求？系统，使其达到特定的要求？提供过多的服务

2、能力来控制排提供过多的服务能力来控制排队系统将会造成过量的成本队系统将会造成过量的成本提供的服务能力不足将会导致提供的服务能力不足将会导致过多的等待，降低顾客满意度过多的等待，降低顾客满意度并造成顾客流失，减少收益并造成顾客流失，减少收益Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 4什么是排队论什么是排队论Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 5什么是排队论什么是排队论Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 6a BasiC Queuing systeMCopyright 2007

3、深圳大学管理学院深圳大学管理学院 运筹学运筹学 7排队系统的描述排队系统的描述涉及的要素涉及的要素顾客顾客队列队列服务台服务台到达间隔时间到达间隔时间服务时间服务时间排队规则排队规则运筹学运筹学排队模型排队模型Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 8排队系统的描述排队系统的描述绩效测度绩效测度等待顾客数等待顾客数顾客等待时间顾客等待时间服务台忙期服务台忙期服务台闲期服务台闲期服务台利用率服务台利用率运筹学运筹学排队模型排队模型Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 9taBle of Contents(主要内容)El

4、ements of a Queuing Model(Section 14.1)(排队模型的要素)Some Examples of Queuing Systems(Section 14.2)(排队系统的一些实例)Measures of Performance for Queuing Systems(Section 14.3)(排队系统的绩效测度)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 10taBle of Contents(主要内容)A Case Study:The Dupit Corp.Problem(Section 14.4)(案例研究：杜皮特公司问题)

5、Some Single-Server Queuing Models(Section 14.5)(一些单服务台排队模型)Some Multiple-Server Queuing Models(Section 14.6)(一些多服务排队模型)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 11taBle of Contents(主要内容)Priority Queuing Models(Section 14.7)(有优先权的排队模型)Some Insights about Designing Queuing Systems(Section 14.8)(关于设计排队系统的

6、一些启示)Economic Analysis of the Number of Servers to Provide(Section 14.9)(服务台数量的经济分析)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 12herr Cutters BarBer shopHerr Cutter is a German barber who runs a one-man barber shop.(赫尔卡特先生是一个德国理发师，开了一家单人理发店)Herr Cutter opens his shop at 8:00 A.M.(赫尔卡特每天早上8点开始工作)The tabl

7、e shows his queuing system in action over a typical morning.(下表显示了一个典型的上午排队系统情况)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 13herr Cutters BarBer shopCopyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 14arrivals(到达)The time between consecutive arrivals to a queuing system are called the interarrival times.(连续两个顾客到达排

8、队系统的时间间隔称为到达间隔时间)The expected number of arrivals per unit time is referred to as the mean arrival rate.(单位时间到达的期望数量称为平均到达率)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 15arrivals(到达)The symbol used for the mean arrival rate is(平均到达率的符号如下)The mean of the probability distribution of interarrival times is(间隔

9、时间的概率分布均值是)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 16arrivals(到达)Most queuing models assume that the form of the probability distribution of interarrival times is an exponential distribution.(大多数排队模型假设到达间隔时间的概率分布形式是指数分布)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 17evolution of the nuMBer of CustoMersCopy

10、right 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 18The Exponential Distribution for Interarrival TimesCopyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 19There is a high likelihood of small interarrival times,but a small chance of a very large interarrival time.This is characteristic of interarrival times in practice.(小间隔时间

11、出现的可能性很大，而大间隔时间出现的机会则很小，这个间隔时间的特征能在实践中观察到)properties of the exponential distriButionCopyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 20指数分布指数分布到达间隔时间服从指数分布则到达到达间隔时间服从指数分布则到达过程服从泊松分布过程服从泊松分布Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 21泊松分布泊松分布Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 22For most queuing systems,the se

12、rvers have no control over when customers will arrive.Customers generally arrive randomly.(对于大多数排队系统，服务台无法控制顾客何时到达，顾客的到达一般是随机的)properties of the exponential distriButionCopyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 23Having random arrivals means that interarrival times are completely unpredictable,in the s

13、ense that the chance of an arrival in the next minute is always just the same.(随机到达意味着到达时间完全是不可预测的，下一分钟有顾客到达的概率和其他分钟相同)properties of the exponential distriButionCopyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 24The only probability distribution with this property of random arrivals is the exponential distrib

14、ution.(唯一符合随机到达的到达间隔时间分布是指数分布)The fact that the probability of an arrival in the next minute is completely uninfluenced by when the last arrival occurred is called the lack-of-memory property.(下一分钟到达的概率完全不受上一次到达的影响的事实称为无记忆性)properties of the exponential distriButionCopyright 2007 深圳大学管理学院深圳大学管理学院 运筹

15、学运筹学 25The number of customers in the queue(or queue size)is the number of customers waiting for service to begin.(队列中的顾客数也称队列大小或队列长度，是等候服务的顾客数量)The number of customers in the system is the number in the queue plus the number currently being served.(系统中的顾客数是队列中的顾客数加上正在接受服务的顾客数量)the Queue(队列)Copyrigh

16、t 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 26The queue capacity is the maximum number of customers that can be held in the queue.(队列容量是队列所能容纳的最大顾客数量)An infinite queue is one in which,for all practical purposes,an unlimited number of customers can be held there.(无限队列是为了应用方便，可以容纳无限顾客数量的队列)the Queue(队列)Copyright 2

17、007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 27When the capacity is small enough that it needs to be taken into account,then the queue is called a finite queue.(当容量很小，需要将其考虑在内时，这个队列就称为有限队列)the Queue(队列)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 28The queue discipline refers to the order in which members of the queue are

18、 selected to begin service.(排队规则指选择队列中的成员接受服务的顺序)lThe most common is first-come,first-served(FCFS).(最普通的排队规则是先到先服务)lOther possibilities include random selection,some priority procedure,or even last-come,first-served.(其他的可能规则包括随机选择、有优先权的服务甚至后到先服务)the Queue(队列)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 29

19、When a customer enters service,the elapsed time from the beginning to the end of the service is referred to as the service time.(当一个顾客接受服务时，从服务开始到服务结束经过的时间称为服务时间)Basic queuing models assume that the service time has a particular probability distribution.(基本的排队模型假设服务时间是一个特定的概率分布)serviCe(服务)Copyright

20、2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 30The symbol used for the mean of the service time distribution is(用于表示服务时间分布均值的符号是)serviCe(服务)The interpretation of itself is the mean service rate.(就是平均服务率就是平均服务率)=Expected service completions per unit time for a single busy server(一个连续工作的服务台单位时间完成的服务量的期望值)Copyright 20

21、07 深圳大学管理学院深圳大学管理学院 运筹学运筹学 31soMe serviCe-tiMe distriButionsExponential Distribution(指数分布)The most popular choice.(最常用的分布形式)Much easier to analyze than any other.(比其它分布更容易分析)Although it provides a good fit for interarrival times,this is much less true for service times.(尽管指数分布很适合描述到达间隔时间，但是却不太符合服务时间

22、的特点)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 32soMe serviCe-tiMe distriButionsProvides a better fit when the service provided is random than if it involves a fixed set of tasks.(服务是随机时，指数分布比较适合；服务包含一系列固定任务时，指数分布不太适合)Standard deviation:s s=Mean(标准差等于均值)Constant Service Times(固定服务时间)A better fit for sys

23、tems that involve a fixed set of tasks.(更适合于包含一系列固定任务的系统)Standard deviation(标准差):s s=0.Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 33soMe serviCe-tiMe distriButionsErlang Distribution(爱尔朗分布)Fills the middle ground between the exponential distribution and constant.(服务时间的波动量介于指数分布和常量之间)Has a shape paramete

24、r,k that determines the standard deviation.(有一个形状参数k决定其标准差)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 34爱尔郎分布爱尔郎分布Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 35erlang distriBution(爱尔朗分布)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 36standard deviation and Mean for distriButionsCopyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹

25、学 37laBels for Queuing ModelsTo identify which probability distribution is being assumed for service times(and for interarrival times),a queuing model conventionally is labeled as follows:(为了表示服务时间以及到达间隔时间服从什么概率分布，基本排队系统的排队模型通常用如下的符号表示)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 38laBels for Queuing Mode

26、lsThe symbols used for the possible distributions are(用于表示可能的分布的符号是)M=Exponential distribution(Markovian)指数分布(马尔科夫)D=Degenerate distribution(constant times)退化分布(固定时间)运筹学运筹学排队模型排队模型Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 39laBels for Queuing ModelsEk=Erlang distribution(shape parameter=k)(爱尔朗分布形态参数=k)

27、GI=General independent interarrival-time distribution(any distribution)(独立的到达间隔时间的一般分布允许任意类型的分布)G=General service-time distribution(any arbitrary distribution)(服务时间的一般分布允许任意类型的分布)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 40suMMary of usual Model assuMptions1.Interarrival times are independent and ident

28、ically distributed according to a specified probability distribution.(到达间隔时间独立同分布)2.All arriving customers enter the queuing system and remain there until service has been completed.(所有到达的顾客都进入排队系统，并待在那里直到服务结束)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 41suMMary of usual Model assuMptions3.The queuing s

29、ystem has a single infinite queue,so that the queue will hold an unlimited number of customers(for all practical purposes).(排队系统有一个无限队列，因此队列将可以容纳无限量的顾客出于应用的原因)4.The queue discipline is first-come,first-served.(排队规则是先到先服务)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 42suMMary of usual Model assuMptions5.Th

30、e queuing system has a specified number of servers,where each server is capable of serving any of the customers.(排队系统拥有特定数量的服务台，每一个服务台能够为任意一位顾客提供服务)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 43suMMary of usual Model assuMptions6.Each customer is served individually by any one of the servers.(每一位顾客由一个服务台

31、单独提供服务)7.Service times are independent and identically distributed according to a specified probability distribution.(服务时间是独立的，服从特定的概率分布)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 44Examples of Commercial Service Systems that Are Queuing SystemsCopyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 45Examples of Intern

32、al Service Systems That Are Queuing SystemsCopyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 46Examples of Transportation Service Systems That Are Queuing SystemsCopyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 47Choosing a Measure of perforManCeManagers who oversee queuing systems are mainly concerned with two measures

33、 of performance:(检查排队系统的管理人员主要考虑两种绩效测度)How many customers typically are waiting in the queuing system?(排队系统中有多少顾客在等待)How long do these customers typically have to wait?(这些顾客要等待多少时间)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 48Choosing a Measure of perforManCeWhen customers are internal to the organizati

34、on,the first measure tends to be more important.(当顾客是提供服务的组织内部服务系统的内部顾客时，第一个测度比较重要)Having such customers wait causes lost productivity.(让内部服务系统的顾客等待会导致损失生产力)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 49Choosing a Measure of perforManCeCommercial service systems tend to place greater importance on the se

35、cond measure.(商业服务系统外部顾客接受商业组织的服务会认为第二个测度更加重要)Outside customers are typically more concerned with how long they have to wait than with how many customers are there.(比起已经有多少顾客在等待，顾客更关心他们会等待多久)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 50defining the Measures of perforManCeL=Expected number of customers i

36、n the system,including those being served(the symbol L comes from Line Length).Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 51defining the Measures of perforManCeLq=Expected number of customers in the queue,which excludes customers being served.Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 52defining the Measure

37、s of perforManCeW=Expected waiting time in the system(including service time)for an individual customer(the symbol W comes from Waiting time).Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 53defining the Measures of perforManCeWq=Expected waiting time in the queue(excludes service time)for an individual cus

38、tomer.Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 54defining the Measures of perforManCeThese definitions assume that the queuing system is in a steady-state condition.(这些定义假设排队系统处于平稳条件中)运筹学运筹学排队模型排队模型Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 55Relationship between L,W,Lq and Wq并且知其一即知其四Copyright 2007 深圳大学管

39、理学院深圳大学管理学院 运筹学运筹学 56Using Probabilities as Measures of PerformanceIn addition to knowing what happens on the average,we may also be interested in worst-case scenarios.(除除了知道系统性能指标的各种平均值之了知道系统性能指标的各种平均值之外，我们还可能对最坏情况感兴趣外，我们还可能对最坏情况感兴趣)lWhat will be the maximum number of customers in the system?(Excee

40、ded no more than,say,5%of the time.)(在在95%的时间里，系统的最大顾客数不会超过的时间里，系统的最大顾客数不会超过某个值某个值?)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 57Using Probabilities as Measures of PerformancelWhat will be the maximum waiting time of customers in the system?(Exceeded no more than,say,5%of the time.)(在在95%的时间里，系统的顾客最大等待时

41、间不的时间里，系统的顾客最大等待时间不会超过某个值会超过某个值?)Statistics that are helpful to answer these types of questions are available for some queuing systems(统计手段在统计手段在回答这类问题时非常有用，因此它也回答这类问题时非常有用，因此它也可用于一些排队系统中可用于一些排队系统中):Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 58Using Probabilities as Measures of Performance Pn=Steady-sta

42、te probability of having exactly n customers in the system.(在在系统中有系统中有n个顾客的平稳概率个顾客的平稳概率)P(W t)=Probability the time spent in the system will be no more than t.(在系统中的时间消耗不超过在系统中的时间消耗不超过t的概率的概率)P(Wq t)=Probability the wait time will be no more than t.(等待时间不超等待时间不超过过t的概率的概率)Copyright 2007 深圳大学管理学院深圳大学管

43、理学院 运筹学运筹学 59Using Probabilities as Measures of PerformanceExamples of common goals(常用目常用目标的一些例子标的一些例子):lNo more than three customers 95%of the time:P0+P1+P2+P3 0.95(在在95%的时间里系统中的顾客数不的时间里系统中的顾客数不超过超过3个个)lNo more than 5%of customers wait more than 2 hours:P(W 2 hours)0.95(等待时间超过等待时间超过2小时的顾客数不小时的顾客数不超

44、过总顾客数的超过总顾客数的5%)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 60the dupit Corp.proBleMThe Dupit Corporation is a longtime leader in the office photocopier marketplace.Dupits service division is responsible for providing support to the customers by promptly repairing the machines when needed.This is done by

45、 the companys service technical representatives,or tech reps.Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 61the dupit Corp.proBleM杜皮特公司在办公复印机市场上长期处于领导地位杜皮特公司的服务部门负责为公司的顾客提供高质量的服务支持，在需要的时候维修公司的设备。这项工作由公司的技术服务代表完成Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 62the dupit Corp.proBleMCurrent policy:Each tech reps te

46、rritory is assigned enough machines so that the tech rep will be active repairing machines(or traveling to the site)75%of the time.lA repair call averages 2 hours,so this corresponds to 3 repair calls per day.lMachines average 50 workdays between repairs,so assign 150 machines per rep.Copyright 2007

47、 深圳大学管理学院深圳大学管理学院 运筹学运筹学 63the dupit Corp.proBleM目前的政策：每一位技术服务代表的地域应当有足够多的机器设备，使得技术服务代表在75%的时间里都处于维修工作状态(或在前往维修地点的路上)l每台设备的平均维修时间是2小时，一天平均要接到3个维修电话l机器平均50个工作日需要维修一次，因此为每位技术服务代表分配150台机器Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 64目前存在的问题目前存在的问题刚买了一款新式彩色打印-复印机，现在出了问题，等了这么久还没有人来维修，服务水平太差了，我要投诉！Copyright 20

48、07 深圳大学管理学院深圳大学管理学院 运筹学运筹学 65the dupit Corp.proBleMProposed New Service Standard:The average waiting time before a tech rep begins the trip to the customer site should not exceed two hours.(建议的新服务标准：在技术服务代表开始前往顾客所在地修理设备之前，顾客的平均等待时间不应超过两个小时)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 66alternative approaC

49、hes to the proBleMApproach Suggested by John Phixitt:Modify the current policy by decreasing the percentage of time that tech reps are expected to be repairing machines.(约翰建议的做法：修改目前的政策，降低期望技术服务代表进行维修工作的时间百分比。减少分配数量，增加服务代表)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 67alternative approaChes to the proBle

50、MApproach Suggested by the Vice President for Engineering:Provide new equipment to tech reps that would reduce the time required for repairs.(工程副总裁建议的做法：为技术服务代表提供新的装备，以减少设备修理时间)Copyright 2007 深圳大学管理学院深圳大学管理学院 运筹学运筹学 68alternative approaChes to the proBleMApproach Suggested by the Chief Financial Off