第3章生产系统建模方法

1、生产系统建模与仿真生产系统建模与仿真 Modeling and Simulation of Production System第第3章章 生产系统建模方法生产系统建模方法 第3章 生产系统建模方法 3.1 系统建模方法概述 3.2 实体流图法 3.3 活动循环图法 3.4 面向对象建模方法及统一建模语言 3.5 Petri网建模理论与方法 基本要求v理解实体流图法生产系统建模v理解活动循环图法生产系统建模v理解Petri网建模理论与方法v了解面向对象的建模方法生产系统建模系统建模方法概述v离散事建模中存在的困难离散事件的发生时刻是离散的,不 连续性是它的本质特征。离散系统的性能指标往往具有一些

2、离散的特征,如零件的加工时间等。系统中普遍存在着一些随机性的因素。复杂离散系统通常具有分层和递阶特征。存在“状态爆炸”性和计算可行性问题。系统建模方法概述 模型反映系统结构、参数及其主要行为特征之间的关系,它是系统设计、运行和控制的基础。根据建模手段和目标,可以将离散事件动态系统模型分为三个层次:即逻辑层次、统计层次和代数层次。本章介绍前两个层次中的几种体系较完整且得到较多工程应用的离散事件系统建模方法。实体流图概念 : 实体流图法采用与计算机程序流程图相类似的图示符号和原理，建立表示临时实体产生、在系统中流动、接受永久实体服务以及消失等过程的流程图。该图可以表示事件、状态变化及实体间相互作用

3、的逻辑关系。实体流图v常用符号：常用符号：菱形框判断;矩形框事件、状态、活动等中间过程;圆端矩形框开始和结束；箭头线逻辑关系。实体流图v 具体建模思路：具体建模思路：(1)确定组成系统的实体及属性，将队列作为一种特殊的实体来考虑。(2)分析各种实体的状态和活动，及其相互间的影响。队列实体的状态是队列的长度。(3)考虑有哪些事情（事件）导致了活动的开始或结束，或者可以作为活动开始或结束的标志，以确定引起实体状态变化的事件，并合并条件事件。实体流图v 具体建模思路具体建模思路: (4)分析各种事件发生时，实体状态的变化规律。 (5)在一定的服务流程下，分析与队列实体有关的特殊操作（如换队等）。 (

4、6)通过以上分析，以临时实体的流动为主线，用约定的图示符号画出被仿真系统的实体流程图。实体流图v 具体建模思路具体建模思路: (7) 给出模型参数的取值、参变量的计算方法及属性描述变量的取值方法。 (8) 给出队列的排队规则。由多个队列存在时，还应给出其服务规则（包括队列的优先序、换队规则等）实体流图v例3 .1 一个理发店只有一个理发师，顾客来后按先来先理原则接受服务，只要有顾客理发师就不停歇。若店里有顾客，新顾客来后就会排队而不会离开。 建模目的是考察理发师的忙闲情况。建模目的是考察理发师的忙闲情况。实体流图v例3 .1 (1)辨识系统实体 该理发店是一个单服务台单队列服务系统。理发师是永

5、久实体，顾客是临时实体，顾客队列是一类特殊实体。实体流图v例3 .1 (2)分析实体状态和活动 理发师有“理发”和“休息”两个活动，对应“忙”和“闲”两种状态。 顾客与理发师协同完成理发活动或者排队等待，有“等待服务”和“接受服务”两种状态。 队列的状态用队列的长度标识。实体流图v例3 .1(3)分析实体状态的变化情况v 顾客到达，若理发师“忙”，则进入“等待 服务”，否则进入“接受服务”状态。v 排队中的顾客，在理发师完成了前一个服务 后，进入“接受服务”状态，否则保持“等待服 务”状态。v 理发师完成某一顾客服务后，若队列处于“ 非零”状态，则立即开始服务活动，否则进入“ 闲”状态。实体流

