理论模型建模方法课件.ppt

1、第三章第三章 理论模型建模方法理论模型建模方法本章内容要求：本章内容要求：1 1、掌握实体流图法、活动周期法、掌握实体流图法、活动周期法、PetriPetri网法、网法、EulerEuler网法网法建模的基本原理。建模的基本原理。2 2、能够应用所学建模方法建立并分析实际系统模型、能够应用所学建模方法建立并分析实际系统模型重点：实体流图法、重点：实体流图法、PetriPetri网法网法 本章介绍几种典型的离散事件建模方法。本章介绍几种典型的离散事件建模方法。 实体流图法实体流图法与计算机程序流程图的方法类似，可以描述临时与计算机程序流程图的方法类似，可以描述临时实体产生、流动、消实体产生、流动

2、、消 亡及其被永久实体加工、处理的过程和亡及其被永久实体加工、处理的过程和逻辑关系。逻辑关系。 活动周期图法活动周期图法针对实体的行为模式进行建模，可以直观地表针对实体的行为模式进行建模，可以直观地表示出某类实体生命周期中的活动和状况、具有规范化的特点。示出某类实体生命周期中的活动和状况、具有规范化的特点。 PetriPetri网方法网方法适于建立加工系统等多种离散事件系统的模型，适于建立加工系统等多种离散事件系统的模型，并可对网系统的特性进行比较严密的数学分析，得到对并发、并可对网系统的特性进行比较严密的数学分析，得到对并发、冲突、死锁等现象的深刻认识，应用也比较广泛。冲突、死锁等现象的深刻

3、认识，应用也比较广泛。 EulerEuler网方法网方法以图论和网论为数学描述语言以图论和网论为数学描述语言, ,贯穿了面向对象贯穿了面向对象的建模思想，描述方法比较规范，可以建立连续的建模思想，描述方法比较规范，可以建立连续离散事件混离散事件混合系统模型，方法的通用性较强。合系统模型，方法的通用性较强。 3.1 基本概念和术语基本概念和术语(1)(1)实体实体(Entity)(Entity)实体是构成系统的可单独辨识和描述的功能单元。实体是构成系统的可单独辨识和描述的功能单元。例如工厂中的机器，商店中的服务员，生产线上的工件，交通道路上例如工厂中的机器，商店中的服务员，生产线上的工件，交通道

4、路上的车辆等的车辆等。属性和行为相同或相近的实体可以用一类来描述，这样做可属性和行为相同或相近的实体可以用一类来描述，这样做可以简化系统的组成和关系。例如，理发店服务系统可以看成以简化系统的组成和关系。例如，理发店服务系统可以看成是由是由“服务员服务员”和和“顾客顾客”两类实体组成的两类实体组成的. .而两类实体之而两类实体之间存在服务与被服务的关系。间存在服务与被服务的关系。 (2) (2)属性属性(Attribute)(Attribute) 属性是实体特征的描述一般是实体所拥有的全部特征的属性是实体特征的描述一般是实体所拥有的全部特征的一个子集，用特征参数或变量表示。选用哪些特征参数作一个

