实体流图法-.ppt

计算机科学与技术学院计算机科学与技术学院COMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGY吉林大学吉林大学 5.4 实体流图法实体流图法 对系统进行仿真研究，首先要建立系统的模型。对系统进行仿真研究，首先要建立系统的模型。离散事件系统的时间是连续变化的，但系统的状离散事件系统的时间是连续变化的，但系统的状态仅发生在一些离散的时刻，由随机事件的驱动态仅发生在一些离散的时刻，由随机事件的驱动而发生，因此，离散事件系统的模型很难用数学而发生，因此，离散事件系统的模型很难用数学方程来描述。所以，逐渐形成一些与连续系统不方程来描述。所以，逐渐形成一些与连续系统不同的建模方法。实体流图法就是其中之一。同的建模方法。实体流图法就是其中之一。实体流程图方法（简称实体流图法）与程序流程实体流程图方法（简称实体流图法）与程序流程图类似图类似，可以描述临时实体产生、流动、消亡及，可以描述临时实体产生、流动、消亡及其被永久实体加工、处理的过程和逻辑关系，应其被永久实体加工、处理的过程和逻辑关系，应用比较广泛。用比较广泛。2024/5/22 周三1计算机科学与技术学院计算机科学与技术学院COMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGY吉林大学吉林大学 临时实体和永久实体临时实体和永久实体在离散事件系统中，实体分为两大类：在离散事件系统中，实体分为两大类：临时实体、临时实体、永久实体。永久实体。临时实体：临时实体：按一定规律由系统外部到达系统，在按一定规律由系统外部到达系统，在系统中受永久实体的作用，按照一定的流程通过系统中受永久实体的作用，按照一定的流程通过系统，最后离开系统。因此，临时实体只在系统系统，最后离开系统。因此，临时实体只在系统中存在一段时间便自行消失。中存在一段时间便自行消失。进入商店购物的顾客是临时实体，它们按一定的进入商店购物的顾客是临时实体，它们按一定的统计分布规律到达商店，经过服务员的服务后离统计分布规律到达商店，经过服务员的服务后离开商店。开商店。永久实体：永久实体：相应地，永久驻留在系统中的实体称相应地，永久驻留在系统中的实体称为永久实体，它们是系统产生功能的必要条件。为永久实体，它们是系统产生功能的必要条件。理发店中的理发员，交通路口的红绿灯等是永久理发店中的理发员，交通路口的红绿灯等是永久实体。实体。2024/5/22 周三2计算机科学与技术学院计算机科学与技术学院COMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGY吉林大学吉林大学 实体流程图方法实体流程图方法实体流程图方法：实体流程图方法：采用与计算机程序流程图类似的图示符采用与计算机程序流程图类似的图示符号和原理，建立表示临时实体产生、在系统中流动、接受号和原理，建立表示临时实体产生、在系统中流动、接受永久实体服务以及消失等过程的流程图。永久实体服务以及消失等过程的流程图。建模思路：建模思路：（1）辨识组成系统的实体和属性。将队列作为一种特殊的实）辨识组成系统的实体和属性。将队列作为一种特殊的实体考虑。体考虑。（2）分析各种实体的状态和活动，及其相互间的影响。队列）分析各种实体的状态和活动，及其相互间的影响。队列实体的状态是队列的长度。实体的状态是队列的长度。（3）确定引起实体状态变化的事件。）确定引起实体状态变化的事件。（4）分析各种事件发生时，实体状态的变化规律。）分析各种事件发生时，实体状态的变化规律。（5）在一定的服务流程下，分析与队列实体有关的特殊操作）在一定的服务流程下，分析与队列实体有关的特殊操作（如换队等）。（如换队等）。（6）通过以上分析，以临时实体为主线，画实体流程图。）通过以上分析，以临时实体为主线，画实体流程图。（7）给出模型参数的取值、参变量的计算方法及属性描述变）给出模型参数的取值、参变量的计算方法及属性描述变量的取值方法。属性描述变量，例如顾客到达时间、服务量的取值方法。属性描述变量，例如顾客到达时间、服务时间等，可以取一组固定值，可以由某一计算公式取值，时间等，可以取一组固定值，可以由某一计算公式取值，还可以是一个随机变量（此时应给出分布函数）。还可以是一个随机变量（此时应给出分布函数）。（8）给出队列的排队规则。对多个队列应有服务规则。）给出队列的排队规则。对多个队列应有服务规则。2024/5/22 周三3计算机科学与技术学院计算机科学与技术学院COMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGY吉林大学吉林大学 例例1：理发店服务系统：理发店服务系统一个理发店只有一个理发员。顾客来到理发店后，一个理发店只有一个理发员。顾客来到理发店后，如果有人正在理发就坐在一旁等候。理发员按先来如果有人正在理发就坐在一旁等候。理发员按先来先理发的原则为每一个顾客服务，而且只要有顾客先理发的原则为每一个顾客服务，而且只要有顾客就不停歇。就不停歇。建模目的建模目的是考察理发员的忙闲情况（假定顾客到达是考察理发员的忙闲情况（假定顾客到达间隔和理发花费的时间服从一定的概率分布）。间隔和理发花费的时间服从一定的概率分布）。本例有本例有3类实体：类实体：理发员、顾客、顾客队列。理发员、顾客、顾客队列。理发员：理发员：永久实体，其活动为永久实体，其活动为“理发理发”，有，有“忙忙”“闲闲”2种状态。种状态。顾客：顾客：临时实体，与理发员共同完成活动，有临时实体，与理发员共同完成活动，有“等等待服务待服务”、“接受服务接受服务”等状态。等状态。顾客队列：顾客队列：特殊实体，状态为队列的长度。特殊实体，状态为队列的长度。2024/5/22 周三4计算机科学与技术学院计算机科学与技术学院COMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGY吉林大学吉林大学 例例1中各个实体之间的关系中各个实体之间的关系（1）某一顾客到达时，如果理发员处于某一顾客到达时，如果理发员处于“忙忙”的的状态，则该顾客进入状态，则该顾客进入“等待服务等待服务”的状态，否则，的状态，否则，进入进入“接受服务接受服务”状态。状态。（2）理发员完成对某一顾客的服务时，如果队列理发员完成对某一顾客的服务时，如果队列处于处于“非零非零”状态，则立即开始服务活动，否则状态，则立即开始服务活动，否则进入进入“闲闲”状态。状态。（3）“顾客到达顾客到达”可以导致可以导致“服务服务”活动的开始，活动的开始，“顾客理完离去顾客理完离去”导致导致“服务服务”活动的结束，因活动的结束，因此，这二个事情可以作为事件看待。此，这二个事情可以作为事件看待。（4）“顾客到达顾客到达”将使理发员由将使理发员由“闲闲”变为变为“忙忙”，或使，或使“队列长度队列长度”加加1。（5）“顾客理完离去顾客理完离去”将使理发员由将使理发员由“忙忙”变为变为“闲闲”，或使，或使“队列长度队列长度”减减1。2024/5/22 周三5计算机科学与技术学院计算机科学与技术学院COMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGY吉林大学吉林大学 理发店服务系统实体流程图理发店服务系统实体流程图 需要给出模型属性变量：需要给出模型属性变量：顾客的到达时间（随机顾客的到达时间（随机变量）、理发员为一个顾客理发所需的服务时间变量）、理发员为一个顾客理发所需的服务时间（随机变量）等，它们的值可以分别从不同的分（随机变量）等，它们的值可以分别从不同的分布函数中抽取。布函数中抽取。队列的排队规则：队列的排队规则：先到先服务（先到先服务（FIFO）。）。注意：注意：实体流图是实体流动和逻辑关系图，不是实体流图是实体流动和逻辑关系图，不是计算机程序框图。计算机程序框图。顾客到达顾客到达排队等待排队等待置理发员为忙置理发员为忙顾客开始理发顾客开始理发顾客理完离去顾客理完离去置理发员为闲置理发员为闲理发员闲理发员闲YN2024/5/22 周三6计算机科学与技术学院计算机科学与技术学院COMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGY吉林大学吉林大学 计算机科学与技术学院计算机科学与技术学院COMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGY吉林大学吉林大学 5.5 模型的人工运行模型的人工运行 人工运行：人工运行：建立实体流图模型后，应选取有代表建立实体流图模型后，应选取有代表性的例子将流图全部走一遍，即所谓的人工运行。性的例子将流图全部走一遍，即所谓的人工运行。人工运行模型要求遍历流图的各个分支和实体的人工运行模型要求遍历流图的各个分支和实体的各种可能状态，在时间逐步变化的动态条件下，各种可能状态，在时间逐步变化的动态条件下，分析事件的发生及状态的变化过程，以检查模型分析事件的发生及状态的变化过程，以检查模型的组成和逻辑关系是否正确。的组成和逻辑关系是否正确。2024/5/22 周三8计算机科学与技术学院计算机科学与技术学院COMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGY吉林大学吉林大学 模型的人工运行举例模型的人工运行举例例：例：“理发店服务系统理发店服务系统”（1）系统的初始状态（仿真开始时刻）：）系统的初始状态（仿真开始时刻）：对应开门营业时间，此时，理发员为对应开门营业时间，此时，理发员为“闲闲”，队列，队列长度为长度为0。（2）模型参数及变量的取值：）模型参数及变量的取值：设第设第i个顾客与第个顾客与第i-1个顾客到达的时间间隔为个顾客到达的时间间隔为Ai，设理发员为第设理发员为第i个顾客的理发时间为个顾客的理发时间为Si，一般来说，一般来说，Ai、Si为随机变量，应根据分布函为随机变量，应根据分布函数来产生。这里，为了便于解释，取其样本值为：数来产生。这里，为了便于解释，取其样本值为：A115，A232，A324，A440，A522，S1=43，S2=36，S3=34，S4=28，2024/5/22 周三9计算机科学与技术学院计算机科学与技术学院COMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGY吉林大学吉林大学 模型的人工规则模型的人工规则模型按一定的规则运行。本模型的人工规则如下：模型按一定的规则运行。本模型的人工规则如下：规则规则1：确定当前时间确定当前时间模型人工运行开始，取当前时间模型人工运行开始，取当前时间TIMEt0（t0为仿为仿真初始时刻），人工运行开始后，当前时间逐步向真初始时刻），人工运行开始后，当前时间逐步向前推移，且递取下一最早发生事件的发生时刻。如前推移，且递取下一最早发生事件的发生时刻。如果当前时间有顾客到达事件发生，转规则果当前时间有顾客到达事件发生，转规则2。若有。若有顾客离开事件发生，则转规则顾客离开事件发生，则转规则3。规则规则2：顾客到达事件处理顾客到达事件处理假定在时刻假定在时刻TIME有顾客有顾客i到达，如果此时理发员忙，到达，如果此时理发员忙，则进入队列等待，队列长度加则进入队列等待，队列长度加1；否则置理发员为；否则置理发员为忙状态，顾客开始理发，且在忙状态，顾客开始理发，且在di=TIME+Si时刻理时刻理发完毕离去。发完毕离去。规则规则3：顾客离去事件处理顾客离去事件处理假定在时刻假定在时刻TIME有顾客有顾客i离去离去，如果此时队列长度，如果此时队列长度为为0，则置理发员为闲状态，否则，队列中排在队，则置理发员为闲状态，否则，队列中排在队首的一名顾客开始理发，队列长度减首的一名顾客开始理发，队列长度减1，并且该顾，并且该顾客在客在di=TIME+Si时刻理发完毕离去。时刻理发完毕离去。2024/5/22 周三10计算机科学与技术学院计算机科学与技术学院COMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGY吉林大学吉林大学 理发店服务系统的人工运行理发店服务系统的人工运行（1）在）在TIMEt0时刻（取时刻（取t0=0），无任何事件发生。），无任何事件发生。下一最早发生的事件为下一最早发生的事件为“顾客顾客1到达到达”，发生时刻，发生时刻为为a1TIMEA115。（2）在）在TIME15时刻，顾客时刻，顾客1到达。按规则到达。按规则2，由，由于理发员闲，开始为顾客于理发员闲，开始为顾客1理发，理发员变忙。顾理发，理发员变忙。顾客客1离去时刻离去时刻d1=TIME+S1=15+43=58下一个最早发生的事件为下一个最早发生的事件为“顾客顾客2到达到达”，顾客，顾客2到达的时刻为到达的时刻为a2a1A215+32=47（58）。）。2024/5/22 周三11计算机科学与技术学院计算机科学与技术学院COMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGY吉林大学吉林大学 理发店服务系统的人工运行理发店服务系统的人工运行（3）在）在TIME47时刻，顾客时刻，顾客2到达。由于理发员到达。由于理发员忙，顾客忙，顾客2只好排队等待，队列长度变为只好排队等待，队列长度变为1。下一个最早发生的事件为下一个最早发生的事件为“顾客顾客1离去离去”，离去，离去时刻时刻d1=58（a3=a2+A3=47+24=71）（4）在）在TIME58时刻，顾客时刻，顾客1离去。按规则离去。按规则3，由，由于队列长度为于队列长度为1，理发员开始为顾客，理发员开始为顾客2理发，队列理发，队列长度为长度为0。顾客。顾客2离去时刻离去时刻d2=TIME+S2=58+36=94下一个最早发生的事件为下一个最早发生的事件为“顾客顾客3到达到达”，顾客，顾客3到达的时刻为到达的时刻为a3=a2+A3=47+24=71。（5）在）在TIME71时刻，顾客时刻，顾客3到达，到达，2024/5/22 周三12计算机科学与技术学院计算机科学与技术学院COMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGY吉林大学吉林大学 理发店服务系统的人工运行理发店服务系统的人工运行上述运行过程可在实体流程图上标注。上述运行过程可在实体流程图上标注。首先在实体流程图队列框和永久实体状态判断框首先在实体流程图队列框和永久实体状态判断框旁边标出系统的初始状态，如在旁边标出系统的初始状态，如在“排队等待排队等待”框框边上标边上标0，“理发员闲理发员闲”边上标边上标YES，在流图下方，在流图下方标标TIME0。然后，当时间推进到一个新的时刻点时，在对应然后，当时间推进到一个新的时刻点时，在对应框图上标出当前和未来各个时刻的实体状态。框图上标出当前和未来各个时刻的实体状态。2024/5/22 周三13计算机科学与技术学院计算机科学与技术学院COMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGYCOMPUTER SCIENCE AND TECHNOLOGY吉林大学吉林大学 理发店模型人工运行结果理发店模型人工运行结果 A顾客到达，顾客到达，D顾客离去，顾客离去，B理发员忙，连在一起的数字是顾客编号理发员忙，连在一起的数字是顾客编号 时间时间事件事件理发员状态理发员状态队列队列状态状态下一个下一个最早最早事件事件当前当前将来将来tt+t长度长度0无无15/1A闲闲闲闲015/1A151A47/2A,58/1D闲闲B1047/2A472A71/3AB1B1158/1D581D94/2DB1B2071/3A713A111/4AB2B2194/2D2024/5/22 周三14