6、图v例3 .1 (4)分析引起状态变化的事件v 顾客到达或顾客结束排队可导致“服务”活动开始，而顾客离开或顾客理发完毕可导致“服务”活动结束。后两个事件为条件事件，且有因果关系，可 以合并，不单独考虑。实体流图v例3 .1 (5)分析队列实体的操作v 由于本问题中只有一个队列，且顾客不会因人多而离去，因此队列规则简单，没有换队等特殊的队列操作。实体流图v例3 .1 (6)画出系统实体流程图v 通过前面分析，以顾客的活动为主线，画出理发店服务系统的实体流图。可从顾客到达系统开始，按照事件和活动交替原则，按顺序画出实体在系统中的流动过程。实体流图v例3 .1 实体流图v例3 .1 (7)确定模型参

7、变量v 需给出的模型属性变量有:顾客到达时间、理发师为一个顾客理发所需的服务时间等，它们 的值可以从不同的分布函数中抽取。实体流图v例3. 2售票窗口服务系统 一名售票员同时负责剧票的窗口销售和电话咨询工作。购票者在窗口排队，先到先购票，咨询者打来的电话由系统存贮后按先来先服务原则转给售票员予以答复，电话服务比窗口服务优先。但是售票员正售票时若来电话，则必须完成本次售票后才能接听。v 建模目的:研究售票员的忙闲率。实体流图v例4. 2售票窗口服务系统 本系统中售票员为永久实体永久实体，有“窗口售票”和“电话服务”两种活动，状态状态包括“空闲” “接电话”和“售票”三种。电话咨询者和购票者为两类

8、临时实体临时实体。本例特点在于同时存在两个队列，但两队列中的顾客不可互相换队。 试绘出售票窗口服务系统的实体流图模型。实体流图v例3. 2售票窗口服务系统模型属性变量模型属性变量:“购票者到达时间”、话咨询者到达时间”、“售票服务时间”、电话服务时间”，均为随机变量。排队规则排队规则:先到先服务。服务规则服务规则:分别排队，电话优先。实体流图v例4. 2售票窗口服务系统实体流图v例3. 2售票窗口服务系统 本例中有两类临时实体同时流动，因此可能出现资源冲突。当系统中实体类型和数量较多且存在资源占用冲突现象时，利用实体流图法建模便会产生困难。 对资源冲突类问题的描述，活动循环图方法有其独到之处。

9、实体流图v实体流图模型的人工运行实体流图模型的人工运行v 建立实体流图模型后，选取有代表性的例子将实体流图全部手工执行一遍，称为人工运行。 要求遍历实体流图的所有分支和所有状态，检查模型组成和逻辑关系是否正确。实体流图v实体流图模型的人工运行实体流图模型的人工运行v v例例3.1中，假定：中，假定：v(1)系统的初始状态 初始时刻对应为实际系统开门营业的时刻。此时，设理发师状态为“闲”，队列长度为0。v(2)模型参数及变量取值 模型变量包括顾客到达时间间隔和为顾客理发的时间。为讨论方便，这里取其样本值为:实体流图v实体流图模型的人工运行实体流图模型的人工运行v 例3.1 实体流图v实体流图模型

10、的人工运行实体流图模型的人工运行v例3.1v规则1:确定当前仿真时间 仿真开始后，仿真时间逐步向前推移，每一步推进到下一最早事件的发生时刻，即选取当前时间之后所有顾客到达时间和理发师开始为顾客服务时间中的最小者。之后转规则2或规则3。实体流图v实体流图模型的人工运行实体流图模型的人工运行v例3.1 v规则2:顾客到达事件处理 若TIME时刻有顾客到达，可确定下一顾客到达时刻。如果此时理发师忙，则顾客进入队列等待，队长加1;否则置理发师为忙状态，顾客开始接受理发服务。转规则1。实体流图v实体流图模型的人工运行实体流图模型的人工运行v例3.1 v规则3:顾客离去事件处理 若在当前TIME时刻有顾客

11、离去，若此时队长为0，则置理发师为闲状态;否则队首的顾客开始接受理发服务，队长减1。转规则1实体流图v实体流图模型的人工运行实体流图模型的人工运行v例3. 3按照前述规则对例3. 1给出的理发店服务系统模型进行人工运行。实体流图v实体流图模型的人工运行实体流图模型的人工运行v例3. 3按照前述规则对例3. 1给出的理发店服务系统模型进行人工运行。TIME=47时模型的人工运行结果时模型的人工运行结果活动循环图法 对于生产系统某些本质属性和行为的描对于生产系统某些本质属性和行为的描述，目前还难以建立精确的解析模型，因述，目前还难以建立精确的解析模型，因此建立系统的逻辑模型便成为一种重要的此建立系