5、子集，用特征参数或变量表示。选用哪些特征参数作为实体的属性与建模目的有关为实体的属性与建模目的有关, ,可参照下述原则选取：可参照下述原则选取： 便于实体的分类：便于实体的分类： 例如将理发店顾客的性别例如将理发店顾客的性别(“(“男男”或或“女女”）作为属性考虑，可将）作为属性考虑，可将“顾客顾客”实体分为二类每类顾客占用不同的服务台。实体分为二类每类顾客占用不同的服务台。 便于实体行为的描述便于实体行为的描述 例如将飞机的飞行速度作为届性考虑便于对例如将飞机的飞行速度作为届性考虑便于对“飞机飞机”实体的行为实体的行为( (如两地间的飞行时间如两地间的飞行时间) )进行描述。进行描述。 便于

6、排队规则的确定便于排队规则的确定 例如生产线上待处理工件的优先级水平有时需考虑为便于例如生产线上待处理工件的优先级水平有时需考虑为便于“按优先级按优先级排队排队”规则的建立和实现。规则的建立和实现。 (3)(3)活动活动(Activity)(Activity) 实体在一段时间内持续进行的操作或过程。活动所占用的时间区段称实体在一段时间内持续进行的操作或过程。活动所占用的时间区段称为忙期为忙期(duration)(duration)，忙期可以是定时的或随机的。，忙期可以是定时的或随机的。 (4)(4)状态状态(State)(State) 对实体活动的特征状况或性态的划分，其表征量称为状态变量。在

7、理对实体活动的特征状况或性态的划分，其表征量称为状态变量。在理发店服务系统模型中，发店服务系统模型中，“顾客顾客”有有“等待服务等待服务”、“接受服务接受服务”等状态，等状态，“服务员服务员”有有“忙忙”和和“闲闲等状态。活动总是与一个或几个实体的状等状态。活动总是与一个或几个实体的状态相对应。状态可作为动态属性进行描述。态相对应。状态可作为动态属性进行描述。 (5)(5)事件事件(Event)(Event) 导致系统状态产生变化的瞬间操作或行为。事件发生的时刻称为事件导致系统状态产生变化的瞬间操作或行为。事件发生的时刻称为事件点。不关心事件所代表的操作和行为意义时，事件与事件点是同义语。若点

8、。不关心事件所代表的操作和行为意义时，事件与事件点是同义语。若事件的发生是有前提的则称为条件事件。事件的发生是有前提的则称为条件事件。 活动、状态和事件三者间的联系活动、状态和事件三者间的联系: :由子事件的发生会导致状态的变化，而由子事件的发生会导致状态的变化，而实体的活动可以与一定的状态相对应，因此可以用事件来标识活动的开始实体的活动可以与一定的状态相对应，因此可以用事件来标识活动的开始和结束。其间的关系如图和结束。其间的关系如图3.13.1所示，图中所示，图中S S表示状态，表示状态，A A表示活动，表示活动，E E表示事表示事件，件，P P表示进程。表示进程。 (6)(6)进程进程(P

9、rocess)(Process) 一组按发生时间排列的事件活动序列称为一个进程。一组按发生时间排列的事件活动序列称为一个进程。 (7)(7)队列队列(Queue)(Queue) 处于等待状态的实体序列。一般按新到的实体排在队后的次序组成队处于等待状态的实体序列。一般按新到的实体排在队后的次序组成队列。离散事件建模中，队列可作为一种状态或特殊实体对待。列。离散事件建模中，队列可作为一种状态或特殊实体对待。 图图3.1 活动、状态、事件及进程活动、状态、事件及进程32 实体流图法实体流图法 3 32 21 1 实体流图实体流图 在离散事件系统中，实体可以分为两大类：在离散事件系统中，实体可以分为两

10、大类：临时实体临时实体和和永永久实体久实体。 临时实体临时实体按一定规律由系统外部到达系统，在系统中接受按一定规律由系统外部到达系统，在系统中接受永久实体的作用，按照一定的流程通过系统，最后离开系永久实体的作用，按照一定的流程通过系统，最后离开系统。统。 例如进入商店购物的顾客、交通路口的车辆、生产线上的电视例如进入商店购物的顾客、交通路口的车辆、生产线上的电视机、进人防空火力网的战斗机，驶入地下停车场的汽车等机、进人防空火力网的战斗机，驶入地下停车场的汽车等。 与临时实体相反、那些永久驻留在系统中的实体称为永久与临时实体相反、那些永久驻留在系统中的实体称为永久实体。系统要对临时实体产生作用，

11、就必须有永久实体的实体。系统要对临时实体产生作用，就必须有永久实体的活动，临时实体和永久实体协同完成某项活动活动，临时实体和永久实体协同完成某项活动如理发店的如理发店的理发员，生产线上的加工、装配机械，交通路口的红绿灯等，都是永理发员，生产线上的加工、装配机械，交通路口的红绿灯等，都是永久实体的例子。久实体的例子。 实体流图法（实体流图法（entity flow chart ,EFC) 采用与计算机程序采用与计算机程序 流程图相类似的图示符号和原理，建立表示临时实体产流程图相类似的图示符号和原理，建立表示临时实体产生、在系统中流动、接受永久实体生、在系统中流动、接受永久实体“服务服务”以及消失

12、等以及消失等过程的流程图。借助实体流程图、可以表示事件、状态过程的流程图。借助实体流程图、可以表示事件、状态变化及实体间相互作用的逻辑关系。变化及实体间相互作用的逻辑关系。 建立实际系统的实体流图模型建立实际系统的实体流图模型一是要对实际系统的工一是要对实际系统的工作过程有深刻的理解和认识作过程有深刻的理解和认识，二是要将事件、状态变化、二是要将事件、状态变化、活动和队列等概念贯穿于建模过程中活动和队列等概念贯穿于建模过程中。 常用的图示符号只有常用的图示符号只有菱形框菱形框( (表示判断表示判断) )、矩形框矩形框( (表表示事件、状态、活动等中间过程示事件、状态、活动等中间过程) )、圆端

13、矩形框圆端矩形框( (表示开表示开始和结束始和结束) )及及箭头线箭头线( (表示逻辑关系表示逻辑关系) )等。等。 建模时可按照以下思路进行：建模时可按照以下思路进行： (1)(1)辨识组成系统的实体及属性。将队列作为一种特殊的实体来考虑。辨识组成系统的实体及属性。将队列作为一种特殊的实体来考虑。 (2)(2)分析各种实体的状态和活动，及其相互间影响，队列实体的状态是分析各种实体的状态和活动，及其相互间影响，队列实体的状态是 队列的长度。队列的长度。 (3)(3)考察有哪些事件导致了活动的开始或结束，或者可以作为活动开始或考察有哪些事件导致了活动的开始或结束，或者可以作为活动开始或结束的标志

14、，以确定引起实体状态变化的事件，并合并条件事件。结束的标志，以确定引起实体状态变化的事件，并合并条件事件。 (4)(4)分析各种事件发生时，实体状态的变化规律。分析各种事件发生时，实体状态的变化规律。 (5)(5)在一定的服务流程下，分析与队列实体有关的特殊操作在一定的服务流程下，分析与队列实体有关的特殊操作( (如换队等如换队等) )。 (6)(6)通过以上分析，以临时实体的流动为主线，用约定的图示符号画出镇通过以上分析，以临时实体的流动为主线，用约定的图示符号画出镇仿真系统的实体流程图。仿真系统的实体流程图。 (7)(7)给出模型参数的取值、参变量的计算方法及属性描述变量的取值方法。给出模

15、型参数的取值、参变量的计算方法及属性描述变量的取值方法。属性描述变量，属性描述变量，例如顾客到达时间、服务时间等，可以取一组固定值，可以例如顾客到达时间、服务时间等，可以取一组固定值，可以由某一计算公式取值还可以是一个随机变量。属性描述变量是随机变量时，由某一计算公式取值还可以是一个随机变量。属性描述变量是随机变量时，应给出其分布函数。应给出其分布函数。 (8)(8)给出队列的排队规则。有多个队列存在时，还应给出其服务规则包给出队列的排队规则。有多个队列存在时，还应给出其服务规则包括队列的优先序、换队规则等。括队列的优先序、换队规则等。(1)(1)辨识系统实体辨识系统实体（2 2）分析实体状态

16、变化情况）分析实体状态变化情况（3）分析引起状态变化的事件）分析引起状态变化的事件(4)分析队列实体的操作分析队列实体的操作 “顾客到达顾客到达”或或“顾客结束排队顾客结束排队”可以导致可以导致“服务服务”活动的开始，面活动的开始，面“顾客理完离去顾客理完离去”可以导致可以导致“服务服务”活动的结束，因此这三件事情均可作活动的结束，因此这三件事情均可作为事件看待。但是为事件看待。但是, ,由于由于”顾客结束排队顾客结束排队”是以理发员状态是是以理发员状态是“闲闲”为条为条件的，因此是条件事件；而队列状态为件的，因此是条件事件；而队列状态为“非零非零”时理发员状态为时理发员状态为“闲闲”是是由事

17、件由事件“顾客理完离去顾客理完离去”导致的导致的, ,因此将因此将“顾客结束排队顾客结束排队”事件并入事件并入“顾顾客理完离去客理完离去”事件，不予单独考虑。这是实体流图法建模的一般原则。事件，不予单独考虑。这是实体流图法建模的一般原则。“顾客到达顾客到达”将使理发员由将使理发员由“闲闲”变为变为“忙忙”，或使，或使“队列长度队列长度”加加1 1。“顾客理完离去顾客理完离去”将使理发员由将使理发员由“忙忙”变为变为“闲闲”。“顾客结束排队顾客结束排队”将将使使“队列长度队列长度”减减1 1，并使理发员由，并使理发员由“闲闲”变为变为“忙忙”。由于本问题中只有一个队列，面且顾客不会因排队人数太多

18、而离去、由于本问题中只有一个队列，面且顾客不会因排队人数太多而离去、因此队列规则很简单，没有特殊的队列操作。因此队列规则很简单，没有特殊的队列操作。（5）画出系统实体流程图）画出系统实体流程图 通过以上分析，以顾客活动为主线画出理发店服务系统的实体流图。通过以上分析，以顾客活动为主线画出理发店服务系统的实体流图。NoYES顾客排队等待顾客排队等待顾客进入队列顾客进入队列有其他顾客离开有其他顾客离开顾 客 排 在顾 客 排 在队首队首No顾客到达顾客到达进入理发店进入理发店理发员闲理发员闲置理发员为忙置理发员为忙顾客开始理发顾客开始理发接受理发服务接受理发服务顾客理完离去顾客理完离去置理发员为闲

19、置理发员为闲YES(6)(6)确定模型参变量确定模型参变量 需给出的模型属性变量有：顾客的到达时间（随机变量）、需给出的模型属性变量有：顾客的到达时间（随机变量）、理发员为一个顾客理发所需的服务时间（随机变量）等，它理发员为一个顾客理发所需的服务时间（随机变量）等，它们的值可分别从不同的分布函数中抽取。们的值可分别从不同的分布函数中抽取。 （7）给出排队规则）给出排队规则队列的排队规则是先到先服务（队列的排队规则是先到先服务（FIFOFIFO），即每到一名顾），即每到一名顾客就排在队尾，服务员先为排在队首的顾客服务客就排在队尾，服务员先为排在队首的顾客服务. .例例3.2 分时计算机系统分时计

20、算机系统 分时计算机系统由一个分时计算机系统由一个CPUCPU和多台计算机输入终端组成和多台计算机输入终端组成( (图图3.33.3）。）。用户从终端输入作业，请求用户从终端输入作业，请求CPUCPU为其服务。所有终端输入的作业由一个为其服务。所有终端输入的作业由一个CPUCPU执行，因而形成单一队列。执行，因而形成单一队列。CPUCPU按按FIFO(FIFO(先进先出先进先出) )的服务规则分时的服务规则分时轮流为各终端的作业服务。如果一个作业的轮流为各终端的作业服务。如果一个作业的CPUCPU执行时间大于一个时间执行时间大于一个时间片片t te e，则该任务执行一段时间，则该任务执行一段时

21、间t te e后退出后退出CPUCPU，并重新参加排队。只有当，并重新参加排队。只有当某一终端发出的服务请求执行完毕退出某一终端发出的服务请求执行完毕退出CPUCPU后，才允许该终端重新输入后，才允许该终端重新输入一个新的作业，建模的目的是研究用户的等待时间。一个新的作业，建模的目的是研究用户的等待时间。实实 体体活活 动动状状 态态用用 户户输入作业输入作业等待输入等待输入输入输入等候等候CPU执行作业执行作业等待作业等待作业忙忙闲闲作作 业业输入作业输入作业进入队列进入队列执行作业执行作业接受输入接受输入等待执行等待执行接受处理接受处理队队 列列队列长度队列长度分时计算机系统实体列表分时计

22、算机系统实体列表本系统的实体为计算机用户、计算机的本系统的实体为计算机用户、计算机的CPUCPU及用户请求执行的作业，及用户请求执行的作业，其中前二类实体是水久实体。其中前二类实体是水久实体。 作业是临时实体。作业是临时实体。实实 体体状态变化状态变化对应的活动对应的活动活动开始事件活动开始事件活动结束事件活动结束事件 变化前变化前 变化后变化后用户用户输入输入等候等候等待输入等待输入输入完毕输入完毕作业执行完毕作业执行完毕等候等候输入输入输入作业输入作业前一作业执行完毕前一作业执行完毕输入完毕输入完毕CPUCPU闲闲忙忙执行作业执行作业接到作业请求接到作业请求执行完毕或执行了一执行完毕或执行

23、了一个时间片个时间片忙忙闲闲等待作业等待作业执行完毕或执行了执行完毕或执行了一个时间片一个时间片接到作业请求接到作业请求作业作业接受输入接受输入等待执行等待执行进入队列进入队列输入完毕输入完毕前一作业执行完毕前一作业执行完毕等待执行等待执行接受处理接受处理执行作业执行作业前一作业执行完毕前一作业执行完毕作业执行完毕作业执行完毕接受处理接受处理接受输入接受输入输入作业输入作业作业执行完毕作业执行完毕输入完毕输入完毕长度长度1+11+1作业进入队列作业进入队列长度长度-1-1队首作业开始执行队首作业开始执行分时计算机系统活动与事件关系分时计算机系统活动与事件关系假定作业假定作业“输入完毕输入完毕”

24、到到CPU“CPU“接到执行请求接到执行请求”之间无时间延迟。则可之间无时间延迟。则可将二者看成同一事件。根据与例将二者看成同一事件。根据与例3 31 1同样的理由，同样的理由，“开始输入开始输入”和和“作作业结柬排队业结柬排队”均为条件事件，且均可并入均为条件事件，且均可并入“执行完毕执行完毕”事件处理。另外，事件处理。另外，“作业执行了一个时间片作业执行了一个时间片”与与“执行完毕执行完毕”标志着同样的事件处理标志着同样的事件处理只只是前者发生时需将作业送去重新排队，因此可看作同一类事件。这样模是前者发生时需将作业送去重新排队，因此可看作同一类事件。这样模型中只需考虑型中只需考虑“输入完毕

25、输入完毕”和和“执行完毕或执行了一个时间片执行完毕或执行了一个时间片”两种类两种类型的事件即可。要注意作业的输入型的事件即可。要注意作业的输入( (到达到达) )是有条件的且需耗费一定的时是有条件的且需耗费一定的时间；而且，执行作业的结束间；而且，执行作业的结束( (离去离去) )可能是暂时的，也可能是永久的，需可能是暂时的，也可能是永久的，需要加以判断。要加以判断。模型参数包括：模型参数包括：终端数量，时间片长度、辅助操作时间终端数量，时间片长度、辅助操作时间( (若一个作业在若一个作业在一个时间片内执行不完，一个时间片内执行不完，CPUCPU为完成该作业重新入队并从队列中取出下为完成该作业

26、重新入队并从队列中取出下一作业所需要的时间一作业所需要的时间) )。 模型属性变量有：模型属性变量有：作业输入时间作业输入时间( (随机变量随机变量) )、作业所需执行的时间、作业所需执行的时间( (随随机变量）等机变量）等 排队规则同例排队规则同例3 31 1。开始开始前一作业执行完毕前一作业执行完毕开始输入开始输入输入完毕输入完毕CPU闲闲置置CPU为忙为忙开始执行作业开始执行作业作业执行完作业执行完置置CPU为闲为闲用户等待用户等待作业等待作业等待NOYESNONOYESYES执行完一个时间片执行完一个时间片其他作业执行完其他作业执行完一个时间片一个时间片作业排在队首作业排在队首例例3.

27、3 3.3 剧院雇佣一名售票员同时负责剧票的窗口销售和对电话问讯者剧院雇佣一名售票员同时负责剧票的窗口销售和对电话问讯者的咨询服务。购票者按先到先服务的原则在窗口排队买票，问讯者打来的咨询服务。购票者按先到先服务的原则在窗口排队买票，问讯者打来的电话由电话系统存储后按先来先服务的原则一一予以答复，电话服务的电话由电话系统存储后按先来先服务的原则一一予以答复，电话服务比窗口服务有更高的优先级。售票员正在售票时若有电话打入，则售票比窗口服务有更高的优先级。售票员正在售票时若有电话打入，则售票员必须完成本次售票活动后再接听电话。系统建模的目的是研究售票员员必须完成本次售票活动后再接听电话。系统建模的

28、目的是研究售票员的忙闲率。的忙闲率。 本系统有本系统有个永久实体，即售票员、售祟员有个永久实体，即售票员、售祟员有“窗口售票窗口售票”和和“电电话服务话服务”两种活动，状态包括两种活动，状态包括空闲空闲”、“回电话回电话”和和“售票售票”。电话。电话问讯者和购票者为两类临时实体，其行为模式均与例问讯者和购票者为两类临时实体，其行为模式均与例3 31 1中的顾客实体中的顾客实体类似。本例与前二个例子的主要区别是有两条服务途径，因此可同时存类似。本例与前二个例子的主要区别是有两条服务途径，因此可同时存在二个队列，但顾客不可能换队。实体流图模型如图在二个队列，但顾客不可能换队。实体流图模型如图3.5

29、3.5所示。所示。电话拨入电话拨入购票者到达购票者到达售票员闲售票员闲售票员闲售票员闲有电话同时接入有电话同时接入购票者进入队列购票者进入队列售票员完成一个服务售票员完成一个服务置售票员为忙置售票员为忙电话拨入电话拨入排在队首排在队首售票员完成一个服务售票员完成一个服务电话进入队列电话进入队列电话队列为空电话队列为空排在队首排在队首开始电话服务开始电话服务开始售票服务开始售票服务电话服务完毕电话服务完毕售票服务完毕售票服务完毕置售票员为闲置售票员为闲YESNoYESYESYESYESYESYESNoNoNoNoNoNo图图3.5 售票窗口服务系统实体流图售票窗口服务系统实体流图 模型属性变量有

30、模型属性变量有“购票者到达时间购票者到达时间”、“电话问讯者到达时间电话问讯者到达时间”、“售票服务时间售票服务时间”和和“电话服务时间电话服务时间”，均为随机变量。排队规则为，均为随机变量。排队规则为FIFOFIFO，服务规则是，服务规则是“窗口购票者和电话问讯者分别排队，优先进行电窗口购票者和电话问讯者分别排队，优先进行电话服务话服务”。 注意，图注意，图3.53.5中有二处是与服务规则有关的判断相特殊操作。当中有二处是与服务规则有关的判断相特殊操作。当“电电话问讯者话问讯者”和和“窗口购票音窗口购票音”同时到达而售票员处于同时到达而售票员处于“闲闲”状态时，状态时，前者接受服务，后者加入

31、购票者队列；当服务完毕而购票队列和电话前者接受服务，后者加入购票者队列；当服务完毕而购票队列和电话队列均不为空时，先进行电话服务。队列均不为空时，先进行电话服务。3.2.2 模型的人工运行模型的人工运行 建立实体流图模型后，选取有代表性的例子将流图全部走一遍，即建立实体流图模型后，选取有代表性的例子将流图全部走一遍，即所谓人工运行。人工运行模型要求遍历流图的各个分支和实体的各种所谓人工运行。人工运行模型要求遍历流图的各个分支和实体的各种可能状态，在时间逐步变化的动态条件下，分析事件的发生及状态的可能状态，在时间逐步变化的动态条件下，分析事件的发生及状态的变化过程、以检查模型酌组成和逻辑关系是否

32、正确。变化过程、以检查模型酌组成和逻辑关系是否正确。 例例3.13.1中假定：中假定： (1)(1)系统的初始状态系统的初始状态 永久实体永久实体“理发员理发员”的状态及特殊实体的状态及特殊实体“队列队列”的状态。所谓初始时的状态。所谓初始时刻是指仿真开始的时刻，可以对应为实际系统刻是指仿真开始的时刻，可以对应为实际系统( (理发店理发店) )开门营业的时开门营业的时间。此时，理发员为间。此时，理发员为“闲闲”，队列长度是，队列长度是o o。 (2)(2)模型参数及变量的取值模型参数及变量的取值 本模型的变量包括第本模型的变量包括第i i个顾客与第个顾客与第i-1i-1个顾客到达的时间间隔个顾

33、客到达的时间间隔AiAi以及以及理发员为第理发员为第i i个顾客的理发时间个顾客的理发时间SiSi。一般说来，。一般说来，Ai , SiAi , Si均为随机变量，均为随机变量，应根据其分布函数来产生。这里，为了便于解释取其样本值为应根据其分布函数来产生。这里，为了便于解释取其样本值为 A1=15 A2=32 A3=24 A4=40 A5=22,A1=15 A2=32 A3=24 A4=40 A5=22, 模型需按一定的规则运行。本模型的人工运行规则如下：模型需按一定的规则运行。本模型的人工运行规则如下： 规则规则1 1确定当前时间确定当前时间 模型人工运行开始时，取当前时间，模型人工运行开始

34、时，取当前时间，TIME=tTIME=t0 0(t(t0 0为仿真初始时刻为仿真初始时刻) )。人工运。人工运行开始后，当前时间逐步向前推移且递取下一最早发生事件的发生时刻。行开始后，当前时间逐步向前推移且递取下一最早发生事件的发生时刻。如果当前时间有顾客到达事件发生，转规则如果当前时间有顾客到达事件发生，转规则2 2；若有顾客离去事件发生，；若有顾客离去事件发生，则转规则则转规则3 3。 规则规则2 2顾客到达事件处理顾客到达事件处理 假定在时刻假定在时刻TIMETIME有顾客有顾客i i到达。根据图到达。根据图3.23.2知，如果此时理发员忙。则入队知，如果此时理发员忙。则入队列等待队列长

35、度加上列等待队列长度加上1,1,否则置理发员为否则置理发员为“忙忙”状态，顾客开始理发，且状态，顾客开始理发，且在在didiTIME+SiTIME+Si时刻理毕离去。时刻理毕离去。 规则规则3-3-顾客离去事件处理顾客离去事件处理 假定在时刻了假定在时刻了TIMETIME有顾客有顾客i i离去。根据图离去。根据图3 32 2知，如果此时队列长度为知，如果此时队列长度为0 0，则置理发员为则置理发员为”闲闲”状态状态; ;否则否则, ,队列中排在队首的一名顾客开始理发，队队列中排在队首的一名顾客开始理发，队列长度减去列长度减去1.1.并且该顾客在并且该顾客在didiTIME+SiTIME+Si时

36、刻理毕离去。时刻理毕离去。3.3 活动周期图法活动周期图法在上节关于实体流图法的介绍中，我们可以看到这样一种现象：实体的在上节关于实体流图法的介绍中，我们可以看到这样一种现象：实体的行为模式在有限的几种情况之间周而复始地变化表现出一定的生命周行为模式在有限的几种情况之间周而复始地变化表现出一定的生命周期形式。例如，例期形式。例如，例3 31 1中的理发员实体的状态在中的理发员实体的状态在“闲闲”和和“忙忙”之间不之间不断变化而断变化而“忙忙”状态意味着理发员与顾客协同完成状态意味着理发员与顾客协同完成“理发理发”活动。顾活动。顾客实体是临时实体，虽然单个实体仅在系统中停留一段时间，但是顾客客实

37、体是临时实体，虽然单个实体仅在系统中停留一段时间，但是顾客实体的群体行为则是在实体的群体行为则是在“到达到达”、“等待等待”、“理发理发”和和“离去离去”之间之间周而复始地变化，出现局而复姑的行为模式。活动周期图周而复始地变化，出现局而复姑的行为模式。活动周期图(ActivltycycLe(ActivltycycLe Di“8ram Di“8ram，AcDAcD) )正是基于这样一种思想逐步形成的一种正是基于这样一种思想逐步形成的一种离散事件建模方法。离散事件建模方法。 活动周期图以直观的方式显示了实体的状态变化历程和各实体之间活动周期图以直观的方式显示了实体的状态变化历程和各实体之间的交互作

38、用关系，便于理解和分析。活动周期图可以充分反映各类实体的交互作用关系，便于理解和分析。活动周期图可以充分反映各类实体的行为模式，并将系统的状态变化以的行为模式，并将系统的状态变化以“个体个体”状态变化的集合方式表示状态变化的集合方式表示出来，因此可以更好地表达众多实体的并发活动和实体之间的协同。但出来，因此可以更好地表达众多实体的并发活动和实体之间的协同。但是，它只描述了系统的稳态，而没有表示系统的瞬态，即活动的开始和是，它只描述了系统的稳态，而没有表示系统的瞬态，即活动的开始和结束事件。结束事件。3.3.1 活动周期图活动周期图实体状态：静寂实体状态：静寂(Dead) 和激活（和激活（Act

39、ive) 静寂状态（无活动）静寂状态（无活动） 激活状态（活动）激活状态（活动）ACD基本图符基本图符不同实体采用不同线型不同实体采用不同线型顾客顾客理发员理发员活动周期图的建模过程：活动周期图的建模过程：(1) (1) 辨识系统的实体组成及其属性辨识系统的实体组成及其属性(2)(2)分别画出各实体活动周期图分别画出各实体活动周期图 遵循原则：遵循原则： a a 交替原则交替原则 静寂状态与激活状态必须交替出现。直联活动与前置活动静寂状态与激活状态必须交替出现。直联活动与前置活动之间存在虚拟的队列。之间存在虚拟的队列。 b b 闭合原则闭合原则 临时实体的活动周期图表示一个或单位实体从产生到消

40、失临时实体的活动周期图表示一个或单位实体从产生到消失的循环过程。的循环过程。(3)(3)将各实体的活动联接成系统活动周期图（以协同活动为纽带）将各实体的活动联接成系统活动周期图（以协同活动为纽带）(4)(4)增添必要的虚拟实体增添必要的虚拟实体(5)(5)标明活动发生的约束条件和占用的资源数量标明活动发生的约束条件和占用的资源数量 包括：包括：a a 活动活动是否可以发生的判断条件（表达式）活动活动是否可以发生的判断条件（表达式） b b 永久实体在参加一次协同活动所占用的资源数量永久实体在参加一次协同活动所占用的资源数量 （/ /符号）符号）(6) (6) 给出模型参数的取值，参变量的计算方

41、法及属性描述变给出模型参数的取值，参变量的计算方法及属性描述变量的取值方法并给出排队规则和服务规则。量的取值方法并给出排队规则和服务规则。例例 3.4 机床加工系统机床加工系统 2) 机床机床三种激活状态：安装刀具（三种激活状态：安装刀具（RETOOL)、安装工件、安装工件（RESET)、加工（、加工（RUNNING)3)将工人和机床活动周期图合并将工人和机床活动周期图合并确定模型的参变量和属性描述确定模型的参变量和属性描述模型参数：模型参数：1 1、机床数量、机床数量2 2、累计加工工件数、累计加工工件数3 3、累计加工时间、累计加工时间属性变量：属性变量：1 1、加工工件时间、加工工件时间

