ACD的建模方法.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,ACD,的建模方法举例,假设有一个系统，它有两类实体机床和工人。,机床是半自动的，需要一个工人去安装（,SETUP,）,工件。然后机床可以自动的对工件进行加工（,RUN,），,直到加工完毕，机床停止。,此时若有一个工人可用来安装工件，就可以开始一次新的循环。,因此，半自动机床这一类实体就有,SETUP,和,RUN,这两种活动，两个等待状态（队列）,IDLE,（,空闲）和,READY,（,就绪），其活动循环图如,图,4.19,所示。,1,图,4-19,机床的活动循环图,2,现在对另一类实体工人进行分析，假设工人只担负一项任务,安装工件，即工人只参加一个活动,SETUP,，,则这一类实体的循环图如,图,4.20,所示。,3,图,4.20,工人活动循环图,4,在完成了各类实体的活动循环的分析和绘制之后，就应当将它们综合成一个系统的活动循环图，如图,4.21,所示。,在此图中，表示机床的活动循环；,0,0,0,表示工人的活动循环。,5,图,4.21,系统的活动循环图,6,对于合作活动，只有当参与合作活动的实体都在该活动的前置队列中存在时，此活动才能开始。,在,图,4.21,中，如果合作活动,SETUP,要开始，则必须有一个工人在队列,WAIT,中和一台机床在队列,IDLE,中才行。如果其中之一不在而另一个在，则后者将被迫在队列中等待。,这种被迫等待，通常会使系统的性能严重下降。,7,当一个活动开始时，相应的实体从队列中移到该活动中。,在,ACD,图上，可以使用标志来代表实体。这样，就可以用该标志在活动循环图中的位置来代表实体的状态，用它从队列到活动中的移动来模拟上述的移入动作。,当模拟的活动周期结束时，标志再从该活动移入相关的后续队列。,一个活动完成后，释放其后续活动所需的实体，并使后续的活动有了开始的可能。在本例中,READY,队列是虚拟队列，,SETUP,是合作活动。,8,活动循环图是按照实体类的行为模式建立的，它与实体类中的实体数量无关。,例如在本例中，它与机床数及工人数都无关。换言之，这个活动循环图可以应用于机床数和工人数较多的系统，以模拟一个大的制造系统；反之，也可以用来模拟一个小的制造系统。,因此，只要系统的行为模式相同，即使它们的实体类型和活动周期不同，都可以用同一个活动循环图来描述。,9,ACD,图仿真所需的信息,在建立,ACD,图后，如要进行仿真，还需要以下三种信息：,（,1,）每一个活动的周期值（即活动持续时间）。它可以是一个常数，如,图,4.21,中的,D,10,；,一个计算值（如,5,乘以机床主轴数）；一个随机变量（如负指数分布函数的随机采样值），或者是上述数值的组合。,10,（,2,）每一个队列的排队规则。排队规则可采用先进先出，后进后出，等级高者先出或其它的优先规则。“等级高者”规则按实体的属性决定其优先等级，如效率最高的工人优先；最不耐心的顾客优先等。,在活动循环图中，若没有指明排队规则，则表示默认的规则是先进先出。,11,（,3,）系统仿真的初始条件。在确定仿真的初始条件时，应尽量避免使系统处于“空闲状态”。因此，应该尽可能的使初始状态接近系统的稳态。,在,ACD,图上，应该恰当地给出每个实体的初始位置（既可以给定于队列中，也可以给定于活动中）。但是要注意，如果实体放在合作活动中，必须保证该活动要求参加的所有实体均已放入。,12,仿真分析规则和人工仿真运行,现在以,图,4.22,中的活动循环图为例，来讨论系统仿真的进程和仿真分析的规则。,假设该系统由,3,台半自动机床（以、为标志）和一个工人组成，活动周期是固定的（,SETUP,为,3,，,RUN,为,10,），排队规则均为先进先出。,13,初始时钟,CLOCK,值定为零。系统的初始条件为：工人处于,WAIT,（,等待）队列中，三台机床位于,IDLE,（,空闲）队列中。这个初始条件即前述的系统空闲状态，要达到系统运行稳态，还有一段过渡过程。,图,4.22,给出了,CLOCK,0,时的系统状态。,14,图,4.22,时钟值为零时的系统状态,15,在设定系统初始状态后，系统的仿真运行即可按下列的规则推进：,1,）规则,1,（,C,相）,依次检查每一活动，以判断此活动是否可以开始，即此活动所要求的足够的实体集合，是否已经存在于所有有关的前置队列中。,如果含有，则将这个实体集合的标志移入此活动的矩形中，且计算出此活动的终止时间（它等于当前的时钟值加上此活动的周期）并将此时间值写在该活动的矩形内。,16,当所有活动都检查完后，转向规则,2,。,2,）,规则,2,（,A,相）,检查所有活动的终止时间，选其最小值，并设置时钟值为此选择值，然后，转向规则,3,（除非时钟值超过了预定的仿真终止时间）。,在此例中，这个最小值是,3,，当前的时钟值等于,3,。,17,3,）,规则,3,（,B,相）,比较每一个活动的终止时间是否等于当前时钟值（从规则,2,可看出，至少有一个活动的终止时间等于当前时钟值）。,对每个终止时间等于当前时钟值的活动，删除其在,C,相（规则,1,）时写于矩形内的终止时间，并将此活动矩形内的实体标志移入其相关的后续队列，然后转向规则,1,。,18,在此例中，现在,SETUP,结束，工人返回到,WAIT,队列，机床,1,走,到,READY,队列中，其直联活动,RUN,也可以开始了，这种情况显示于,图,4.23,中。接着，使用规则,1,，,SETUP,活动又可以开始。,19,图,4.23,时钟值为,3,时的系统状态,20,图,4.24,给出系统在时钟值为,6,时的状态。在这个时间点上，机床,1,在加工（到时钟值为,13,时要结束），机床,2,立即开始加工，而机床,3,还没有安装。,21,图,4.24,时钟值为,6,时的系统状态,22,表,4.1,时钟值,0,至,30,之间的变化,时间,开,始,结,束,安装,SETUP,加工,RUN,安装,SETUP,加工,RUN,0,(3),3,(6),(13),6,(9),(16),9,(19),13,(16),23,16,(19),(26),19,(22),(29),22,(32),26,(29),29,(32),(39),24,4.4,排队系统,经典随机服务系统理论，即排队论，源于,Erlang,关于电话的研究。,第二次世界大战后得到迅猛发展，成为随机运筹学与概率论中最有活力的研究课题。,它不仅建立了比较完备的理论体系，而且在军事、生产、经济、管理、交通、通讯、网络等领域得到了广泛应用。,25,排队系统的基本概述,排队系统必须经过三个环节，即到达、排队等候处理,(,服务,),、离去。,如图,4.31,所示为单服务员排队系统模型。,26,图,4.31,单服务员排队系统模型,27,一些基本概念,一、排队系统的输入过程分类有：,(1),按照顾客相继到达时间间隔可分为确定型和随机型；,随机型到达采用概率分布来描述，最常用的是泊松到达。,若采用平稳泊松过程描述，则有：在,内到达的顾客数,k,的概率为：,28,其中，表示在 区间内到达顾客的个数；,为到达率。,若顾客到达满足平稳泊松过程，则到达时间间隔服从指数分布，其密度函数为：,其中,为到达时间间隔的均值。,29,(2),按照顾客到达系统的方式可以逐个或成批；,(3),按照顾客到达系统可以是独立的或相关的,输入过程可以是平稳、马氏、齐次的。,30,二、排队系统的排队规则,(1),先到先服务,顾客按照到达次序接收服务；,(2),后到先服务,例如乘坐电梯时，顾客总是后进先出的。仓库中堆放的大件物品也是如此。在情报系统中，最后到达的信息往往是更有价值的，因而常常采用后到先服务的规则；,31,(3),随机服务,当服务台空闲时，从等待的顾客中随机,选取一名顾客进行服务，而不管到达的,先后次序；,(4),优先权服务,例如医院中急诊病人优先得到治疗,32,(5),多个服务台,当顾客到达时，可以按照如下规则在每个服务台前排成一队，第,1,，,n+1,，,2n+1,，,个顾客排入第一个队，第,2,，,n+2,，,2n+2,，,个顾客排入第二个队等等。,或者所有顾客排成一个公共的队，每当有一个服务台空闲时，队首的顾客进入服务。也可以这样排成,n,个队，当某个顾客到达时，以概率,排入第 队 。,33,三、排队系统的服务机构,(1),系统可以一个窗口或多个窗口为顾客进行服务；,(2),各窗口的服务时间可以是确定型或随机型。若服务时间为随机型的，顾客在系统内逗留的时间均值 ；顾客排队等候服务的时间均值 ；服务时间的均值,t,；,显然 。,34,排队系统的性能指标,一般情况下，我们都是用以下三个指标来评价排队系统的性能：,顾客在系统内的平均等待时间；,系统的平均队长；,服务利用率。,35,单服务员排队系统的仿真方法,对于排队服务系统，顾客往往注重排队顾客是否太多，等待的时间是否太长，而服务员则关心他的空闲时间。,从上面我们知道,队长、等待时间以及服务利用率,等指标可以衡量系统性能，下面介绍已知顾客到达时间和服务时间的统计规律（往往来自实际数据或一定的概率分布），来仿真排队系统。,36,系统的假设,1),顾客源是无穷的；,2),排队长度没有限制；,3),到达系统的顾客按先后顺序依次进,入服务。,两位顾客先后到达系统的时间间隔,i,是随机变量，每位顾客的服务时间,s,也是随机变量，它们的概率分布已经根据经验或理论假设确定。,37,状态变量的设置,根据两个概率分布，可以生成任意多个到达系统的时间间隔,i,与服务时间,s,的数据，记,表示第,k,位顾客与第,k-1,位顾客到达时间间隔，表示第,k,位顾客服务时间。,在任意时间,t,，,系统状态可以用排队等候的顾客数目和服务员是否在工作来描述。排队等候的顾客数目称为队长，记作,L(t),。,服务员的状态用,S(t),表示：当服务员工作时，令,S(t,)=1,，,服务员空闲时，令,S(t)=0,。,38,引起系统状态,L(t),和,S(t),改变的行为称为事件。,在排队系统中包含两类基本事件：,“顾客到达”,和,“顾客离开”,。记表示第,k,位顾客到达时刻为 ，离开时间为 ，根据已知的 与 ，按照以下的递推关系得到：,39,仿真的初始和终止条件,系统状态在到达时刻 ，离开时刻 将发生变化。,在模拟系统运行中，设置时钟,t,，让,t,依事件发生的先后顺序，从一个事件的发生时刻到下一个事件的发生时刻，这种仿真模式称为下一事件时间推进法。,初始和终止条件可设为：,t=0,是第一位顾客到达时刻，仿真终止时刻是给定的时刻,T,。,40,仿真过程的运行,首先根据时间间隔,i,和服务时间,s,的概率分布生成随机数 与 ，再根据递推关系,计算到达时刻 和离开时间 ，然后让时钟,t,按照 和 从小到大的顺序推进，一般不是生成,i,或,s,待用，而是在时钟,t,推进到某一事件发生时，才生成所需的,i,或,s,。,41,设当前时钟为,t,，,在每一个事件发生时，需要设置、并记录以下四个量的数值：队长,L,，,服务员状态,S,，,t,以后下一个“顾客到达”事件的发生时刻记作,ARRIVETIME,，,t,以后下一个“顾客离开”事件的发生时刻记作,DEPARTTIME,。,仿真流程图见下图：,42,43,Matlab,仿真的主程序,%,定义全局变量,global Q_LIMIT,mean_interarrival,mean_service,mean_delays_required,global next_event_type,num_custs_delayed,num_delays_required num_events num_in_q server_status,global area_num_in_q area_server_status,mean_interarrival,mean_service time_arrival.,time_last_event time_next_event total_of_delays,44,%,以下为输入参数,%,mean_interarrival,平均到达时间,%mean_service=,平均服务时间,%mean_delays_required=,等待的顾客数,%area_server_status=,系统状态,%num_events=,事件类型,%Q_LIMIT=,仿真队列的限制,%,num_custs_delayed,=,服务的顾客数,45,Q_LIMIT=200;,mean_interarrival,=1.0;,mean_service=0.5;,mean_delays_required=100;,area_server_status=0;,num_events=2,46,主程序,INIT;%,执行初始化过程,while(num_custs_delayed,mean_delays_required),TIMING;%,安排下一事件,UPDATE;%,更新排队系统,if(next_event_type=1),ARRIVE;%,处理顾客到达程序,elseif,(next_event_type=2),DEPART;%,处理顾客离去程序,end,end,REPORT;%,生成报告,47,INIT,，,TIMING,，,UPDATE,，,ARRIVE,，,DEPART,，,REPORT,是仿真的主程序中调用的子程序,(,它们对应功能在主程序中已经作了解释,),，以上是整个仿真程序的框架。,48,