12、统的逻辑模型便成为一种重要的研究手段。研究手段。 v活动循环图活动循环图(Activity Cycle Diagram)法，法，简称简称ACD法法,是用于表示是用于表示系统内各要素系统内各要素(实体实体)间间逻辑关系的一种方法。逻辑关系的一种方法。活动循环图法v活动循环图表示 在活动循环图中，实体的状态被分成了静止状态和激活状态两类，并分别用不同的符号来表示，以圆圈表示实体的静止状态，以矩形表示实体的活动状态，以有向弧表示静止状态与活动状态之间的转换。活动循环图法v建模方法与过程建模方法与过程 ACD法建模的具体过程法建模的具体过程: (1)辨识组成系统的实体及其属性辨识组成系统的实体及其属性

13、 永久实体永久实体 临时实体临时实体 队列不作为实体考虑队列不作为实体考虑活动循环图法ACD法建模的具体过程法建模的具体过程: (2)分析各类实体的活动和状态 确定实体状态的类型(活动或静止),分析实体状态变化的顺序关系。 活动循环图法ACD法建模的具体过程法建模的具体过程:(3)根据实体状态分别画出各实体的活动循环图以实体活动过程为依据。 遵从以下原则:v交替原则。v闭合原则。 活动循环图法ACD法建模的具体过程法建模的具体过程:(4)将各实体的活动循环图连接成系统活动循环图 (5)增添必要的虚拟实体(6)标明活动发生(实体进入活动状态)的约束条件和占用资源的数量(7)给出模型参数的取值、参

14、变量的计算活动循环图法 某机械加工系统有两个实体:一台半自动机床和一个操作工人。工人负责安装工件和从机床上取下工件。工件安装完毕后，机床可自动完成工件的加工。加工完毕机床停止，直到工人安装一个新的工件，再开始下一个加工循环。 试用ACD法建模。活动循环图法活动循环图法活动循环图法v活动循环图综合活动循环图法v思考某机械加工系统有两个实体:三台半自动机床和一个操作工人。活动循环图法v活动循环图的人工运行 首先确定系统初始状态。在活动循环图上标记临时实体在初始状态下的位置，给每个实体按到达系统的顺序标号。 标记永久实体在初始状态下的位置。 “等待”或“空闲” 活动循环图法v活动循环图的人工运行初始

15、状态确定后，按如下规则运行模型:规则规则1活动的发生与执行活动的发生与执行 按服务优先级，依次检查各临时实体每一项活动的前置状态(均为静止状态)和标在活动对应状态上方的发生条件，判断活动是否可以开始，满足以下两个条件的活动即可开始:活动循环图法v活动的所有前置状态中均有实体停留，各类永久实体的数量超过或等于相应箭头线上所标明的资源占用量。v 活动发生的约束条件已经满足。活动循环图法v规则规则2确定当前时间确定当前时间 检查所用活动的终止时间，从中选择最小者作为当前时间，然后转规则3。v规则规则3活动的完成活动的完成 从所有已发生的活动中，检出终止时间等于当前时间的临时实体，删掉其标在活动框外的

16、终止时间。之后将相应的临时实体标记移至后续静止状态中。 最后，将参与活动的各永久实体的后续静止状态分别作上标记，转规则1。活动循环图法v仿真运行仿真运行活动循环图法v仿真运行仿真运行活动循环图法v仿真运行仿真运行活动循环图法v例3. 2机床加工系统模型的人工运行活动循环图法vACD法具有直观、形象的优点，但该方法也存在明显缺点: (1)当系统实体数量众多时，活动循环图将非常复杂; (2)该方法只能描述系统的稳态特征，无法进行瞬态研究; (3)该方法缺乏定量的分析工具。 上述缺点限制了ACD法的推广。 活动循环图法v活动循环图法与实体流图法的比较 实体流图法是以临时实体在系统中的流动过程为主线建