42、2 2、安装刀具时间、安装刀具时间3 3、安装工件时间、安装工件时间4 4、饮茶时间、饮茶时间5 5、轮休时间、轮休时间例例3.5 3.5 售票窗口服务系统售票窗口服务系统三类实体：售票员、窗口购票者、电话问询者三类实体：售票员、窗口购票者、电话问询者1、售票员、售票员 两种激活：窗口售票、电话服务两种激活：窗口售票、电话服务2、窗口售票者、窗口售票者激活状态激活状态窗口服务，到达窗口服务，到达静寂状态静寂状态排队等待、外部排队等待、外部3、电话问询者、电话问询者激活状态激活状态电话服务、打电话电话服务、打电话静寂状态静寂状态等接电话、局外等接电话、局外例例3.6 货物转运系统货物转运系统 实

43、体：实体：大货车、小货车、卸货仓位、工人、进站通大货车、小货车、卸货仓位、工人、进站通道和出站通道道和出站通道2）小货车）小货车3）装卸仓位）装卸仓位4 4）进出通道）进出通道5 5）装卸工人）装卸工人货物转运系统活动周期图货物转运系统活动周期图以机床加工系统为例以机床加工系统为例实体流图法和活动周期图之间的区别及各自的特点实体流图法和活动周期图之间的区别及各自的特点 (1)实体流程图实体流程图(以下简称为以下简称为EFC)是以临时实体在系统中的流动过程为主线建立的模型、永是以临时实体在系统中的流动过程为主线建立的模型、永久实体浓缩于表示状态和事件的图示符号之中，队列被作为一种特殊的实体来对待

