ch3-等待服务模型及仿真

物流系统建模与仿真,2,第三章等待服务模型及仿真,3.1确定性系统与随机系统,确定型离散事件系统：系统状态的变化及其变化的时间间隔可以预先完全确定。随机型离散事件系统：系统状态的变化及其变化的时间间隔具备某种不确定性。现代运营管理系统具有较突出的离散性、随机性的特点，如；订单处理系统，库存管理系统，其订单或需求量以及到达间隔时间等常常都是随机变量，物流系统是典型的离散事件系统。,离散事件系统,确定型离散事件系统,随机型离散事件系统,3,例1某生产系统有两台同样的设备，如果该系统运作分确定性和随机性的两种情况，其设备加工零件的情况如下表所示：,一般的来讲，确定性系统较容易推算其状态演变的情况，而随机性系统难用解析的方法建立模型或求解，这类系统往往要运用仿真的方法来分析和研究。,4,通过计算、仿真，该系统运行16小时的情况如下表所示：,5,物流管理系统中随机性现象随处可见，为了研究随机性现象，以下将讨论有关的随机现象与随机数。,如果零件到达时间间隔缩短到1.2分钟，则该系统运行16小时的情况如下表所示：,6,3.2随机数与随机变量简介,随机现象：事前不可预言的现象，即在相同条件下重复进行试验，每次结果未必相同，或知道事物过去的状况，但未来的发展却不能完全肯定。如：以同样的方式抛置硬币却可能出现正面向上也可能出现反面向上；走到某十字路口时，可能正好是红灯，也可能正好是绿灯。研究这类现象的数学工具是概率论和统计。随机变量(randomvariable)表示随机现象各种结果的变量。例如某一时间内公共汽车站等车乘客的人数，电话交换台在一定时间内收到的呼叫次数，等，都是随机变量的实例。,7,随机数和随机变量的产生对于有随机因素影响的系统进行仿真时，首先要建立随机变量模型，即确定系统的随机变量并确定这些随机变量的分布类型和参数。对于分布类型是已知的或者是可以根据经验确定的随机变量，只要确定它们的参数就可以了。建立了随机变量模型后还必需能够在计算机中产生一系列不同分布的随机变量的抽样值来模拟系统中的各种随机现象。,8,随机变量分布的表示方法：公式法如：列表法如：,9,图示法以横坐标表示随机变量的可能取值，纵坐标表示随机变量取这些值的概率，并用线把这些点连接得下图，它反映了随机变量的概率分布。按照随机变量的取值情况又可把其分为两类，即离散随机变量和连续随机变量,连续随机变量概率分布图,离散随机变量概率分布图,确定系统中随机变量模型时，一般有三种情形：1）随机变量分布的类型已知，需由观测数据确定其分布的参数；2）由观测数据确定随机变量概率分布类型，并在此基础上确定其参数；3）由已有的观测数据难以确定随机变量的理论分布二项式，则定义一个实验分布。随机现象常见于许多物流管理系统，如等待服务系统、仓储系统，等等。以下介绍等待服务系统。,11,生产制造等待加工的过程,12,车辆等待过关检查或装卸的过程,13,3.3等待服务模型（排队模型）,等待服务模型是研究系统随机聚散现象和随机服务系统工作过程的定量分析方法，又称随机服务系统模型，或排队论模型。排队论(queuingtheory)简述:排队论就是通过对服务对象到来及服务时间的统计研究,得出这些数量指标(等待时间、排队长度、忙期长短等)的统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，又能使服务费用最经济或某些指标最优,排队论是运筹学的分支之一。,14,排队系统排队是人们在日常生活中经常遇到的现象，如顾客到商店买东西，病人到医院看病，人们上下汽车，故障机器停机待修等常常都要排队。排队的人或事物统称为顾客，为顾客服务的人或事物叫做服务机构(服务员或服务台等)，顾客排队要求服务的过程或现象称为排队系统或服务系统。由于顾客到来的时刻与进行服务的时间一般来说都是随机的，所以服务系统又称随机服务系统。,15,排队系统的基本组成,输入来源,队列,服务机构,排队系统,顾客,服务完离开,排队系统的三个基本组成部分：输入过程(顾客按照怎样的规律到达)；排队规则(顾客按照一定规则排队等待服务)；服务机构(服务机构的设置，服务台的数量，服务的方式，服务时间分布等),16,一、输入过程考察的是顾客到达服务系统的规律。它可以用一定时间内顾客到达数或前后两个顾客相继到达的间隔时间来描述，一般分为确定型和随机型两种。例如，在生产线上加工的零件按规定的间隔时间依次到达加工地点，定期运行的班车、班机等都属于确定型输入。随机型的输入是指在时间t内顾客到达数n(t)服从一定的随机分布。如服从泊松分布，则在时间t内到达n个顾客的概率为:,17,又如，相继到达的顾客的间隔时间T服从负指数分布，即,常见的随机分布有：M:指数分布(Markovian)D:定长分布(常数时间)Ek:k级Erlang分布G:普通的概率分布(任意概率分布),18,),),19,),20,4)泊松分布:在单位时间里有x个顾客到达的概率为:P(x)=xe-/x!(x=0,1,2,)为单位时间平均到达的顾客数。满足以下四个条件的输入流称为泊松流(泊松过程)*平稳性:在时间区间t,t+t)内到达k个顾客的概率与t无关,只与t有关,记为pk(t);*无后效性:不相交的时间区间内到达的顾客数互相独立;*普通性:在足够短的时间内到达多于一个顾客的概率可以忽略;*有限性:任意有限个区间内到达有限个顾客的概率等于1.,21,二、排队规则分为等待制、损失制和混合制三种。等待制：当顾客到达时，所有服务机构都被占用，则顾客排队等候，即为等待制。在等待制中，为顾客进行服务的次序可以是先到先服务，或后到先服务，或随机服务和有优先权服务（如医院接待急救病人）。损失制：如果顾客来到后看到服务机构没有空闲立即离去，则为损失制,如电话系统。混合制：是损失制与等待制的结合，有些系统因留给顾客排队等待的空间有限，因此超过所能容纳人数的顾客必须离开系统，这种排队规则就是混合制。,22,三、服务机构可以是一个或多个服务台。多个服务台可以是平行排列的，也可以是串连排列的。服务时间一般也分成确定型和随机型两种。例如，自动冲洗汽车的装置对每辆汽车冲洗（服务）时间是相同的，因而是确定型的。而随机型服务时间v则服从一定的随机分布。如果服从负指数分布，则其分布函数是:,式中为平均服务率，1/为平均服务时间。,23,顾客的服务时间由于多种原因具有不确定性(随机性)，最好的描述方法就是概率分布；同样顾客到达的间隔时间也具有一定的概率分布。服务时间和到达间隔时间服从什么分布？可以先通过统计得到经验分布，然后再做理论假设和检验。经验分布一般采用直方图来表示，如下图:,24,排队过程的组成部分可分为：单服务台泊松到达、负指数服务时间的排队模型多服务台泊松到达、负指数服务时间的排队模型单服务台泊松到达、任意服务时间的排队模型单服务台泊松到达、定长服务时间的排队模型多服务台泊松到达、任意的服务时间、损失制排队模型顾客来源有限制排队模型单服务台泊松到达、负指数服务时间、系统容量有限制的排队模型多服务台泊松到达、负指数服务时间、系统容量有限制的排队模型,25,排队系统的符号表示一个排队系统的特征可以用五个参数表示，其形式为：ABCDE，其中：A顾客到达的概率分布，可取M、D、G、Ek等；B服务时间的概率分布，可取M、D、G、Ek等；C服务台个数，取正整数；D排队系统的最大容量，可取正整数或；E顾客源的最大容量，可取正整数或。例如M/M/1/表示顾客到达过程服从泊松分布，服务时间服从负指数分布，一个服务台，排队的长度无限制和顾客的来源无限制。,26,M/M/1/设单位时间顾客平均到达数为，单位平均服务顾客数为()。一般地，我们都认定,即到达率小于服务率，如果没有这个条件，则排队的长度将无限制地增加，服务机构根本没有能力处理所有到达的顾客，也就是/k时,38,例2.在前面例1的储蓄所里多设一个服务窗口，即储蓄所开设两个服务窗口。顾客的到达过程仍服从泊松分布，平均每小时到达顾客仍是30人；储蓄所的服务时间仍服从负指数分布，平均每小时仍能处理36位顾客的业务，其排队规则为只排一个队，先到先服务。试求这个排队系统的数量指标。解:k=2，平均到达率:=30/60=0.5，平均服务率:=36/60=0.6。,39,40,系统中无顾客的概率:P0=0.4118平均排队的顾客数:Lq=0.175(个顾客)系统中的平均顾客数：Ls=1.008(个顾客)顾客花在排队上的平均等待时间:Wq=0.35(分钟)顾客在系统中的平均逗留时间:Ws=2.017(分钟)顾客得不到及时服务须排队等待的概率:Pw=0.245,41,通过计算，可知储蓄所的排队系统里有n个顾客的概率，见下表2：表2,42,思考题：1）在例1，2中如果，该储蓄所的运作情况如何？2）在例1，2中如果顾客的到达率服从正态分布，如何计算该储蓄所的运作情况？3）在储蓄所里使用M/M/2模型与使用两个M/M/1模型，它们的服务台数都是2，服务率和顾客到达率都一样，只是在M/M/2中只排一队，在2个M/M/1中排两个队，结果是否一样？试通过仿真进行说明。,43,储蓄所排队系统仿真,储蓄所排队系统仿真模型演示储蓄所排队系统仿真实验实验要点：临时实体工具箱（临时实体的区别）;发生器：临时实体（人）；行走；实体属性视景:三维形状改变.,44,Flexsim实体的属性每个Flexsim实体都有一个属性视窗和一个参数视窗。访问属性可用右键点击模型视窗中的一个实体并选择属性（见右图）。,45,每个Flexsim实体的属性都是相同的。在属性中有4个分页：视景、常规、标签和统计。每个分页包含所选的Flexsim实体的附属信息。常规属性：常规属性分页包含实体的常用信息，如名称、类型、位置、端口连接、显示标记和使用者描述（见右图）。,46,视景属性：视景分页允许建模人员指定视觉特性，如3D形状、2D形状、3D纹理、颜色、位置、尺寸、转角和用户绘图代码。位置、尺寸和转角反映实体的当前属性（见右图）。建模人员可在相关字段中修改这些属性值，也可以在模型界面视窗中用鼠标来改变这些属性。,47,通常，银行平均服务率往往大于例1中的0.8人/分钟，一般情况是服务一个顾客需10分钟左右，如果设服务一个顾客平均需8分钟，即平均服务率为:=0.125人/分钟这时例1中满足:=0.6对于这种情况上述单服务台泊松到达、负指数服务时间的排队模型不可用，而仿真模型则可以对此进行模拟和分析。,银行(例1)排队系统仿真演示,48,表3FlexsimStandardReport,通过仿真容易看出在该储蓄所中顾客等待的时间较长，等待的顾客人数较多，服务水平有待于提高。以下是由Flexsim系统导出的标准报告。,由以上报告可见，在该储蓄所营业2.78小时(即10031秒)内，顾客平均等待的时间为58.1分钟，排队等待的人数为34,而且这种现象将随着营业的进行愈演愈烈。,49,通过仿真可知储蓄所的排队系统并不尽如人意，顾客到达储蓄所排队等待的时间太长。为了提高服务水平，缩短顾客排队的平均时间，就必须缩短平均服务的时间，一般可采用两种措施：第一，减少服务时间，提高服务率；第二，增加服务台即增加服务窗口。进一步对以上两种改进方案进行仿真，比较其改进前后的情况，并对两种方案的仿真结果进行比较，以决定选择更优的方案。,50,如采取第一种方法,不增加服务窗口,而增加新型点钞机，建立储户管理信息系统，可以缩短储蓄所每笔业务的服务时间，使每小时平均服务的顾客数目从原来的8人提高到10人,其仿真的结果如表4所示:,比较表4可知，采取第一种方法该储蓄所营业2.78小时内，顾客平均等待的时间为41.4分钟，比改进前缩短了约17分钟，排队等待的人数为30，比改进前减少了4人，但显然问题没有得到根本性的解决。,表4,51,如果采用第二种方法，再设一个服务窗口，排队的规则为每个窗口排一个队，先到先服务，并假设顾客一旦排了一个队，就不能再换到另一个队上去。这种处理方法就是把顾客分流，把一个排队系统分成两个排队系统，每个排队系统中有一个服务台，每个系统的服务率仍然为8人小时，但到达率由于分流，只有原来的一半了，即每小时到达10人，这时仿真的结果如表5所示:,表5,52,比较表5可知，采取第二种方法该储蓄所营业2.78小时内，顾客平均等待的时间为47.4分钟，比改进前缩短了约11分钟，排队等待的人数为14，比改进前减少了20人，改进的效果仍不理想。如果在第二种方法中把排队的规则变一下，在储蓄所里只排一个队，其仿真的结果如表6所示:,表6,53,M/D/1注：它是M/G/1的特殊情况=0。1)系统中无顾客的概率P0=1/2)平均排队的顾客数,3.3.3单服务台泊松到达、定长服务时间的排队模型,54,3)系统中的平均顾客数:Ls=Lq+/4)顾客花在排队上的平均等待时间:Wq=Lq/5)在系统中顾客的平均逗留时间:Ws=Wq+1/6)系统中顾客必须排队等待的概率:Pw=/7)系统中恰好有n个顾客的概率:Pn,单服务台泊松到达、定长服务时间的排队模型,55,例5某汽车冲洗服务营业部，有一套自动冲洗设备，冲洗每辆车需要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。,56,排队系统仿真,汽车冲洗服务排队系统仿真模型演示汽车冲洗服务排队系统仿真实验实验要点：临时实体工具箱：新增加临时实体；属性；改变三维形状；流节点用法,57,M/M/1/m条件：单位时间顾客平均到达数单位平均服务顾客数关心的项目:1)系统中无顾客的概率P02)系统中平均排队的顾客数Lq3)系统中的平均顾客数Ls4)系统中顾客平均的排队等待时间Wq5)系统中顾客的平均逗留时间Ws6)系统中顾客必须排队等待的概率Pw7)系统中恰好有n个顾客的概率Pn,3.3.4顾客来源有限制的排队模型,58,M/M/1/m数量指标公式:1)系统中无顾客的概率2)平均排队的顾客数3)系统中的平均顾客数:Ls=Lq+(1-p0)4)顾客在排队上的平均花费等待时间:Wq=Lq/(m-Ls)5)在系统中顾客的平均逗留时间:Ws=Wq+1/6)系统中有n个顾客的概率,59,例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,60,应用仿真技术对以上例7系统运营情况进行仿真和分析,其实验要点：1）处理器：MTBF,MTTR，维修使用操作人员；2）分配器,第三节M/M/n模型,61,3.3生产过程排队系统仿真的例子模型描述:某工厂制造三种类型产品的生产过程仿真。在仿真模型中，每种产品关联一个临时实体类型的数值,这三种类型的产品都相间从工厂其它部门送达。模型中还有三台机器。每台机器加工一种特定的产品类型。产品在它们各自的机器中完成加工后，所有三种类型的产品必须在一个共享的检验站中检验其正确性。如果它们的制造完好，就被送到工厂的另一部门，离开仿真模型。如果发现制造有缺陷，则必须送回到仿真模型的起始点，经对应的机器重新进行处理。,62,模型数据:发生器到达速率：产品按指数分布到达，均值为5秒；暂存区最大容量：无限量；处理时间：exponential（0,10）秒；临时实体路径：类型1到1号机器加工，类型2到2号机器加工，类型3到3号机器加工；检验时间：4秒产品返回再加工比例为：20%,63,仿真的目的是找到瓶颈的所在。该检验设备是否导致其它三台加工机器前实体的堆积，或者是否会因为三台加工机器不能跟上它的节奏而使之空闲等待？两机器间的缓冲空间是否必要？将该模型应用到不同行业中,虽然我们以制造行业为例，但同类的仿真模型也可应用于其它行业。以一个复印中心为例。一个复印中心主要有三种服务：黑白复印、彩色复印和装订。在工作时间内有3个雇员工作，一个负责黑白复印工作，另一个处理彩色复印，第三个负责装订。另有一个出纳员对完成的工作进行收款。每个进入复印中心的