典型系统的离散事件系统仿真.ppt

典型系统的离散事件系统仿真,排队系统的仿真模型,排队系统也称为随机服务系统，是随机系统的一个大类，包括各种交通系统、电话系统、加工系统等系统由提供服务的服务设施与被服务者组成被服务者统称为顾客排队系统中仿真钟推进是跳跃式的。,排队系统,一、排队系统的结构排队系统简单而典型的形式如图所示，系统本身包括了顾客(被服务者)、排队队列和服务台三部分。,顾客从顾客源中进入系统，它们形成了不同队长的排队队列，这个队列在不同的时间有不同的长度，也可能为零，即在某些时间无人排队。服务台是接收顾客井为顾客服务的服务设施，它可以是一个简单的单服务台，也可以是一个复杂的服务网络。顾客服务结束后离开系统离开后可能是重返顾客源，也可以是永远离开系统。排队系统是一个顾客不断的到来、排队及服务与离去的动态过程。,二、顾客与顾客源,顾客：需要系统对其服务的实体，有时则直接称为“实体”。顾客可以是零件、机器、人等。顾客源：又叫顾客总体，是指潜在的顾客总数。它分为有限与无限两类。,有限总体指顾客源中的顾客个数是确切的或者是有限的。例如若一个维修工人负责维修一个车间的3台机器，则这3台机器就是一个有限的总体。在具有较大潜在顾客的系统中，顾客源一般假定为无限的，即不能用确切的或者有限个数来描述。例如进入超市的顾客或者要求通话的顾客即可假定为无限总体。,有限顾客源模型中，顾客到来率取决与正在服务或者正在等待服务的顾客数。无限顾客源模型中，顾客到来率不受正在服务或者正在等待服务的顾客数的影响，当到来过程在整个时间上是齐次时，到来率通常假设为常数。,三、顾客到来模式,到来模式是指顾客按怎么的规律到来系统。它一般用顾客相继到来的间隔时间来描述。根据间隔时间的确定与否，到来模式可分为确定性到来与随机性到来。确定性到来模式指顾客有规则的按照一定的间隔时间到达。这些间隔时间是预先确定的或者是固定的。等距到来模式就是一个常见的确定性到来模式。,随机性到来模式指顾客相继到来的间隔时间是随机的，不确定的，它一般使用概率分布来描述。常见的随机性到来模式有以下几种：1、泊松到来模型2、爱尔朗到来模式3、一般独立到来模式,1、泊松到来模型,泊松到来模式（又称M型到来过程）一般需要满足4个条件：平稳性、无后效性（独立性）、普通性和有限性。（商店顾客的到来、机器到来维修点等可以用之）其到来分布函数为：,2、爱尔朗到来模式,常用于典型的电话系统。其到来分布函数为：（其中，为平均到来速率，k为大于零的正整数）,3、一般独立到来模式,也称任意分布的到来模式。指到来间隔时间相互独立，分布函数A0(t)是任意分布的到来模式。这种分布往往可以用一个离散的概率分布表加以描述。此外、还有超指数到来模式、成批到来模式等。前者主要用厂概率分布的标准差大于平均值的情况下；后者则与到来时间间隔的分布无关，只是在每一到来时刻，到来的顾客个数不是一个，而是一批。,四、服务机构,服务机构和顾客（被服务对象）组成了排队系统，服务机构的结构与顾客被服务的内容与顺序组成了整个排队系统的仿真对象。1、服务机构（服务台）是指同一时刻有多少服务台可以提供服务，服务台之间的布置及关系是什么样的。,2、服务时间,定长分布：这是最简单的情形，所有顾客被服务的时间为常数a 指数分布：当服务时间完全随机的时候，可以用指数分布来表示它；爱尔朗分布：它用来描述服务时间的标准差小于平均值(或变异系数标准差平均值1)的情况；,超指数分布：与爱尔朗分布相对应用来描述服务时间的标准差大于平均值(或变异系数1)的情况；一般服务分布：用于服务时间是相互独立但具有相同分布的随机情况，而上述分布是一般分布的特例；正态分布：在服务时间近似于常数的情况下，多种随机因素的影响使得服务时间围绕此常数值上下波动，一船用正态分布来描述服务时间；服务时间依赖于队长的情况：即排队顾客超多，服务速度越快，服务时间越短。,五、排队规则,当顾客进入系统后或顾客进入各级服务台前都有可能因为服务台繁忙而需要排队等待服务，即不能立即被服务，顾客在排队等待服务时有不同的规则。排队规则确定了顾客在队列中的逻辑次序、服务台有空时哪一个顾客被选择去服务以及顾客按什么样的次序与规则接受服务。,排队规则,1、损失制：若顾客到来时，系统所有的服务机构均非空，则顾客自动离去，不再回来。2、等待制：顾客到来时，系统所有服务台均非空，则顾客形成队列等待服务。具体包括：先进先出、后进先出、随机服务、按优先级服务、最短处理时间先服务,3、混合制（损失制与等待制的综合类型）限制队长的排队规则限制等待时间的排队规则限制逗留时间的排队规则,排队系统的性能指标与符号表示,一、排队系统的性能指标及其表示服务质量与服务效率是排队系统的性能指标。服务质量是指顾客需要等待的时间长短，可以用平均等待时间、平均队长来表示；有时也需要加上最大等待时间与最长队长来表示。,服务台效率则用忙期闲期比来表示。另外系统中顾客平均逗留时间与服务台利用率也是系统性能指标1、服务台利用率,2、平均等待时间,3、平均逗留时间,4、平均队长,5、系统中平均顾客数,6、忙期（闲期）,忙期是指服务台全部处于非空闲状态的时间段，否则称为非忙期。闲期指服务台全部处于空闲状态的时间段。对于单服务台来说，忙期与闲期交替出现。除以上常见的性能指标外，具体的排队系统还可以根据系统本身的要求采用其他体现系统性能的指标如最长队列、顾客在系统中最大的逗留时间等等。,排队系统中的符号表示,排队系统符号表示的简要格式为ASCN/K。各符号的含义如下：A：到来间隔时间分布（对应到来模式）S：服务时间分布A与S的具体形式有M（指数分布），D（常数或确定性分布），Ek（k阶爱尔朗分布），G（一般独立分布）等,C：并行服务台个数N：排队的规模K：顾客源（总体）规模通常，此格式可以简化为A/S/C。例如，M/M/1/表示到来时间间隔和服务时间均服从指数分布，单服务台，队列容量与顾客源均无限的系统,单服务台系统的仿真,单服务台结构是排队系统中最简单的结构形式，在该类系统中有一级服务台，这一级中也只有一个服务台。如只有一个理发员的一个小理发馆，只有一台机床加工一个工序的加工系统。它的结构如图：,一、事件类型,原发事件两类：到来与离去后续事件两类：顾客接受服务与服务台寻找服务。（事件定义表如下）,二、事件处理子程序,三、仿真过程,以一个单服务台的理发店为例，将仿真过程列表表示出来，以便更好地了解仿真过程。仿真结束时间为240分钟，该理发店的服务参数为（M/M/1），仿真时间以分计量，=0.1，排队规则为FIFO，仿真表如下：,单级多服务台排队系统的仿真,单级多服务台结构也是经常遇到的一类排队系统形式，它又可分为所有服务台只有一个排队以及每个服务台都有排队的两种不同情况，分别如图(a)与(b)所示。,这里每个服务台的服务时间可以有相同分布与相同参数也可以有不同参数甚至不同的分布。在第一种排队形式中，无论哪个服务台空闲则有顾客进入；当两个或两个以上服务台空闲时，则可按规则选择并进入其中的一个服务台。在第二种排队形式中，首先确定该顾客选择哪个服务台，然后根据选择的服务台是“忙”或“闲”决定是接受并开始服务还是在服务台前的队列中等待服务。,在单级多服务台结构的排队系统仿真建模时，首先应将服务台从1到N编号，每个服务台的忙或闲的状态用专门变量来表示，同时由累加器累加各服务台的忙态或闲态的总时间。此外，此时事件处理子程序也有不同，到来事件处理子程序与单服务台系统相同，但它的后续事件接受服务则不同，它的处理应按下图所示：,多级多服务台排队系统的仿真,多级多服务台排队系统是排队系统的一类常见形式，下图表示了一个典型的多级多服务台排队系统，服务台共有3级、每级分别由2台、3台和1台组成。每级服务台前有一排队，顾客进入系统后逐级进入服务台，逐级服务。如没有空闲的服务台则逐级排队等待，当最后一级服务结束后顾客离开系统。,在多级多服务台结构的排队系统中、服务台的编号用两个参数i,j来表示；i表示服务台所属的级数i在1到I之间、I为此排队系统共有的级数。参数j则用来区分第i级并行的若干服务台，j在1到Ji之间，Ji表示在第i级服务台中并行服务台的个数在上图36中表示的系统I=3,J12,J23,J31,多级多服务台系统中事件的类型及其定义如表,其他类型排队系统,尽管我们分别论述了单服务台、单级多服务台以及多级多服务台的排队系统的仿真建模但在实际系统中不会那么典型、而往往会有不同的情况下面分别论述其他排队系统的有关问题,一、顾客的多样化,如一个加工系统中可以加工一种部件，也可以加工两种或两种以上的部件，不同类的顾客（或工件)到来间隔不同，接受服务内容有相向部分，也有不同部分。如理发店中接待男女顾客都需要洗发，但男、女顾客各有其不同的服务内容，同为男或女顾客也可能有不同的服务内容。,二、服务台的多样化,服务台不仅在个数上有不同,而且在其他方面也有不同 有的服务台可以是移动的、如下一节介绍的救护系统中顾客呼叫服务，服务台为救护车及救护人员、它们到来呼叫地点，将病人送到医院其服务台是移动的。,又如城市的公共交通服务系统，市民在各站台等待排队，公共汽车将逐站地接受顾客并将他们送到目的站，这同样是一个随机服务系统同样有服务效率与服务质量的矛盾。让某一路公共汽车以较高的频率发车则会使各站减小排队队长与等待时间，但也会使公共汽车效率减低，采用离散事件仿真技术仿真公共汽车及市民到各站候车的真实系统运行状况、为这类复杂的实际问题的求解提供了方法,三、顾客等待的多样性,顾客到来系统后如果不能及时接受服务则需要排队等待，但也有的顾客因得不到服务就离开了系统，所以是非等待制而是消失制。如电话系统中由于服务台不能接通顾客的呼叫，顾客的这次呼叫消失了。也有的是在一定队长范围内顾客排队，否则顾客就离去。,同样在接受服务时也有多样化的问题有先到先服务的。也有顾客带有不同的优先级，对优先级高的顾客服务台甚至可以中断现有的服务，让服务一半的顾客排队等待，而为优先级高的顾客服务；总之，现实的排队系统是多样的，也会带来更多的复杂性、仿真技术可以更好地为各种类型排队系统分析、求解。,库存系统的仿真,为了使生产线上每个工序、每台加工装置能不停地工作，需要各个加工环节有一定数量的在制品，整个企业的顺利运作也需要人、财、物等凡需要使用而暂时尚未使用的这些资源存储备用。由于生产过程的种种随机性使这些资源的需要、补充都不可避免地具有随机性。所以为了确保生产的连续性、库存必定会存在。,一、库存系统结构,库存系统主要包括三方面的内容：库存状态、补充和需求库存状态是指存货随着时间的推移而发生的盘点数量的变化。其数量随着需求过程而减少，又随补充过程而增加。,需求是系统的输出，它可以有不同的形式，包括连续需求，间断需求、已知的确定性需求和随机需求等等。无论哪一种形式，一般来说均不受控制。给定了需求形式，系统的输出特性也就相应确定了。补充是系统的输入，补充策略是根据系统的目标和需求方式来确定的。,不同的需求与补充就决定了库存系统的库存状态，它是一个随时间变化而变化的动态过程。库存系统的研究就是为了求解给定系统的动态库存状态，并根据库存状态进行科学的管理与决策。,二、库存系统的参数,库存系统常用的参数如下：1、需求速率D，也称为平均用量，是指材料在单位时间内耗用的平均量。它可以是个定值表示需求稳定也可以是个变量。2、库存量：表示当前的库存状态3、最高存货量M：为特定时间内库存的最高限额，即存量限制的目标。,4、最低存货量L：是备作采购延误或用量突增之用，用来避免停工待料，也称安全存量。5、定货量：每次订货的数量，可以是一个定量，也可以是根据当前库存量而定的一个变量。6、订货提前期B：从货物订购到货物入库所需要的时间，这也往往是个随机量。,7、订货周期长度N：订货时一般使用固定周期，即到一定的时间点做出订货，但也可以是不固定周期，根据库存量I来决定是否订货。8、存储费用库存系统中发生的主要费用可以分为以下三类：,（1）存储费用：应包括搬运、存储、损耗、保险及存货利息等项目（2）缺货损失：单位时间内每单位产品所承担的待料损失（3）订购费用：随每批订货所发生的支出。诸如印花税、报关费、邮电费、验关车费、订购单位的薪金、文具用品等费用。,三、库存状态的动态变化,根据系统参数的特性不同，可以将系统分为确定型库存系统和随机型库存系统。这两类系统的库存状态变化是不同的。,确定库存系统,确定库存系统的需求过程是确定的或者是稳定均匀的，补充过程也是确定的，即订货提前期为零或一个固定的时间段。这类系统可以预先确知其需求特性和补充过程，其存货的控制比较容易，可以通过解析的方法来寻找最佳订货点和订货量以确保库存系统周期内发生的费用最小。,随机型库存系统,随机型库存系统的状态影响因素是随机的、不确定的。其随机性主要表现为需求的随机性和订货提前期的不确定性。不同的库存系统，影响因素的类型是不同的，有的系统仅输入过程或输出过程存在随机性，而更多的库存系统输入和输出两方面都是随机的。,解决随机型库存系统的关键,随机型库存系统中不确定的因素比较多，系统想实现费用最小的目标。可以控制的因素主要是订货点和每批订货量。对于这样的库存系统想做出合适的决策以保证存储费用最小，需要解决的关键问题同确定型库存系统相比有以下不同之处：,1、随机型库存系统关心的是系统生命周期发生的总费用最小，而不是个别存货发生费用最小；2、由于未来期各影响因素的不确定性，做出任何存储决策都是建立在概率预测的基础上；3、寻找的最佳存货量与最佳存货点充分考虑了整个系统生命周期内个因素的影响。,库存系统的基本类型,1、无缺货零提前期批量模型在这种系统中由于缺货损失无限大，不允许出现缺货现象，另外，货物也是可以及时补充的，不需要提前订货，货物随订随到，对这类系统，费用发生仅涉及订货费用和存储费用。,2、有订货提前期和延期交货的库存系统同上一类库存系统相比，有了订货提前期则要求系统提前订货，即在期望货物入库的时间点之前订货。当一个库存系统的缺货费用有限时，允许一定量的缺货将会实现一些经济利益，更有利于存货量的控制。这时候存储费用将包括三方面：存储费用、缺货损失、订货费用,3、制造批量模型在制造批量模型中，货物的入库是一个逐渐的过程，而不像上述几种系统，货物的补充是一次完成的。这种系统中补充过程也会受到不确定性因素的影响，因而补充速度也可能是随机的。当然，上面谈到的订货提前和缺货问题也可能在这类系统中发生。,4、数量折扣模型通常，在采购物品的数量增加时卖主会在出售价格上打一个折扣，当一次采购量达到或超过折扣点时，货物往往会在单价上降低，有时可能会有多个折扣点的存在。,碰到这类问题，库存系统在控制存储费用时，必须考虑折扣因素的影响，加大订货量会增加存储费用，但同时又会减少订货费用并带来折扣优惠，有必要在三者之间权衡。常见的做法是在各折扣价格下找出费用极低的订货量，最后在所有极优订货量中确定出费用最小的量，享受这一订货批量档上的价格优惠。,5、涨价模型当一个库存系统确知在某一未来期货物价格将要上升时，需要存储大量的货物以备未来期的使用，力图降低价格上涨带来的影响。与此同时货物的存储费用也会上升，权衡二者确定最佳存储量是这类模型解决的问题。,库存系统仿真的特点,库存系统的仿真建模需要从如下几方面去考虑一、仿真时钟的步进式推进二、事件类型三、事件表四、费用计算,一、仿真时钟的步进式推进,在库存系统中，由于每个仿真时刻都有需求发生，也就是每个仿真时刻都有事件发生，所以仿真时钟的推进是步进式的每执行完一个时刻的事件后，仿真时钟加一，到来下一个特定时刻，再执行下一个时刻的事件。,虽然在库存系统中每个特定时刻都需执行需求事件但对订货事件与到货事件却不是每个特定时刻都必须执行的，这两个事件应登记在事件表中，当执行完需求事件后再查找事件表，决定是否需执行其他两类事件。,二、事件类型,三、事件表,由于事件类型1即需求事件是每个时刻都发生的事件，所以不登记在事件表中，在事件表中仅登记2类和3类事件。2类事件订货发生的时刻有两种情况，一种是固定间隔N，在T=0时发生一个1类事件，同时产生一个订货事件，在执行订货事件时要计算T当前+T间隔N=T下一次订货，并将下一次订货时间登记在事件表上，此时订货事件是原发事件,在另一种情况下，假如订货时间是根据当前库存量来决定，如当前库存量等于或小于一定的值就需要订货，则订货事件就成了1类事件的后续事件并且是一个条件事件。在执行订货事件时还需要根据到货时间的分布与参数，计算出到货时刻并登记在事件表上。,四、费用计算,在库存系统仿真中还有一个每个时刻必须执行的事件就是费用计算。由于它也是每个时刻就执行的，所以不必列在事件表中，但是在执行完其他所有事件后，必须执行该事件。费用计算就是根据该时刻的库存量计算费用。如有订货则计算订货费用。根据当天是否缺货再计算缺货费用，将这一天所有的费用全计算出来。,报贩问题的仿真,报贩问题：一个报贩前一年年底确定从报社购进的报纸数，报纸以10份为一捆。因此以10为计量单位，每份报纸1.3元买进，以2元卖出。如当天报纸有余量卖不出去，则以0.2元作为废纸卖出，对这个报贩的销售量，首先根据当日的新闻的种类有不同的销量，每日的新闻分为重大、一般和平淡三类。它们发生的概率是0.35,0.45和0.2。,表3.7模拟了进货为70份报纸、20天的销售及利润情况。利润=销售总收入-报纸成本-超过需求的利润损失（缺货损失）+出售废报纸的收入其中缺货损失实际上不是一种真实的损失，而是由于缺货而造成的该得到的利润而没得到的利润，更因为缺货会影响顾客的流失等不利影响，这里将本应得到的每份报纸0.7元利润作为缺货损失。,将20天中的每一天利润相加为72.6元对20天中各费用的总计可得出：总利润=258.00-182.00-5.60+2.20=72.60这是一次仿真的结果，应该进行许多次仿真并将许多次结果进行统计分析，得到当进货为70份报纸时的各种费用与利润。,多周期提前订货折扣的库存系统仿真,一、仿真模型参数1、需求量D的概率函数为,2、订货提前期B的概率函数为,3、折扣,4、缺货损失L,二、费用计算,三、仿真过程,订货点时，发出定单订购固定数量的货物。另外一种方法是当存货量低于订货点时，订货数量为系统允许的最大存货量减去目前的货物存储量，即订货量=最大存储量-目前存储量。这里假设系统采用的是第二种订货策略，每次订货发出尚未到货时不继续发出订货单。,对该系统的仿真以20期为例，考虑折扣点因素，对两种决策进行仿真：1、最大存货量M=120，订货点N=602、最大存货量M=250，订货点N=60两种策略的仿真表分别如表3.8（a）和表3.8（b）,四、仿真结果,当最大存货量为120，对应的10天的存储费用为C=666元，最大存货量为250，对应的存储费用为C=485.5元。总订货量为Q=330,第二种策略可以获得0.1的折扣节约，这样第二种策略下的期间总费用为Ct=666-330*0.1T=336。可以看出，以上两种订货策略相比，第二种策略较优。,仿真设计,一、问题的提出离散事件系统仿真技术是通过真实系统和运行过程来分析一个系统，得到系统的运行状态、性能指标，同时可以预测当系统的外部环境或内部参数发生变化时系统的动态运行状态。,所以离散事件系统仿真是一个系统分析的工具，它为分析离散且随机变化的系统提供了一个分析方法，它是在确定系统结构的前提下求解系统的性能。那么系统分析的逆问题即系统设计是否能采用仿真技术呢？换言之，能否采用仿真技术，根据系统的性能要求设计系统的结构呢？,在排队系统中，系统的性能主要可以分为两大类。一类是系统的服务质量，如等待时间（或排队队长）第二类性能参数是系统的效率，如服务台的忙闲比。这两类性能指标是相关的，为了尽量减少甚至消除排队或等待时间则需要许多服务台，这样造成了服务台效率降低。反之，服务台效率提高则会造成等待时间的增加。,两类排队系统,第一类系统的服务对象是人，人对各类服务的需要组成相应的服务系统。人的要求是系统的到来，这类系统的特点就是到来的不可控。人随机地到来理发店、人随机地要求通话服务，人的到来或呼叫都是随机的。,在这类系统中服务质量即等待时间是第一需要满足的性能参数，在满足允许的等待时间前提下，尽量地提高服务台效率。设计这类系统时第一性能参数是等待时间第二性能参数是服务台效率。,第二类排队系统的服务对象是物，它们的到来是人为安排的，例如各种加工系统。设计这类系统时第一性能指标是服务台效率。希望消除瓶颈加工系统中各加工台都能高效率工作，而等待时间则是第二性能指标。,由于在加工系统中各加工站的加工台数都根据加工节拍设计，仿真数术则是根据性能要求设计各级加工站之间的缓冲的容量，在缓冲器中存放等待加工的零件，在柔性制造系统中根据不断变化的加工要求，设计缓冲的容量是经常遇到的实际要求。,救护系统的仿真设计,救护系统是一个典型的到来不可控系统。当人们提出救护呼叫后，非常关心救护车辆及人员的到来，其等待时间有严格的要求。根据允许的等待时间设计城市救护系统，即设计救护系统的配置是其仿真设计的内容。,救护系统,每个城镇都有救护系统，救护系统由若干个急救站组成，每个急救站配有若干辆救护车，每辆救护车又配备救护人员和急救材料。,救护系统的工作流程如下：需要救护的人打专门电话给急救中心，急救中心根据被救护人的地址告知所在地的急救站，急救站在某时刻接到一个急救呼叫、在得知对方所处位置及有关病情后，派出本站的一辆空闲救护车以及相应的医护人员和医疗设备，赶往呼叫所在地（病人所在地），在对病人做出初步诊断、急救处理后，送往医院做进一步治疗，救护车放下病人后返回急救站，等待下一次救护呼叫,从上面的急救过程描述可知，一般情况下救护车的服务时间(从出发到返回)明显分为五段：从急救站出发到病人所在地时间(TI)在病人所在地处理病人的时间(T2)将病人送到医院的时间(T3)在医院停留(将病人送下救护车)的时间(T4)从医院返回急救站的时间(T5)。如图所示,如无空救护车那就通知正在返回路途的救护车不回急救站直接去病人所在地。,这里需要强调两个概念：(1)救护车的等待时间(WT)是指从顾客发出求救信号到救护车从某地开始出发进行服务的一段时间。这段时间并不是每个顾客都有，故以虚线表示；(2)系统的响应时间就是指救护车的等待时间和时间TI之和。即顾客实际得到急救处理之前需要等待的时间；,救护车、救护人员和急救材料组成一个救护单元,二、单急救站系统的仿真设计,对只有一个急救站的救护系统设计只需根据允许的等待时间及呼叫服务的频率设汁这个急救站的配置数N、这是一个服务台移动的单级多服务台系统。站中救护单元(即服务台结构)数N是救护系统的惟一变量。运用传统仿真技术将配置数从1到N进行逐一试探、模拟得到满足等待时间的最小服务台数，这就是这个救护站的配置，但它需要N次仿真、如图313(a)所尔。,这种逐一枚举的方法费时、费力。而且当面对多个相互支援急救站的救护系统时就无法逐一枚举了如图3.13(b)中表示，采用逆向仿真技术一次仿真就能得到服务台个数。,在仿真设计时，同样模拟顾客的到来，即顾客对救护系统的呼叫。但在到来后，首先根据允许的等待时间WT判断现有配置是否能有车及时到来呼叫地点,若有车则救护单元数不变，模拟它的救护过程，如在现有配置数下不能有车及时到来呼叫地点即现有配置不能满足救护要求则将配置数加一，即派一辆新车去呼叫地进行救护，依次类推。,在传统仿真中，服务台结构即服务台数目是始终不变的，但在用于设计的仿真中服务台数目是变化的。在到来这一特定时刻，有时服务台数目不变，表示现有服务台数已能为这次到来按时服务。有时则会增加一个服务台数目，表示原有的服务台不能按时服务，需要增加新的服务台来为此呼叫服务。,特定时刻服务台数的变化,多急救站的仿真设计,一个城市往往有若干个救护站，大城市甚至有几十个救护站，各站构均设有一定的配置，并共同组成一个救护系统。所以对整个城市的救护系统的仿真不仅仅是对一个站、一个区的运行进行模拟，而是对整个城市救护系统的运行进行模拟。这时应如何来设计十几个甚至更多救护站的配置呢?,采用传统的离散事件系统仿真技术设计这一救护系统时，各站的配置数都是某一范围内的各个值，由于它们的组合数太多，逐一仿真的工作量极大，以致不能实现。,采用前面论述的方法对这类逆问题进行求解，不用多次试探，而可以一次性得到其结果。这时与传统仿真不同，当救护呼叫产生后，不是直接模拟排队、服务的正向运行过程，而是首先根据允许发出呼叫后救护车该到来救护地的允许最晚时刻(LAT)，以这个时刻为依据判断本站及可能的邻站是否能及时给予服务，如能则立即开始或等待服务，如不能则在本站增加一套服务单元进行服务。,多站救护系统接受服务子程序框图,这类仿真设计中，其他处理如初始化，结果统计分析等都与传统仿真相同。同样，由于随机数的引入，一次仿真仅仅得到一次样本值，多次样本值的均值就是逆向仿真结果，即救护系统中各站的配置。,这样，用逆向仿真方法就一次性得到了多站救护系统的配置，实现了对这一复杂的排队系统的设计。多个急救站组成而且部分地区可支持的救护系统是最常见最实用的救护系统。它是采用逆向仿真技术进行系统设计的典型例子。,生产网络缓冲器容量的仿真设计,一、生产系统的缓冲器,生产系统是由若干加工单元(或机器)和相关的缓冲器单元通过材料处理系统联系起来的系统 系统中每个加工站在运行期间可能发生可修复的故障，缓冲器的容量是有限的。工件在系统中流动，且离开一级工作站到进入下一级工作站之前要流经缓冲器。,在生产系统中，当各工作站的生产率不协调、工件在各工作站的单件加工时间随机波动时，会造成系统加工状态的随机波动，而且各加工站的故障发生也是随机的。这样就会造成系统工作不连续、不平稳，工作站对工件的加工时而中断、时而继续，因此加工系统是一个随机系统而不是确定则系统。,工作站在运行期间，其状态是由一些离散时间点上发生的特定的事件如开始加工、结束加工等)来改变的，因而可以认为加工系统是一个典型的离散事件系统。,工作站的失效,工作站不能正常工作称为工作站失效。在生产系统中，工作站的失效有三种情况：1、工作站加工完一个工件并输出到下一级后，可以开始对下一个工件的加工，这时若本站前面的缓冲器为空将造成工作站空闲，称为空闲待料，这与上级工作站的生产率直接相关,2、本站后面的缓冲器全满使工作站加工完毕的工件无法输出而造成工作站阻塞停工，这是由该工作站的实际生产率与下级工作站的生产率的差异和缓冲器容量决定的3、工作站本身发生故障而失效,工作站空闲待料的消除,由工件单件加工时间随机波动导致的工作站空闲待料可以通过在本站前面的缓冲器中预先放置一定数量的待加工工件来减少或加以消除,工作站阻塞停工的消除,由工件单件加工时间随机波动导致的工作站阻塞停工，则可以通过加大本站后面的缓冲器容量来实现。缓冲器能够在一定程度上减少加工系统中停工待料和阻塞现象，增强系统工作的连续性和平稳性，从而提高效率。,但，缓冲器容量及预置工件数量的增加又会增加系统中在制品的库存，从而是成本增加。因此，在加工系统中，合理设计缓冲器来提高系统效率是一个十分重要的问题。,缓冲器容量问题建模现状,1、用极大代数方法建立串行（流水线型）加工系统的“线性模型”2、用极大代数的方法给出了加工系统的托盘及缓冲的优化方法3、用Petri网来分析加工系统中缓冲器的配置，解决了系统的死锁和冲突问题。4、用近似方法来估计缓冲器容量。5、运用马氏随机过程进行研究。,现有研究方法的缺点,1、代数方法没有考虑系统的随机性2、Petri网作为一种图形化工具，对系统的分析是有效的，但对“缓冲器容量设计”这一设计问题显得无能为力。所以，近似方法成为探讨的热点。,单一品种生产网络的分解,与级联生产系统不同，生产网络中的任何一个节点(加工站)都可以有若干个前驱及后续加工站，系统的结构表现为网络形式。系统有多个输入(原材料）但只有一个输出(单一品种生产网络假定)，虽然任何一个输入可能不流经系统中所有的节点，但其流动的路线是确定的。,为行文方便，下文将加工站此后面的缓冲器6n称为本级缓冲器而将44n的前驱加工站后丽的缓冲器称为前级缓冲器例如在团318中对从来说*B1是本级缓冲器B2、B5为前级缓冲器。,这里规定：将加工站Mn此后面的缓冲器Bn称为本级缓冲器，而将Mn的前驱加工站后面的缓冲器称为前级缓冲器。,系统中的加工站有“瓶颈“和“非瓶颈”之分。“瓶颈”是制约系统产量的关键，系统的实际生产率取决于“瓶颈”站的实际生产率，且系统的最大生产率只能达到“瓶颈”站的极限生产率。极限生产率是指加工机器在正常状态下能够达到的生产率的极限，即加工站除故障外、将始终处于工作状态，无空闲待料和阻塞停工现象。系统中极限生产率最低的加工站即为此系统的“瓶颈”站。,“瓶颈”站与“非瓶颈”站之间的关系,类型1：工件从“瓶颈”流向“非瓶颈”站。为提高系统效率、瓶颈站的利用率达到100，而”非瓶颈”站的到来率只能小于100系统的效率取决于“瓶颈”站的效率；,类型2：工件从“非瓶须”站流向“瓶颈”站，此时”非瓶颈”站的利用率必然没有达到100、虽然“非瓶颈”站尚有能力增加产量，但其结果只会增加“瓶颈”站待加工的库存量，而不能增加系统的产出量,类型3：假设“非瓶颈“站C要使用“瓶颈”站A与“非瓶颈”B所加工的工件，“瓶颈”站A的能力已经100利用，”非瓶颈”站B不必利用100的能力。此时，虽然可增加“非瓶颈”站B的利用率以提高其产量，但由于“瓶颈”能力限制“非瓶颈”站C的产量的提高、最终产品的产量不可能增加。,在级联生产系统中，“瓶颈”站与“非瓶颈”站之间仅存在类型1和类型2两种关系，可见级联生产系统是生产网络的特殊形式,一个典型的单一产品生产网络,确定系统中那些站是“瓶颈”站，那些站是非“瓶颈”站后，可以将生产网络分解为两部分：一个是关键资源部分，它包括由“瓶颈”站开始直至最终产品交给用户的部分。其余的是非关键资源部分。,为使“瓶颈站利用率达到100，在关键资源部分，采用推动型生产方式：由“瓶颈”站开始向后安排生产，只要前级加工站后面的缓冲器(前级缓冲器)中有工件，则后级加工站就从中取出工件进行加工后级的生产是由前级加工站推动起来的)。,在非关键资源部分，采用拉动型生产方式，仅当后级加丁站对前级加工工件有“需求”时，前站才进行进产。这样的原则一方面是为了支持关键资源保证关键资源最大限度地利用，使系统获得最大产出，另一方面是为厂使缓冲器的配置最小化，从而降低系统中在制品的库存,三、仿真设计算法,对生产网络进行仿真，首先提出如下假设：假设1：各工作站一旦出现故障能得到立即修复，修复后工作站完全恢复工作。假设2：工件流入或者流出缓冲器的时间很短，相对于其加工时间来讲，可以忽略不计。,假设3：首级工作站原材料充足，末级工作站无阻塞情况，可随时输出假设4：任一工作站在因阻塞或缺料停车待命期间不发生故障。,非关键资源部分拉动型生产，即只有当后级加工站产生”需求”时、本站才进行加工，否则等待；若本站不能满足后站的“需求”，则本级加工站后面的缓冲器(本级缓冲器)容量加一，预置工件数加一。,关键资源部分推动型生产方式。只要本站的前级缓冲器中有工件，则本站一有空闲就进行加工，否则等待；若本级缓冲器已满使得加工完毕的工件不能输出，造成阻塞则本级缓冲器容量加一。,这里的“需求”是通过各级加工站后面的缓冲器(本级缓冲器)中工件的数量来反映的。若本级缓冲器末满，则认为后级加工站对本级加工站的零件有需求，本站将进行加工；否则，认为没有需求，本站等待。这样做的目的是为了充分利用系统中缓冲器资源，以便即使在某站发生故障时，其后面的加工站仍然可以从缓冲器中取走工件进行加工从而减小系统的随机波动，提高系统的运行效率。,加工系统中主要有两类事件，一类是开始加工事件，一类是结束加工事件。按照关键资源部分采用推动型生产方式，非关键资源部分采用拉动型生产方式的原则，单一产品生产网络缓冲器设计的仿真算法如下：,变量说明,prenum 为加工站的前驱加工站的个数；prei 为加工站的第I个前驱加工站；nextmum 为加工站的后续加工站的个数；nexti 为加工站的第I个后续加工站；firstTrue为首加工站；keyTrue 为关键资源部分的加工站,1、开始加工事件处理程序,STEPl：根据当前开始加工的加工站的加工时间的概率分布随机确定其加工时间；进行故障处理；产生本加工站的剩余可加工时间；计算本站结束加工时刻，产生结束加工事件，并将其插入事件处理队列中。STEP 2：根据各加工站的类型进行相应的处理：,Step 3:将本事件从事件队列中删除,2、结束加工事件处理程序,STEP 1：根据各加工站的类型作相应的处理STEP 2：将本事件从事件队列中删除,故障的处理,前面假设加工机器在空闲时不损耗机器因此这里不把加工机器的非工作时间如空闲时间)包含在故障间隔期内，这里所指的故障间隔期为连续两次故障之间允许加工机器工作的时间长度。从系统运行的初始时刻起、分别产生各加工机器到下一故障发生时的可正常工作时间(即故障间隔时间)。,每开始加工一个工件，加工机器的剩余可工作时间就应减去加工该工件时间，当加工机器的剩余可工作时间小于工件加工时间时，说明故障将发生在工件的加工过程中，加工该工件的持续时间应为工件的加工时间加上加工机器的修复时这时还应该产生该加工机器到下一故障发生时刻的可工作时间和对应的故障修复时间。这一处理过程在开始加工事件处理程序的STEP l中进行。,算法中的几点问题,1、如前所述，在关键资源部分的加工站采用推动型生产方式，对非关键资源部分的加工站采用拉动型生产方式。那么对于一个特定的加工站来说，其生产是如何激发的?也就是如何推动或拉动的？,对于非关键资源部分的加工站，其生产在以下两种情况下激发：一是后续加工站开始生产，从本级缓冲器中取走一个工件。此时本级缓冲器必然不满，即后级加工站对本级加工站的工件有“需求”，若本级加工站空闲，则激发本级加工站开始生产。,二是在本级加工站加工完一个工件后，若本级缓冲器不满，则立即产生一个本级加工站开始加工事件，激发本站开始生产。,对于关键资源部分的加工站，其生产也在两种情况下激发：一是其前驱站加工完毕一个工件后，若本站所有属于关键资源部分的前驱缓冲器不空，则推动本站开始生产。二是本站加工完毕后、若本站所有属于关键资源部分的前驱缓冲器不空，则将推动本站开始生产。,2、各级缓冲器容量是如何动态改变的,由于算法要保证“瓶颈”站在非故障期内既不空闲待料，也不阻塞，而“瓶颈”站空闲的原因是其前驱加工站不能及时供给其所需的工件、“瓶颈”站阻塞的原因是其后向的缓冲器已满，造成“瓶颈”站加工完毕的工件不能及时输出。,因此对于非关键资源部分的加工站，当其不能满足后级加工站的需求时，则其缓冲器容量加一，预置工件数加一。对于关键资源部分的加工站，若加工完毕后，发现其后面缓冲器巳满，则其缓冲器容量加一。,3、若某级加工站有多个前驱，本算法假定对各前驱所加工的工件的需求是均等的。若某级加工站有多个后续，本算法假定各后续没有优先顺序，采用先来先服务的原则。在实际问题中，可针对具体要求对本算法做相应地修正。,4、本算法完全适用于级联生产系统，级联生产系统是网络生产系统的特例。其中“瓶颈”与“非瓶须”之间的关系仅有图3.17中的类型1和类型2两种情况。,