44、。对久实体浓缩于表示状态和事件的图示符号之中，队列被作为一种特殊的实体来对待。对这三种实体的描述交织在一起、使得各类临时和永久实体没有单独的图示。活动周期图这三种实体的描述交织在一起、使得各类临时和永久实体没有单独的图示。活动周期图ACD则基于各类临时和水久实体的行为模式，它们均有其单独的图示表达，队列很自然则基于各类临时和水久实体的行为模式，它们均有其单独的图示表达，队列很自然地成为实体生命周期中的一种状态。地成为实体生命周期中的一种状态。 (2)ACD中，各类实体的图示是中，各类实体的图示是“环形环形”的循环图，整个系统的的循环图，整个系统的ACD由多个环套在一起组由多个环套在一起组成；而

45、成；而EFC则是带有小循环的则是带有小循环的“树形树形”流程团。流程团。 (3)事件是事件是EFC的重要组成部分，在的重要组成部分，在EFC中有显式的表达，而在中有显式的表达，而在ACD中，事件蕴含在活动中，事件蕴含在活动之中，没有显式表达。之中，没有显式表达。 (4)状态判断框在状态判断框在EFC中的作用十分重要。中的作用十分重要。ACD将将EFC中需作判断的状态用中需作判断的状态用“空闲空闲”、“等待等待”等静寂状态表示，而对实体是否处于该状态的判断则勿需标在图中因为它已等静寂状态表示，而对实体是否处于该状态的判断则勿需标在图中因为它已升华为模型运行时的一般规则。实际上根据升华为模型运行时

