ch3--等待服务模型及仿真[1]

物流系统建模与仿真,第三章等待服务模型及仿真,2,3.1确定性系统与随机系统,确定型离散事件系统：系统状态的变化及其变化的时间间隔可以预先完全确定。随机型离散事件系统：系统状态的变化及其变化的时间间隔具备某种不确定性。现代运营管理系统具有较突出的离散性、随机性的特点，如；订单处理系统，库存管理系统，其订单或需求量以及到达间隔时间等常常都是随机变量，物流系统是典型的离散事件系统。,离散事件系统,确定型离散事件系统,随机型离散事件系统,3,例1某生产系统有两台同样的设备，如果该系统运作分确定性和随机性的两种情况，其设备加工零件的情况如下表所示：,一般来讲，确定性系统较容易推算其状态演变的情况，而随机性系统难用解析的方法建立模型或求解，这类系统往往要运用仿真的方法来分析和研究。,4,通过计算、仿真，该系统运行16小时的情况如下表所示：,5,物流管理系统中随机性现象随处可见，为了研究随机性现象，以下将讨论有关的随机现象与随机数。,如果零件到达时间间隔缩短到1.2分钟，则该系统运行16小时的情况如下表所示：,6,3.2随机数与随机变量简介,随机现象：事前不可预言的现象，即在相同条件下重复进行试验，每次结果未必相同，或知道事物过去的状况，但未来的发展却不能完全肯定。如：以同样的方式抛置硬币却可能出现正面向上也可能出现反面向上；走到某十字路口时，可能正好是红灯，也可能正好是绿灯。研究这类现象的数学工具是概率论和统计。随机变量(randomvariable)表示随机现象各种结果的变量。例如某一时间内公共汽车站等车乘客的人数，电话交换台在一定时间内收到的呼叫次数，等，都是随机变量的实例。,7,随机数和随机变量的产生对于有随机因素影响的系统进行仿真时，首先要建立随机变量模型，即确定系统的随机变量并确定这些随机变量的分布类型和参数。对于分布类型是已知的或者是可以根据经验确定的随机变量，只要确定它们的参数就可以了。建立了随机变量模型后还必需能够在计算机中产生一系列不同分布的随机变量的抽样值来模拟系统中的各种随机现象。,确定系统中随机变量模型时，一般有三种情形：1）随机变量分布的类型已知，需由观测数据确定其分布的参数；2）由观测数据确定随机变量概率分布类型，并在此基础上确定其参数；3）由已有的观测数据难以确定随机变量的理论分布二项式，则定义一个实验分布。随机现象常见于许多物流管理系统，如等待服务系统、仓储系统，等等。以下介绍等待服务系统。,9,3.3等待服务模型（排队模型）,等待服务模型是研究系统随机聚散现象和随机服务系统工作过程的定量分析方法，又称随机服务系统模型，或排队论模型。排队论(queuingtheory)简述:排队论就是通过对服务对象到来及服务时间的统计研究,得出这些数量指标(等待时间、排队长度、忙期长短等)的统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，又能使服务费用最经济或某些指标最优,排队论是运筹学的分支之一。,10,排队系统排队是人们在日常生活中经常遇到的现象，如顾客到商店买东西，病人到医院看病，人们上下汽车，故障机器停机待修等常常都要排队。排队的人或事物统称为顾客，为顾客服务的人或事物叫做服务机构(服务员或服务台等)，顾客排队要求服务的过程或现象称为排队系统或服务系统。由于顾客到来的时刻与进行服务的时间一般来说都是随机的，所以服务系统又称随机服务系统。,11,排队系统的基本组成,输入来源,队列,服务机构,排队系统,顾客,服务完离开,排队系统的三个基本组成部分：输入过程(顾客按照怎样的规律到达)；排队规则(顾客按照一定规则排队等待服务)；服务机构(服务机构的设置，服务台的数量，服务的方式，服务时间分布等),12,一、输入过程考察的是顾客到达服务系统的规律。它可以用一定时间内顾客到达数或前后两个顾客相继到达的间隔时间来描述，一般分为确定型和随机型两种。例如，在生产线上加工的零件按规定的间隔时间依次到达加工地点，定期运行的班车、班机等都属于确定型输入。随机型的输入是指在时间t内顾客到达数n(t)服从一定的随机分布。如服从泊松分布，则在时间t内到达n个顾客的概率为:,13,又如，相继到达的顾客的间隔时间T服从负指数分布，即,常见的随机分布有：M:指数分布(Markovian)D:定长分布(常数时间)Ek:k级Erlang分布G:普通的概率分布(任意概率分布),14,二、排队规则分为等待制、损失制和混合制三种。等待制：当顾客到达时，所有服务机构都被占用，则顾客排队等候，即为等待制。在等待制中，为顾客进行服务的次序可以是先到先服务，或后到先服务，或随机服务和有优先权服务（如医院接待急救病人）。损失制：如果顾客来到后看到服务机构没有空闲立即离去，则为损失制,如电话系统。混合制：是损失制与等待制的结合，有些系统因留给顾客排队等待的空间有限，因此超过所能容纳人数的顾客必须离开系统，这种排队规则就是混合制。,15,三、服务机构可以是一个或多个服务台。多个服务台可以是平行排列的，也可以是串连排列的。服务时间一般也分成确定型和随机型两种。例如，自动冲洗汽车的装置对每辆汽车冲洗（服务）时间是相同的，因而是确定型的。而随机型服务时间v则服从一定的随机分布。如果服从负指数分布，则其分布函数是:,式中为平均服务率，1/为平均服务时间。,16,顾客的服务时间由于多种原因具有不确定性(随机性)，最好的描述方法就是概率分布；同样顾客到达的间隔时间也具有一定的概率分布。服务时间和到达间隔时间服从什么分布？可以先通过统计得到经验分布，然后再做理论假设和检验。经验分布一般采用直方图来表示，如下图:,17,排队过程的组成部分可分为：单服务台泊松到达、负指数服务时间的排队模型多服务台泊松到达、负指数服务时间的排队模型单服务台泊松到达、任意服务时间的排队模型单服务台泊松到达、定长服务时间的排队模型多服务台泊松到达、任意的服务时间、损失制排队模型顾客来源有限制排队模型单服务台泊松到达、负指数服务时间、系统容量有限制的排队模型多服务台泊松到达、负指数服务时间、系统容量有限制的排队模型,18,排队系统的符号表示一个排队系统的特征可以用五个参数表示，其形式为：ABCDE，其中：A顾客到达的概率分布，可取M、D、G、Ek等；B服务时间的概率分布，可取M、D、G、Ek等；C服务台个数，取正整数；D排队系统的最大容量，可取正整数或；E顾客源的最大容量，可取正整数或。例如M/M/1/表示顾客到达过程服从泊松分布，服务时间服从负指数分布，一个服务台，排队的长度无限制和顾客的来源无限制。,19,M/M/1/设单位时间顾客平均到达数为，单位平均服务顾客数为()。一般地，我们都认定,即到达率小于服务率，如果没有这个条件，则排队的长度将无限制地增加，服务机构根本没有能力处理所有到达的顾客，也就是/1，我们称/为服务强度。,3.3.1单服务台泊松到达、负指数服务时间的排队模型,20,1)系统中无顾客的概率:P0=1/2)平均排队的顾客数:Lq=2/()3)系统中的平均顾客数:Ls=Lq+/4)顾客花在排队上的平均等待时间:Wq=Lq/5)顾客在系统中的平均逗留时间:Ws=Wq+1/6)顾客得不到及时服务必须排队等待的概率:Pw=/7)系统中恰好有n个顾客的概率:Pn=(/)nP0,单服务台泊松到达、负指数服务时间的排队模型,有关数量指标公式为:,21,例1.某储蓄所只有一个服务窗口。根据统计分析,顾客的到达过程服从泊松分布,平均每小时到达顾客30人;储蓄所服务时间服从负指数分布,平均每小时能处理36位顾客的业务,试求这个排队系统的数量指标。解:平均到达率:=30/60=0.5平均服务率:=36/60=0.6系统中无顾客的概率:P0=1/=10.5/0.55=0.167平均排队的顾客数:Lq=2/()=(0.6)2/0.8(0.80.6)=4.67(个顾客),22,系统中的平均顾客数：Ls=Lq+/=2.25+0.6/0.8=5(个顾客)顾客花在排队上的平均等待时间:Wq=Lq/=2.25/0.6=8.3（分钟）顾客在系统中的平均逗留时间:Ws=Wq+1/=3.75+1/0.8=10（分钟）顾客得不到及时服务须排队等待的概率:Pw=/=0.6/0.8=0.83系统中恰好有n个顾客的概率:Pn=(/)nP0=(0.833)n0.167,n=1,2,.,23,通过计算，可知储蓄所的排队系统里有n个顾客的概率，见下表1：表1,24,运用MS6.0软件进行计算,25,应用仿真技术对例1所述的银行系统的运营情况进行模拟和仿真，并通过对实际情况的模拟和仿真，分析该系统运作中存在的问题，提出改进和优化的方案。,银行(例1)排队系统的情景仿真,26,银行排队系统仿真仿真技术学习要点：1.实体参数的设置2.实体属性的特点及其运用3.临时实体的种类和临时实体工具箱4.顾客的到来,27,通过仿真可见系统提供的服务水平较低。如何改进？增加新型点钞机，建立储户管理信息系统，可以缩短储蓄所每笔业务的服务时间，使每小时平均服务的顾客数目从原来的36人提高到42人（即每分钟平均服务的顾客数从0.6人提高到0.7人）再设一个服务窗口，排队的规则为单队多服务台，先到先服务。分别对以上两个方案进行仿真分析，并提出系统的优化方案。,28,例2.在前面例1的储蓄所里增加一个服务窗口，即储蓄所开设两个服务窗口。顾客的到达过程仍服从泊松分布，平均每小时到达顾客仍是30人；储蓄所的服务时间仍服从负指数分布，平均每小时仍能处理36位顾客的业务，其排队规则为只排一个队，先到先服务。试求这个排队系统的数量指标。解:k=2，平均到达率:=30/60=0.5，平均服务率:=36/60=0.6。,3.3.2多服务台泊松到达、负指数服务时间的排队模型,系统中无顾客的概率:P0=0.4118平均排队的顾客数:Lq=0.175(个顾客)系统中的平均顾客数：Ls=1.008(个顾客)顾客花在排队上的平均等待时间:Wq=0.35(分钟)顾客在系统中的平均逗留时间:Ws=2.017(分钟)顾客得不到及时服务须排队等待的概率:Pw=0.245,29,30,通过计算，可知储蓄所的排队系统里有n个顾客的概率，见下表2：表2,31,思考题：1）在例1，2中如果，该储蓄所的运作情况如何？2）在例1，2中如果顾客的到达率服从正态分布，如何计算该储蓄所的运作情况？3）在储蓄所里使用M/M/2模型与使用两个M/M/1模型，它们的服务台数都是2，服务率和顾客到达率都一样，只是在M/M/2中只排一队，在2个M/M/1中排两个队，结果是否一样？试通过仿真进行说明。,32,通常，银行平均服务率往往大于例1中的0.6人/分钟，一般情况是服务一个顾客需10分钟左右，如果设服务一个顾客平均需8分钟，即平均服务率为:=0.125人/分钟这时例1中满足:=0.5对于这种情况上述单服务台泊松到达、负指数服务时间的排队模型不可用，而仿真模型则可以对此进行模拟和分析。,银行(例1)排队系统仿真演示,33,通过仿真容易看出在该储蓄所中顾客等待的时间较长，等待的顾客人数较多，服务水平有待于提高。为了提高服务水平，缩短顾客排队的平均时间，就必须缩短平均服务的时间，一般可采用的措施有第一，减少服务时间，提高服务率；第二，增加服务台即增加服务窗口。进一步对以上两种改进方案进行仿真，比较其改进前后的情况，并对两种方案的仿真结果进行比较，以决定选择更优的方案。,34,如采取第一种方法，不增加服务窗口，而增加新型点钞机，建立储户管理信息系统，可以缩短储蓄所每笔业务的服务时间，使每小时平均服务的顾客数目从原来的8人提高到10人。,如果采用第二种方法，再设一个服务窗口，排队的规则为每个窗口排一个队，先到先服务，并假设顾客一旦排了一个队，就不能再换到另一个队上去。这种处理方法就是把顾客分流，把一个排队系统分成两个排队系统，每个排队系统中有一个服务台，每个系统的服务率仍然为8人小时，但到达率由于分流，只有原来的一半了，即每小时到达15人。,如果在第二种方法中把排队的规则变一下，在储蓄所里只排一个队，其结果又将如何？,35,例3某汽车冲洗服务营业部，有一套自动冲洗设备，冲洗每辆车需要6分钟，到此营业部来冲洗的汽车到达过程服从泊松分布，每小时平均到达6辆，试求这个排队系统的数量指标。解：这是一个M/D/1排队模型，其中:=6辆/小时，=60/6=10辆/小时，得P0=1/=0.4,Lq=0.45,Ls=Lq+/=1.05,Wq=Lq/=0.0750，Ws=Wq+1/=0.1750,Pw=/=0.6。,3.3.3单服务台泊松到达、定长服务时间的排队模型,M/D/1,36,排队系统仿真,汽车冲洗服务排队系统仿真模型演示汽车冲洗服务排队系统仿真实验实验要点：临时实体工具箱：新增加临时实体；属性；改变三维形状；流节点用法,37,M/M/1/m条件：单位时间顾客平均到达数单位平均服务顾客数关心的项目:1)系统中无顾客的概率P02)系统中平均排队的顾客数Lq3)系统中的平均顾客数Ls4)系统中顾客平均的排队等待时间Wq5)系统中顾客的平均逗留时间Ws6)系统中顾客必须排队等待的概率Pw7)系统中恰好有n个顾客的概率Pn,3.3.4顾客来源有限制的排队模型,38,M/M/1/m数量指标公式:1)系统中无顾客的概率2)平均排队的顾客数3)系统中的平均顾客数:Ls=Lq+(1-p0)4)顾客在排队上的平均花费等待时间:Wq=Lq/(m-Ls)5)在系统中顾客的平均逗留时间:Ws=Wq+1/6)系统中有n个顾客的概率,39,例4.某车间有5台机器，每台机器连续运转时间服从负指数分布,平均连续运转时间为15分钟,有一个修理工,每次修理时间服从负指数分布,平均每次12分钟,求该排队系统的数量指标P0,Lq,Ls,Wq,Ws,以及P5.解：这是一个M/M/1/5系统。其中，m=5,=1/15=0.0667,=1/12=0.0833,/=0.8。Lq=2.766;Ls=3.759;Wq=33.43;Ws=45.43P5=0.2870,40,应用仿真技术对以上例7系统运营情况进行仿真和分析,其实验要点：1）处理器：MTBF,MTTR，维修使用操作人员；2）分配器,第三节M/M/n模型,41,3.3生产过程排队系统仿真的例子例5:某工厂制造三种类型产品的生产过程仿真。在仿真模型中，每种产品关联一个临时实体类型的数值,这三种类型的产品都相间从工厂其它部门送达。模型中还有三台机器。每台