17、立的模型，在实体流图中，队列被作为一类特殊的实体来对待，各类临时和永久实体没有独立的符号表示;而活动循环图法则是基于各类临时和永久实体的行为模式，它们均有其单独的图示表达，队列则被看做是实体生命周期中的一种状态。 活动循环图法v实体流图是一种树形流程图，而活动循环图则是由多个环套在一起组成的一种环形的循环图。v 在实体流图中，事件是其重要的组成部分;而在活动循环图中，事件则是隐含在活动之中的。v在实体流图中，状态判断框有着十分重要的作用;而在活动循环图中，则是将需要判断的状态用“空闲”或“等待”等静止状态来表示，对实体是否处于该状态的判断则隐含在模型运行的规则中。活动循环图法v从人工运行规则来

18、看，实体流图的运行规则中只有一条是通用的(体现了事件驱动的仿真策略)，其他各条规则均是从具体的实体流图中抽取，普适性较差;而活动循环图中则存在着与每个具体的活动循环图无关的、普适性很强的运行规则。v 实体流图可以对队列的排队规则和服务规则进行比较详细的描述;与实体流图相比较来说，活动循环图更易于用面向对象的技术来实现，软件上也更易于实现仿真程序的自动生成，而且可以更为方便、直观地对冲突和并发等现象进行表示。如果不考虑模型的运行问题，实体流图法具有比活动循环图法更为广泛的适用范围。面向对象的建模方法与统一建模语言面向对象的建模方法与统一建模语言v面向对象的概念 按照面向对象的观点，客观世界是由许

19、多各种各样的对象所组成的，每个对象都有它们自己的内部状态与运动规律，不同的对象之间通过相互作用和联系构成了各种不同类型的系统。 面向对象的建模方法与统一建模语言面向对象的建模方法与统一建模语言v面向对象的概念 (1)对象(Object) 表示为属性、活动和关联关系三个主要的方面 (2)面向对象(Object- oriented ) 认识客观世界的世界观 、模拟客观世界的一种 方法 (3)消息(Message ) 描述对象间相互作用的一种方式 面向对象的建模方法与统一建模语言面向对象的建模方法与统一建模语言v面向对象的概念 (4)类(Class) 对一组具有相同数据结构和操作的对象进 行描述 (

20、5)继承(Inheritance ) 自动共享类中数据和方法的一种机制 (6)多态性(Polymorphism ) 同样的消息为不同的对象所接收时，也有 可能会导致完全不同的操作 面向对象的建模方法与统一建模语言面向对象的建模方法与统一建模语言v面向对象分析与设计 v面向对象分析 将面向对象的思想应用于系统分析中，即形成了面向对象分析(Object- oriented Analysis, OOA)方法 面向对象分析的基本结构面向对象分析的基本结构 面向对象的建模方法与统一建模语言面向对象的建模方法与统一建模语言v面向对象分析与设计v面向对象分析的一般内容和步骤如下: (1)识别对象辨别所研究的

21、实际系统中包含的客观对象(2)识别结构对象间的组织方式 (3)识别主题系统分析结果的概貌 面向对象的建模方法与统一建模语言面向对象的建模方法与统一建模语言v面向对象分析与设计 v面向对象分析的一般内容和步骤如下:(4)定义属性描述对象状态信息的数据元素 (5)定义方法 定义每一种对象和分类结构应有的行为 定义各实例之间的消息关联 面向对象的建模方法与统一建模语言面向对象的建模方法与统一建模语言v面向对象分析与设计v面向对象设计 系统的设计过程就是将所要求解的问题分求解的问题分解解为一些对象及对象间传递消息的过程对象及对象间传递消息的过程。 面向对象的建模方法与统一建模语言面向对象的建模方法与统

22、一建模语言v面向对象分析与设计 面向对象分析主要是对问题域和系统任务面向对象分析主要是对问题域和系统任务进行描述，通过分析得到对象及其相互间进行描述，通过分析得到对象及其相互间的关系的关系; 面向对象设计则主要是增加系统实现所必面向对象设计则主要是增加系统实现所必需的各种组成成分需的各种组成成分,解决的是这些对象及其解决的是这些对象及其相互关系的实现问题。相互关系的实现问题。 面向对象的建模方法与统一建模语言面向对象的建模方法与统一建模语言v对象建模技术 对象建模技术(Object Modeling Technology, OMT)是由兰博(J.Rumbaugh)等人提出的。 主要应用于对问题