46、的一般规则。实际上根据EFC人工运行规则，每一个静寂状态都有人工运行规则，每一个静寂状态都有“条件条件”的底蕴的底蕴 (5)从人工运行规则来看，从人工运行规则来看，ACD存在普适性很强的运行规则，它与每个具体的存在普适性很强的运行规则，它与每个具体的ACD无关；无关；而而EFC的运行规则中只有第的运行规则中只有第1条是通用的条是通用的(体现了事件调度法体现了事件调度法)，其它各条均从具体的，其它各条均从具体的EFC中抽取，普适性很差。中抽取，普适性很差。 (6)由由(1)和和(5)知，知，ACD更易于用而向对象的技术实现，软件上也更易于实现仿真程序的自更易于用而向对象的技术实现，软件上也更易于

47、实现仿真程序的自动生成。另外由动生成。另外由(1)知，知，ACD表示冲突和并发现象更方便、直观。表示冲突和并发现象更方便、直观。 (7)正是由于正是由于EFC没有没有ACD那样规范，因此如果不考虑模型的远行间题，那样规范，因此如果不考虑模型的远行间题，EFC比比ACD的适的适用范围更广。另外，用范围更广。另外，EFC中可以对队列的排队规则和服务规则进行比较详细的描述。中可以对队列的排队规则和服务规则进行比较详细的描述。3.4 Petri网方法网方法 对活动周期图建模方法作以下改变：对活动周期图建模方法作以下改变：(1)(1)取消临时实体取消临时实体ACDACD中的中的“源源”状态状态”，即不再

