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

Chapter 14.Queuing Models,第十四章.排队模型,运筹学排队模型,现实生活中的排队模型,BankAirportHospitalRoadManufacturingHotelRestaurantWC,运筹学排队模型,排队模型存在的问题,如何以最经济的方式控制排队系统，使其达到特定的要求？提供过多的服务能力来控制排队系统将会造成过量的成本提供的服务能力不足将会导致过多的等待，降低顾客满意度并造成顾客流失，减少收益,什么是排队论,什么是排队论?,什么是排队论,排队论是研究排队系统的理论，又称随机服务系统理论，它提供了很多不同的排队模型，通过这些排队模型能够找到服务成本和服务水平之间较好的平衡。,A Basic Queuing System,排队系统的描述,涉及的要素顾客队列服务台到达间隔时间服务时间排队规则,运筹学排队模型,排队系统的描述,绩效测度等待顾客数顾客等待时间服务台忙期服务台闲期服务台利用率,运筹学排队模型,Table of Contents(主要内容),Elements of a Queuing Model(Section 14.1)(排队模型的要素)Some Examples of Queuing Systems(Section 14.2)(排队系统的一些实例)Measures of Performance for Queuing Systems(Section 14.3)(排队系统的绩效测度),Table of Contents(主要内容),A Case Study:The Dupit Corp.Problem(Section 14.4)(案例研究：杜皮特公司问题)Some Single-Server Queuing Models(Section 14.5)(一些单服务台排队模型)Some Multiple-Server Queuing Models(Section 14.6)(一些多服务排队模型),Table of Contents(主要内容),Priority Queuing Models(Section 14.7)(有优先权的排队模型)Some Insights about Designing Queuing Systems(Section 14.8)(关于设计排队系统的一些启示)Economic Analysis of the Number of Servers to Provide(Section 14.9)(服务台数量的经济分析),Herr Cutters Barber Shop,Herr Cutter is a German barber who runs a one-man barber shop.(赫尔卡特先生是一个德国理发师，开了一家单人理发店)Herr Cutter opens his shop at 8:00 A.M.(赫尔卡特每天早上8点开始工作)The table shows his queuing system in action over a typical morning.(下表显示了一个典型的上午排队系统情况),Herr Cutters Barber Shop,Arrivals(到达),The time between consecutive arrivals to a queuing system are called the interarrival times.(连续两个顾客到达排队系统的时间间隔称为到达间隔时间)The expected number of arrivals per unit time is referred to as the mean arrival rate.(单位时间到达的期望数量称为平均到达率),Arrivals(到达),The symbol used for the mean arrival rate is(平均到达率的符号如下),The mean of the probability distribution of interarrival times is(间隔时间的概率分布均值是),Arrivals(到达),Most queuing models assume that the form of the probability distribution of interarrival times is an exponential distribution.(大多数排队模型假设到达间隔时间的概率分布形式是指数分布),Evolution of the Number of Customers,The Exponential Distribution for Interarrival Times,There 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.(小间隔时间出现的可能性很大，而大间隔时间出现的机会则很小，这个间隔时间的特征能在实践中观察到),Properties of the Exponential Distribution,指数分布,到达间隔时间服从指数分布则到达过程服从泊松分布,泊松分布,For most queuing systems,the servers have no control over when customers will arrive.Customers generally arrive randomly.(对于大多数排队系统，服务台无法控制顾客何时到达，顾客的到达一般是随机的),Properties of the Exponential Distribution,Having random arrivals means that interarrival times are completely unpredictable,in the sense that the chance of an arrival in the next minute is always just the same.(随机到达意味着到达时间完全是不可预测的，下一分钟有顾客到达的概率和其他分钟相同),Properties of the Exponential Distribution,The only probability distribution with this property of random arrivals is the exponential distribution.(唯一符合随机到达的到达间隔时间分布是指数分布)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 Distribution,The 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(队列),The 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(队列),When the capacity is small enough that it needs to be taken into account,then the queue is called a finite queue.(当容量很小，需要将其考虑在内时，这个队列就称为有限队列),The Queue(队列),The queue disciplinerefers to the order in which members of the queue are selected to begin service.(排队规则指选择队列中的成员接受服务的顺序)The most common is first-come,first-served(FCFS).(最普通的排队规则是先到先服务)Other possibilities include random selection,some priority procedure,or even last-come,first-served.(其他的可能规则包括随机选择、有优先权的服务甚至后到先服务),The Queue(队列),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(服务),The 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(一个连续工作的服务台单位时间完成的服务量的期望值),Some Service-Time Distributions,Exponential 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.(尽管指数分布很适合描述到达间隔时间，但是却不太符合服务时间的特点),Some Service-Time Distributions,Provides a better fit when the service provided is random than if it involves a fixed set of tasks.(服务是随机时，指数分布比较适合；服务包含一系列固定任务时，指数分布不太适合)Standard deviation:s=Mean(标准差等于均值)Constant Service Times(固定服务时间)A better fit for systems that involve a fixed set of tasks.(更适合于包含一系列固定任务的系统)Standard deviation(标准差):s=0.,Some Service-Time Distributions,Erlang Distribution(爱尔朗分布)Fills the middle ground between the exponential distribution and constant.(服务时间的波动量介于指数分布和常量之间)Has a shape parameter,k that determines the standard deviation.(有一个形状参数k决定其标准差),爱尔郎分布,Erlang Distribution(爱尔朗分布),Standard Deviation and Mean for Distributions,Labels for Queuing Models,To identify which probability distribution is being assumed for service times(and for interarrival times),a queuing model conventionally is labeled as follows:(为了表示服务时间以及到达间隔时间服从什么概率分布，基本排队系统的排队模型通常用如下的符号表示),Labels for Queuing Models,The symbols used for the possible distributions are(用于表示可能的分布的符号是)M=Exponential distribution(Markovian)指数分布(马尔科夫)D=Degenerate distribution(constant times)退化分布(固定时间),运筹学排队模型,Labels for Queuing Models,Ek=Erlang distribution(shape parameter=k)(爱尔朗分布形态参数=k)GI=General independent interarrival-time distribution(any distribution)(独立的到达间隔时间的一般分布允许任意类型的分布)G=General service-time distribution(any arbitrary distribution)(服务时间的一般分布允许任意类型的分布),Summary of Usual Model Assumptions,Interarrival times are independent and identically distributed according to a specified probability distribution.(到达间隔时间独立同分布)All arriving customers enter the queuing system and remain there until service has been completed.(所有到达的顾客都进入排队系统，并待在那里直到服务结束),Summary of Usual Model Assumptions,The queuing system has a single infinite queue,so that the queue will hold an unlimited number of customers(for all practical purposes).(排队系统有一个无限队列，因此队列将可以容纳无限量的顾客出于应用的原因)The queue discipline is first-come,first-served.(排队规则是先到先服务),Summary of Usual Model Assumptions,The queuing system has a specified number of servers,where each server is capable of serving any of the customers.(排队系统拥有特定数量的服务台，每一个服务台能够为任意一位顾客提供服务),Summary of Usual Model Assumptions,Each customer is served individually by any one of the servers.(每一位顾客由一个服务台单独提供服务)Service times are independent and identically distributed according to a specified probability distribution.(服务时间是独立的，服从特定的概率分布),Examples of Commercial Service Systems that Are Queuing Systems,Examples of Internal Service Systems That Are Queuing Systems,Examples of Transportation Service Systems That Are Queuing Systems,Choosing a Measure of Performance,Managers who oversee queuing systems are mainly concerned with two measures of performance:(检查排队系统的管理人员主要考虑两种绩效测度)How many customers typically are waiting in the queuing system?(排队系统中有多少顾客在等待)How long do these customers typically have to wait?(这些顾客要等待多少时间),Choosing a Measure of Performance,When customers are internal to the organization,the first measure tends to be more important.(当顾客是提供服务的组织内部服务系统的内部顾客时，第一个测度比较重要)Having such customers wait causes lost productivity.(让内部服务系统的顾客等待会导致损失生产力),Choosing a Measure of Performance,Commercial service systems tend to place greater importance on the second measure.(商业服务系统外部顾客接受商业组织的服务会认为第二个测度更加重要)Outside customers are typically more concerned with how long they have to wait than with how many customers are there.(比起已经有多少顾客在等待，顾客更关心他们会等待多久),Defining the Measures of Performance,L=Expected number of customers in the system,including those being served(the symbol L comes from Line Length).,Defining the Measures of Performance,Lq=Expected number of customers in the queue,which excludes customers being served.,Defining the Measures of Performance,W=Expected waiting time in the system(including service time)for an individual customer(the symbol W comes from Waiting time).,Defining the Measures of Performance,Wq=Expected waiting time in the queue(excludes service time)for an individual customer.,Defining the Measures of Performance,These definitions assume that the queuing system is in a steady-state condition.(这些定义假设排队系统处于平稳条件中),运筹学排队模型,Relationship between L,W,Lq and Wq,并且,知其一即知其四,Using Probabilities as Measures of Performance,In addition to knowing what happens on the average,we may also be interested in worst-case scenarios.(除了知道系统性能指标的各种平均值之外，我们还可能对最坏情况感兴趣)What will be the maximum number of customers in the system?(Exceeded no more than,say,5%of the time.)(在95%的时间里，系统的最大顾客数不会超过某个值?),Using Probabilities as Measures of Performance,What will be the maximum waiting time of customers in the system?(Exceeded no more than,say,5%of the time.)(在95%的时间里，系统的顾客最大等待时间不会超过某个值?)Statistics that are helpful to answer these types of questions are available for some queuing systems(统计手段在回答这类问题时非常有用，因此它也可用于一些排队系统中):,Using Probabilities as Measures of Performance,Pn=Steady-state 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的概率),Using Probabilities as Measures of Performance,Examples of common goals(常用目标的一些例子):No more than three customers 95%of the time:P0+P1+P2+P3 0.95(在95%的时间里系统中的顾客数不超过3个)No more than 5%of customers wait more than 2 hours:P(W 2 hours)0.95(等待时间超过2小时的顾客数不超过总顾客数的5%),The Dupit Corp.Problem,The 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 the companys service technical representatives,or tech reps.,The Dupit Corp.Problem,杜皮特公司在办公复印机市场上长期处于领导地位杜皮特公司的服务部门负责为公司的顾客提供高质量的服务支持，在需要的时候维修公司的设备。这项工作由公司的技术服务代表完成,The Dupit Corp.Problem,Current policy:Each tech reps territory is assigned enough machines so that the tech rep will be active repairing machines(or traveling to the site)75%of the time.A repair call averages 2 hours,so this corresponds to 3 repair calls per day.Machines average 50 workdays between repairs,so assign 150 machines per rep.,The Dupit Corp.Problem,目前的政策：每一位技术服务代表的地域应当有足够多的机器设备，使得技术服务代表在75%的时间里都处于维修工作状态(或在前往维修地点的路上)每台设备的平均维修时间是2小时，一天平均要接到3个维修电话机器平均50个工作日需要维修一次，因此为每位技术服务代表分配150台机器,目前存在的问题,刚买了一款新式彩色打印-复印机，现在出了问题，等了这么久还没有人来维修，服务水平太差了，我要投诉！,The Dupit Corp.Problem,Proposed New Service Standard:The average waiting time before a tech rep begins the trip to the customer site should not exceed two hours.(建议的新服务标准：在技术服务代表开始前往顾客所在地修理设备之前，顾客的平均等待时间不应超过两个小时),Alternative Approaches to the Problem,Approach Suggested by John Phixitt:Modify the current policy by decreasing the percentage of time that tech reps are expected to be repairing machines.(约翰建议的做法：修改目前的政策，降低期望技术服务代表进行维修工作的时间百分比。减少分配数量，增加服务代表),Alternative Approaches to the Problem,Approach Suggested by the Vice President for Engineering:Provide new equipment to tech reps that would reduce the time required for repairs.(工程副总裁建议的做法：为技术服务代表提供新的装备，以减少设备修理时间),Alternative Approaches to the Problem,Approach Suggested by the Chief Financial Officer:Replace the current one-person tech rep territories by larger territories served by multiple tech reps.(首席财务总监建议的做法：将现在的单个技术服务代表负责区域转变为较大的区域，由多个技术服务代表提供服务),Alternative Approaches to the Problem,Approach Suggested by the Vice President for Marketing:Give owners of the new printer-copier priority for receiving repairs over the companys other customers.(营销副总裁建议的做法：授予这种新的打印-复印机的所有者比公司的其他顾客优先接受维修服务的权利),The Queuing System for Each Tech Rep,The customers:The machines needing repair.(顾客：需要修理的设备)Customer arrivals:The calls to the tech rep requesting repairs.(顾客到达：打给每一个技术服务代表要求修理的电话)The queue:The machines waiting for repair to begin at their sites.(队列：顾客所在地等待修理的所有设备)The server:The tech rep.(服务者：技术服务代表),The Queuing System for Each Tech Rep,Service time:The total time the tech rep is tied up with a machine,either traveling to the machine site or repairing the machine.(Thus,a machine is viewed as leaving the queue and entering service when the tech rep begins the trip to the machine site.),The Queuing System for Each Tech Rep,服务时间：技术服务代表花在一台设备上的总时间，包括到待修设备所在地的行进时间和维修时间(因此当技术服务代表开始前往设备所在地时，这台设备就可以视作已经离开队列进入服务系统了),Notation for Single-Server Queuing Models,Notation for Single-Server Queuing Models,运筹学排队模型,The M/M/1 Model,Assumptions(假设)Interarrival times have an exponential distribution with a mean of.(到达间隔时间服从均值为 的指数分布)Service times have an exponential distribution with a mean of 1/m.(服务时间服从均值为1/m 的指数分布)The queuing system has one server.(排队系统有一个服务台),The M/M/1 Model,运筹学排队模型,The M/M/1 Model,运筹学排队模型,The M/M/1 Model,The probability of having exactly n customers in the system is(系统中刚好有n个顾客的概率为),The probability that the waiting time in the system exceeds t is(在系统中的等待时间超过t的概率是),The M/M/1 Model,The probability that the waiting time in the queue exceeds t is(在队列中的等待时间超过t的概率是),运筹学排队模型,M/M/1 Queuing Model for the Dupits Current Policy,John Phixitts Approach(Reduce Machines/Rep),The proposed new service standard is that the average waiting time before service begins be two hours(i.e.,Wq 1/4 day).(建议的新服务标准是将每一个服务开始前的平均等待时间降为2小时),John Phixitts Approach(Reduce Machines/Rep),John Phixitts suggested approach is to lower the tech reps utilization factor sufficiently to meet the new service requirement.(约翰建议的方法是降低技术服务代表的有效因子以适应新的服务要求),John Phixitts Approach(Reduce Machines/Rep),运筹学排队模型,M/M/1 Model for John Phixitts Suggested Approach(Reduce Machines/Rep),方案1的结果,指定给每一位技术服务代表的设备数从150下降到100现有的技术服务代表人数10000人，工资约6亿美元/年公司大约要增加5000位技术服务代表，增加的费用大约为3亿美元/年,The M/G/1 Model,Assumptions(假设)：Interarrival times have an exponential distribution with a mean of 1/l.(到达间隔时间服从均值为1/l 的指数分布)Service times can have any probability distribution.You only need the mean(1/m)and standard deviation(s).(服务时间可以为任何概率分布，仅需要知道均值和标准差)The queuing system has one server.(排队系统有一个服务台),The probability of zero customers in the system is(系统中没有顾客的概率是),The expected number of customers in the queue is(队列中的顾客期望数是),The M/G/1 Model,The M/G/1 Model,The expected number of customers in the system is(系统中的顾客期望数是),The expected waiting time in the queue is(队列中的期望等待时间是),The