ACD的建模方法

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