48、考虑临时实，即不再考虑临时实体的生命周期循环；体的生命周期循环；(2)(2)将活动看作是将活动看作是“开始事件开始事件+ +状态状态+ +结束事件结束事件”，这样一来，这样一来，建模的元素就变成建模的元素就变成“事件事件”和和“状态状态”，后者包括，后者包括ACDACD中的激活状态和静寂状态中的激活状态和静寂状态. .(3)(3)不强调实体模型之间的独立性。不强调实体模型之间的独立性。 3.4.1 Petri网的基本概念网的基本概念 1 1基本术语基本术语 (1)(1)资源资源 与系统状态发生变化有关的因京，称为资源。如原料、部件、产品与系统状态发生变化有关的因京，称为资源。如原料、部件、产品

49、( (成品或半成品成品或半成品) )、人员、工具、设备、数据及信息等。、人员、工具、设备、数据及信息等。 (2)(2)状态元素状态元素 资源按其在系统巾的作用分类，每一类存放一处，则该处抽象为一个资源按其在系统巾的作用分类，每一类存放一处，则该处抽象为一个相应的状态元素。相应的状态元素。 (3)(3)库所库所 状态元索又称库所。它不仅表示一个场所，而且表示在该场所存放了状态元索又称库所。它不仅表示一个场所，而且表示在该场所存放了一定的资源一定的资源 (4)(4)变迁变迁 资源的消耗、使用及产生对应于状态元素的变化，网论中将此变化叫资源的消耗、使用及产生对应于状态元素的变化，网论中将此变化叫做变

50、迁。做变迁。 (5)(5)条件条件 如果一个库所只有两种状态，有标记和无标记，则称该库所为条件。如果一个库所只有两种状态，有标记和无标记，则称该库所为条件。 (6)(6)事件事件 涉及条件的变迁称为事件。涉及条件的变迁称为事件。 (7)(7)容量容量 库所对储存资源的数量限制称为库所的容量。库所对储存资源的数量限制称为库所的容量。2 2PetriPetri网的数学结构网的数学结构定义定义3.4.1 3.4.1 一个一个PetriPetri网网(PN)(PN)是一个三元组是一个三元组N(SN(S，T T，F)F)，式中，式中(1)S(1)S和和T T分别是库所和变迁的有限集，满足分别是库所和变迁