第5章 制造系统的仿真方法 系统仿真课件 广东工业大学 工业工程系_

1第5章制造系统的仿真方法5.1制造系统的调度策略25.1制造系统的调度策略¾仿真钟推进机制仿真钟推进方法有两大类：z事件调度法，即按下一最早发生事件的发生时间推进；z固定增量推进方法。35.1制造系统的调度策略¾三种仿真调度策略：事件调度法、活动扫描法、进程交互法。45.1制造系统的调度策略¾主要术语：z成分（Component）：相应于系统中的实体，用于构造模型中的各个部分，可分为两大类：¾主动成分（Active-typeComponent）：可以主动产生活动的成分。如排队系统中的顾客，它的到达将产生排队活动或服务活动。¾被动成分（Passive-typeComponent）：本身不能激发活动，只有在主动成分作用下才产生状态变化。55.1制造系统的调度策略¾主要术语：z描述变量：成分状态、属性的描述。z成分间的相互关系：描述成分之间相互影响的规则。在一个模型中，主动成分对被动成分可能产生作用，而主动成分之间也可能产生作用。C＝{α1.α2,…,αn}成分集合，αi是第i个成分分量(1≤i≤n)。CA＝{α1.α2,…,αm}主动成分子集，αj是第j个成分分量(1≤j≤m,m＜n)。CP＝{α1.α2,…,αl}被动成分子集，αk是第k个成分分量(1≤k≤l,l＜n)。一个模型中，n=m+l65.1制造系统的调度策略¾主要术语：S所有成分的状态变量。P={p1,p2,…,pn}参数(属性)集合。tα成分α的状态下一发生变化的时刻。Dα(S)：判别成分α在状态变量值为S时的条件是否满足。Dα(S)=true，表示满足，Dα(S)=false，表示不满足。TIME模型仿真钟的值。75.1制造系统的调度策略¾事件调度法：„事件调度法基本思想：用事件的观点来分析真实系统，通过定义事件及每个事件发生引起系统状态的变化，按时间顺序确定并执行每个事件发生时有关的逻辑关系。所有事件均放在事件表中。模型中有一个时间控制成分，该成分从事件表中选择具有最早发生时间的事件，并将仿真钟修改到该事件发生的时间，再调用与该事件相应的事件处理模块，该事件处理完后返回时间控制成分。这样，事件的选择与处理不断地进行，直到仿真终止的条件或程序事件产生为止。85.1制造系统的调度策略¾事件调度法：„策略的描述：成分集合C＝{α1,α2,…,αn}主动成分集合CA＝{α1,α2,…,αm}被动成分集合CP＝{αm+1,αm+2,…,αn}95.1制造系统的调度策略¾事件调度法：„策略的描述：描述变量：描述每一主动成分α∈CA的变量α的状态sαsα下一变化时刻的时间变量tα描述每一被动成分α∈CP的变量α的状态sα(被动成分的状态变化只有在主动成分作用下才能发生,其发生时间由主动成分来确定,因而不需要时间变量。)105.1制造系统的调度策略¾事件调度法：„策略的描述：描述变量：描述所有成分的属性的变量参数集合P={p1,p2,…,pr}115.1制造系统的调度策略¾事件调度法：„策略的描述：成分间的相互关系：主动成分对被动成分产生影响，主动成分也会对主动成分产生影响；各成分处理的优先级，即同时发生时的处理顺序（解结规则）。注意，在事件调度法中，一般主动成分也同时具有被动成分属性，以便接受其它主动成分的作用。125.1制造系统的调度策略¾事件调度法：„事件调度法算法：执行初始化操作，包括：置初始时间t=t0，结束时间t∞=tg事件表初始化，置系统初始事件成分状态初始化：操作事件表，包括取出具有t(s)=min{tα|α∈CA}事件记录修改事件表推进仿真钟TIME=t(s)135.1制造系统的调度策略¾事件调度法：„事件调度法算法：whilewhile((TIMETIME==tt∞∞))则执行则执行casecase根据事件类型根据事件类型iiii=1=1执行第执行第11类事件处理程序类事件处理程序i=2i=2执行第执行第22类事件处理程序类事件处理程序……i=mi=m执行第执行第mm类事件处理程序类事件处理程序endcaseendcase取出具有取出具有t(s)=min{tα|α∈CA}事件记录事件记录置仿真时间置仿真时间TIMETIME==tt((ss))endwhileendwhile145.1制造系统的调度策略¾活动扫描法：„活动扫描法基本思想：事件调度法中仿真钟的推进仅仅依据准则，而该事件发生的任何条件的测试必须在该事件处理程序内部去处理。如果条件满足，该事件发生，否则，则推迟或取消该事件发生。从本质上来说，事件调度法是一种“预定事件发生时间”的策略。这样，仿真模型中必须预定系统中下一最先发生的事件。该策略对于活动持续时间确定性较强（可以是服从某种分布的随机变量）的系统是比较方便的。}min{)(ACtst∈=αα155.1制造系统的调度策略¾活动扫描法：„活动扫描法基本思想：当事件的发生不仅与时间有关，而且与其它条件有关，即只有满足某些条件时才会发生。在这种情况下，事件调度法策略的弱点则表现出来了，由于这类系统的活动持续时间的不确定性，因而无法预定活动的开始或终止时间。165.1制造系统的调度策略¾活动扫描法：„活动扫描法基本思想：活动扫描法的基本思想是：用活动的观点建模。系统由成分组成，而成分包含着活动，这些活动的发生必须满足某些条件；每一个主动成分均有一个相应的活动子例程；仿真过程中，活动的发生时间也作为条件之一，而且是较之其它条件具有更高的优先权。175.1制造系统的调度策略¾活动扫描法：„活动扫描法基本思想：设Dα(S)表示成分α在系统状态S下的条件是否满足的判定条件(Da(S)=true则表示满足，Da(S)=false则表示不满足)，tα表示成分α的状态下一发生变化的时刻，活动扫描法每一步要对系统中所有主动成分进行扫描，当：(1)tα≤仿真钟当前值TIME，且(2)Dα(S)=true时,执行该成分α的活动子例程。所有主动成分扫描一遍后，则又按同样顺序继续进行扫描，直到仿真结束。显然，活动扫描法由于包括了对事件发生时间的扫描，因而它也具有事件调度法的功能。185.1制造系统的调度策略¾活动扫描法：„实现措施：1.设置系统仿真钟TIME与成分仿真钟tα系统仿真钟表示系统仿真进程的推进时间，而成分仿真钟则记录该成分的活动发生时刻，两者的关系可能有三种情况：(i)tαTIME表示该活动在将来某一时刻可能发生了；(ii)tα=TIME表示该活动如果条件满足则应立即发生；(iii)tαTIME表示该活动按预定时间早应发生，但因条件未满足,到目前为止实际上仍未发生，当前是否发生，则只要判断其发生的条件。195.1制造系统的调度策略¾活动扫描法：„实现措施：2.设置条件处理模块该模块用于测定的Dα(S)值及系统仿真钟与成分仿真钟之间的关系，记FUTURE(S)={α|tαTIME}，PRESENT(S)={α|tα=TIME}，PAST(S)={α|tαTIME}该模块将满足下列条件：(i)α∈PRESENT(S)∪PAST(S)，且(ii)Dα(S)=true的成分置于可激活（ACTIVATABLE）的成分集合中，即205.1制造系统的调度策略¾活动扫描法：„实现措施：2.设置条件处理模块此时，系统仿真钟不推进，仅仅处理成分活动，包括修改成分仿真钟。如果可激活的成分集合为空，则将系统仿真钟推进到下一最早发生的活动生成时刻，即TIME=min(ta|α∈FUTURE(S))()()()()PRESENTSPASTSACTIVATABLESDStrueααα⎧∈∪⎪=⎨=⎪⎩215.1制造系统的调度策略¾活动扫描法：„实现算法：执行初始化操作，包括：置初始时间t=t0，结束时间t∞=tg设置主动成分的仿真钟tαi(i=1,2,…,m)成分状态初始化：111((,),,(,),,,)mmmnSststssαααααα+=225.1制造系统的调度策略¾活动扫描法：„实现算法：设置系统仿真钟TIME=t0While(TIMEt∞)，则执行扫描forj=最高优先数到最低优先数将优先数为j的成分置成iIf(tαiTIME且Dαi(S)=true)执行活动子例程i退出，重新开始扫描endifendforTIME=min(tα|α∈FUTURE(S))endwhile235.1制造系统的调度策略¾活动扫描法：„策略核心：建立活动子例程模型，包括此活动发生引起的状态变化（自身的），对其它成分的状态产生的作用等等。„条件处理模块：策略实现的本质，它相应于事件调度法中的定时模块。245.1制造系统的调度策略¾进程交互法„进程交互法基本思想：进程交互法采用进程（Process）描述系统，它将模型中的主动成分所发生的事件及活动按时间顺序进行组合，从而形成进程表，一个成分一旦进入进程，只要条件满足，它将完成该进程的全部活动。255.1制造系统的调度策略¾进程交互法„进程交互法基本思想：系统仿真钟的控制程序采用两张事件表，其一是当前事件表（CEL：CurrentEventsList），它包含了从当前时间点开始有资格执行的事件的事件记录，但是该事件是否发生的条件（如果有的话）尚未判断，其二是将来事件表（FEL：FutureEventsList），它包含在将来某个仿真时刻发生的事件的事件记录。每一个事件记录中包括该事件的若干属性，其中必有一个属性，说明该事件在进程中所处位置的指针。265.1制造系统的调度策略¾进程交互法„进程交互法仿真钟推进z满足tα≤TIME的所有事件记录从FEL移到CEL中z对CEL中的每个事件记录进行扫描z对于从CEL中取出的每一个事件记录9首先判断它属于哪一个进程以及它在该进程中的位置；9该事件是否发生则决定于发生条件是否为真；‡若Dαi(S)=True,则发生包含该事件的活动；只要条件允许，该进程要尽可能多地连续推进，直到结束‡如果Dαi(S)=False或仿真钟要求停止，则退出该进程。9然后对CEL的下一事件记录进行处理。275.1制造系统的调度策略¾进程交互法„进程交互法仿真钟推进z当CEL中的所有记录处理完毕后，9结束对CEL的扫描；9继续推进仿真钟，即把将来事件表中的最早发生的事件记录移到CEL中；9直到仿真结束。285.1制造系统的调度策略¾进程交互法„策略描述执行初始化操作，包括设置开始时间t=t0，结束时间t=t∞设置初始化事件，并置于FEL中将FEL中有关事件记录置于CEL中成分状态初始化：设置系统仿真钟TIME=t0111((,),,(,),,,)mmmnSststssαααααα+=295.1制造系统的调度策略¾进程交互法„策略描述While(TIME=t∞)，则执行设置开始时间t=t0，结束时间t=t∞1.CEL扫描While(CEL中最后一个记录未处理完)则While(Dai(S)=true且当前成分未处理完)则执行该成分的活动确定该成分的下一事件endwhileendwhile2.推进仿真钟TIME=FEL中安排的最早时间If(TIME=t∞)则将FEL中TIME时刻发生的事件记录移到CEL中endifendwhile305.1制造系统的调度策略¾进程交互法„仿真钟推进示意SS11SS22SS33SS44DD22DD33DD44DD55bb00bb11bb22bb33bb44bb55bb66bb77bb88bb99tt00tt11tt22cc11tt33cc22tt44cc33tt55150150AA11AA22AA33AA44AA55315.1制造系统的调度策略¾进程交互法„进程交互法既可预定事件，又可对条件求值，因而它兼有事件调度法及活动扫描法两者的特点。