23、需求进行分析、问题求解方法的设计及其程序设计语言或数据库实现 面向对象的建模方法与统一建模语言面向对象的建模方法与统一建模语言v对象建模技术 OMT方法从对象模型、动态模型和功能模型三个既不相同但又相互关联的角度来进建模 Petri网建模理论与方法网建模理论与方法 v1962年（联邦）德国 Carl Adam Petri 博士在他的博士论文“Communication with automate”中首次提出了一种网状结构的信息流模型，后来被称为 Petri 网。 vPetri网是一种用于描述事件和条件关系的网络模型。 v经过几十年的发展，目前Petri网建模方法已经在生产系统和决策系统等众多领

24、域得到了广泛的应用。 Petri网建模理论与方法网建模理论与方法vPetri网主要优点：网主要优点：采用网络图的形式模拟离散事件系统，形式简洁、直观，特别适合于描述系统组织、结构和状态的变化；可以在不同概念级别上表明系统的结构和性质；能有效模拟异步并发系统，直接分析模型实体中是否具有诸如死锁，状态空间无限等异常特征。Petri网建模理论与方法网建模理论与方法vPetri网基本概念 例：用螺钉将3个零件1，1个零件2和2个零件3连接在一起，得到零件4。 Petri网建模理论与方法网建模理论与方法v定义 一个三元组N=(P,T,F),其中P=P1，P2，Pn为库所集合，n为库所的数量；T=T1，T

25、2，Tm为变迁集，m为变迁数量。 必要条件：v Petri 网的非空性：PT,表示网中至少有一个元素。v Petri 网的二元性：PT=，表示库所和变迁是两类不同的元素。Petri网建模理论与方法网建模理论与方法vPetri网中不能有孤立的元素: F (PxT) (TxP) dom(F)cod(F)=P T F是由一个P元素和一个T元素组成的有序偶的集合(称为流关系) dom ( F)和cod ( F)分别为F中有序偶的第一个元素和第二个元素组成的集合 Petri网建模理论与方法网建模理论与方法vPetri网的图形化表示方法网的图形化表示方法 通常采用圆圈“O”和 短竖线“|”来分别表 示库存

26、和变迁。 库所和变迁这两类 节点通过有向弧连接 Petri网建模理论与方法网建模理论与方法v库所(place)可以用来表示条件、资源和缓冲站。v变迁(Transition)可以用来表示事件、任务和作业Petri网建模理论与方法网建模理论与方法v在Petri网中，以权函数（Weight Factor)来表示每个变迁发生一次所引起的相关资源数量的变化，它也称为权重W。未加标注的弧权值默认为1 。v在Petri网中，用K(p)表示库所P的容量 ，标注的库所容量默认为无穷大 。v将库所中拥有的资源(令牌)数量及其分布称为( Marking)，通常记为M，在有向图中用库所中的黑点来表示 ,有M(P)K(

27、P) Petri网建模理论与方法网建模理论与方法v对图2-1中给出的简单加工系统，可以建立其相应的Petri网模型 Petri网建模理论与方法网建模理论与方法v某工业生产线包含两项操作，分别用变迁t1和变迁t2来表示。变迁t1将传入生产线的半成品s1用两个螺钉s2固定在一起，成为半成品s3;变迁t2再将s3、部件s4、部件s5用3个螺钉s2固定在一起，得到产品s6。完成操作t1和t2时都需要用到工具s7 。假定由于存放空间的限制，部件s1和s5最多不能超过100件，停放在生产线上的半成品s3最多不能超过5件，螺钉s2存放最多不超过1000件。建立该生产线生产过程的Petri网模型。 Petri网建模理论与方法网建模理论与方法Petri网建模方法的主要特点有以下几个:v 采用图形建模方法，可以清晰地描述系统内部的相互作用，如并发、冲突和因果依赖等关系。模型直观、易于理解。v 与系统结构关系密切，对系统内部的数据流和物流都可以很好地进行表述，容易在控制模型的基础上直接实