生产计划_生产计划与控制--制造系统的建模方法

1 第4章制造系统的建模方法 4 2活动循环图法4 4Petri网建模理论4 4 1Petri网的基本概念4 4 2Petri网的扩展形式4 4 3基于Petri网的事件关系分析4 4 4基于Petri网的系统性能分析4 4 5Petri网建模与分析实例4 5排队系统模型4 5 1排队系统的基本概念4 5 2顾客到达时间间隔和服务时间分布4 5 3排队系统的应用案例4 6库存系统模型4 6 1库存系统的基本概念4 6 2确定型库存模型4 6 3随机型库存模型 2 活动循环图法 ACD 基本原理 离散事件系统建模方法之一 活动循环图法 ActivityCycleDiagram ACD ACD认为 系统中的每个实体都按照各自的循环方式发生变化 静止状态和活动状态 这两种状态在循环交替出现 ACD以 表示静止状态 以 表示活动状态 以有向箭头 表示静止状态与活动状态之间的转换 当系统中有多个实体时 有向弧就要使用不同的颜色或线型 以示不同实体的区别 3 活动循环图法 ACD 建模方法与建模过程 根据研究对象的不同 可以建立系统不同层次的ACD模型 即高层次模型可以进一步分解为低层次的模型 ACD法注重 个体 的活动 系统状态的变化是全部个体状态变化的集合 ACD法的缺点 当系统庞大 复杂时 活动循环图将十分复杂 ACD法只描述系统的稳态 而不研究系统的瞬态 如动作的开始 结束等 ACD法缺乏定量的分析工具 4 活动循环图法 ActivityCycleDiagram ACD ACD法中的术语 实体活动队列实体行为模式直联活动和虚拟队列合作活动 5 活动循环图法 ACD 举例 一个由一位工人看管若干数控机床的加工车间 工人的任务是 1 若刀具完好 则安装工件按运行按钮 2 若若刀具损坏或需要更新 则先重装刀具 然后按运行按钮 上述工作仅当机床完成一次自动加工工序并停止运行时工人才能执行 假定每台机床均可加工各种工件 不会发生刀具 工件短缺现象 希望通过建模仿真来研究工人的忙闲率 1 识别实体和属性 工人 安装工件 RESET 安装刀具 RETOOL 其它活动 AWAY 等待 WAITING 机床 安装刀具 安装工件 和 加工 RUNNING 6 活动循环图法 ACD 举例 2 画实体活动周期图 绘制实体活动周期图必须遵循以下两个原则 交替原则 闭合原则 7 活动循环图法 ACD 举例 3 系统活动周期图 8 活动循环图法 ACD 举例 4 增加必要的虚拟实体 5 确定模型的参变量和属性描述变量 参数 机床数量 参变量 累计加工的工件数 和 累计加工时间 等 属性变量 加工工件时间 安装刀具时间 安装工件时间 饮茶时间 等 服务规则 9 活动循环图法 ACD 建模步骤 1 识别实体和属性 2 分析各类实体的活动与状态及其变化的顺序 3 画出个实体的ACD 4 将实体ACD连接成系统ACD 5 增添必要的虚拟实体 6 表明活动发生的约束条件和占用资源的数量 7 给出模型参数 参变量计算方法及属性描述变量取值方法模型 以及排队规则 4 4Petri网建模与仿真4 4 1Petri网的概述4 4 2Petri的基本概念4 4 3Petri网的运行规则4 4 4Petri网的变迁间的关系4 4 5Petri网的行为特性4 4 6Petri网的行为特性分析方法4 4 7Petri网的分类4 4 8Petri网建模举例4 4 9高级Petri网 11 4 4 1Petri网的概述 离散事件系统建模方法之三 Petri网 Petrinet 1962年 德国人CarlAdamPetri首次使用网状模型模拟通信系统 后发展成为Petri网理论 Petri网能够描述系统的结构特征 并能对系统的动态性能进行分析 与其它建模方法相比 Petri网建模具有下述优点 Petri网具有准确的图形化建模能力和严密的数学基础 能够定性描述和定量分析系统中顺序 并发 随机和冲突等事件关系 12 4 4 1Petri网的概述 以Petri网模型为基础可以生成系统的控制逻辑代码及仿真逻辑代码 通过仿真或数学方法 由Petri网模型分析系统的有界性 活性及可重用性等系统逻辑特性以及产量 设备利用率等性能指标 Petri网提供了比其它建模工具更为丰富的模型信息 80年代以后 Petri网开始应用于制造系统的仿真 调度和控制建模以及系统性能分析中 13 4 4 2Petri的基本概念 Petri网的基本概念 resource state transition place event condition capability 14 4 4 2Petri的基本概念 Petri网的定义 Petri网有两种表示方式 一种是形式定义 另一种是图形表示 形式定义规定了Petri网的结构 组成 节点间的相互关系和动态行为 形式定义具有严密性 精确性 抽象性和概括性等优点 但是不形象 不直观 也不易于理解 Petri网的图形表示则具有形象直观 易于理解的特点 但是图形表示具有具体性 即Petri网图形往往与特定的建模实例相对应 15 4 4 2Petri的基本概念 1 定义1 基本Petri网 N 其中 P p1 p2 pm 为库所 place 的集合 T t1 t2 tn 为变迁 transition 的集合 F P T T P 为输入函数和输出函数集 称为流关系 三元组N P T F 构成网 net 的充分必要条件 P T 规定了库所和变迁是两类不同的元素 P T 表示网中至少有一个元素 F P T T P 建立了从库所到变迁 从变迁到库所的单方向联系 并且规定同类元素之间不能直接联系 16 4 4 2Petri的基本概念 dom F cod F P T dom F x y x y F 为F所含有的有序偶的第一个元素的集合cod F y x y x F 为F所含有的有序偶第二个元素的集合dom F cod F P T则规定了网中不能有孤立元素 变迁的发生受到系统状态的控制 即变迁发生的前置条件必须满足 变迁发生后 某些前置条件不再满足 而某些后置条件则得到满足 Petri网描述系统的最基本概念是库所和变迁 库所表示系统的状态 变迁表示资源的消耗 使用及使系统状态产生的变化 17 4 4 2Petri的基本概念 库所 变迁 N 其中 P p1 p2 p3 p4 T t1 t2 t3 F p1 t1 t1 p2 t1 p3 p2 t2 t3 p5 18 4 4 2Petri的基本概念 图形化表示 Petri网是由节点和有向弧组成的一种有向图 用圆圈 0 表示库所用短竖线 或矩形 口 表示变迁以联结库所与变迁之间的有向弧表示输入输出函数用令牌 token 库所中的黑点 表示库所中拥有的资源数量 库所中令牌分布决定变迁的使能 enabled 和激发 fire 变迁的激发又将改变令牌的分布 以变迁激发导致令牌在库所间的流动 Petri网可以用于模拟系统的动态运行过程 反映系统的动态特性 19 4 4 2Petri的基本概念 W 权函数 权重 每个变迁发生一次引起的相关资源数量上的变化 w p t 或w t p 缺省时 权重为1 K 容量函数 库所容量 标注在库所旁边 缺省时 权重为1 M 标识 库所中拥有的资源 令牌 数量及其分布 标识以库所中的黑点表示 20 4 4 2Petri的基本概念 举例 一个工业生产线Petri网模型 有一条工业生产线 它要完成两项工业操作 这两个操作分别用变迁t1和变迁t2表示 第一个变迁t1将传入生产线的半成品s1和部件s2用两个螺丝钉s3固定在一起 变成半成品s4 第二个变迁t2再将s4和部件s5用三个螺丝钉s3固定在一起 变成半成品s6 完成操作t1和t2都要用到工具s7 假定由于存放空间的限制 部件s2和s5最多不能超过100件 停放在生产线上的半成品s4最多不能超过5件 螺丝钉s3存放的件数不能超过1000件 21 4 4 2Petri的基本概念 下图是一个具有W的petri网图 在这个图上弧线上标有数字 22 4 4 2Petri的基本概念 六组元 P T F K W M0 构成库所 变迁网系统 place transitionsystem P T 系统 的条件是 N P T F 是构成 的基网 K W M0分别为N上的容量函数 权函数和初始标识 2 定义2 库所 变迁网系统 初始标识M0 m1 m2 mm 中的分量表示起始状态时相应库所中令牌的数量 系统运行过程中的标识用M表示 容量函数K表示库所的容量 有时 允许某些库所的容量为无穷 表示这些库所的容量不会对系统的行为构成限制 23 4 4 2Petri的基本概念 上述定义给出了从结构到资源的静态特征 再定义变迁发生的条件和结果 构成了网系统的完整定义 权函数W规定每个变迁发生一次引起的相关资源数量的变化 一般地 对于任何 x y F 0 W 网系统的动态规律称为变迁规则 transitionrule 24 4 4 3Petri网的运行规则 3 定义3 变迁发生条件 运行规则 p t M p W p t p t M p K p W t p p t p t M p K p W p t W t p 则称t在M下有效 记作M t 六组元 P T F K W M 为一Petri网系统 对于任意t T变迁元素 如果在标识M下 有 25 4 4 3Petri网的运行规则 M 为M之后继 successor 的事实记作M t M 若M t 则t在M可以发生 同时将标识M改变为M的后续M 对于任何p P M 为 4 定义4 变迁发生后果 运行规则 4 4 3Petri网的运行规则 下图是一个petri网系统中变迁t激发前和激发后的标识 例 根据Petri网的运行规则 按照t1t2t3t4的顺序 依次对图1中变迁发生进行检查 28 4 4 4Petri网的变迁间的关系 基于Petri网的事件关系分析1 事件关系逻辑图 a顺序关系 b并发关系 c冲突关系 e迷惑关系 d冲撞关系 29 4 4 4Petri网的变迁间的关系 基于Petri网的事件关系分析1 事件关系逻辑图 f死锁关系 Petri网的可达性 有界性和安全性 活性以及可逆性 4 4 5Petri网的行为特性 1 可达性可达性是Petri网的一个重要特性 给定一个Petri网 已知初始标识M0可以到达那些标识 或者给定某一标识 是否可以从初始标识通过一系列变迁到达该标识 定义5 若从初始标识开始实施一个变迁序列产生标识 则称该标识是从M0可达的 若只要从开始实施一个变迁即可产生 则称是从M0立即可达的 所有从M0可达的标识的集合称为可达标识集或可达集 记为R M0 31 4 4 5Petri网的行为特性 可达树描述了从M0出发的所有可能启动序列的集合 它将R M0 的各个标识作为节点 是以从M0到各个节点的发射系列为树枝画出的图 32 4 4 5Petri网的行为特性 可达性可描述制造系统这样的2个问题 1 系统按照一定的轨迹运行 系统能否达到一定的状态或不期望的状态不出现 典型的问题是生产调度计划的验证 即按照一定的生产计划进行生产 一定的生产任务是否能够完成 2 要求到达一定的状态 如何确定系统的运行轨迹 典型的问题是生产调度问题 33 4 4 5Petri网的行为特性 2 有界性和安全性定义6 对于Petri网 若存在一个整数 使得M0的任何一个可达性标识的每个位置中的标识数都不超K 则称Petri网为K 有界或简称有界 若K 1 则称此Petri网为安全的 这种网的每个位置或有一个标识 或没有标识 通常 位置用于表示制造系统中的工件 工具 托盘以及AGV的存放区 工件的存放区就是缓冲区 还用于表示资源的可利用情况 确认这些存放区是否溢出或资源的容量是否溢出是非常重要的 Petri网的有界性是检查系统是否存在溢出的有效尺度 当位置用于描述一操作 该位置的安全性能够确保不会重复启动一正在进行的操作 34 4 4 5Petri网的行为特性 3 活性定义7 对于一变迁t T 在任一标识下 若存在一个变迁序列 该变迁序列的实施使得此变迁t可实施 则称该变迁是活的 若一Petri网的所有变迁都是活的 则该Petri网是活的 死变迁和锁死从反面描述Petri网的活性 出现锁死的原因是不合理的资源分配策略或某些或全部资源的耗尽 在自动化制造系统中 许多资源是共享的 在这样的资源共享系统中 下列4个情况可能同时满足 从而导致锁死 1 互斥 一个资源不可以为2个或2个以上过程同时使用 一过程排斥其它过程对于该资源的占用 2 占用且等待 一过程已占用某一或某些资源 同时又在请求占用其它资源 3 无抢占 已分配给某一过程的资源不能从该过程中抢走 除非该过程使用此资源完毕后释放 4 循环等待 2个或更多过程排成一个链 链上每个过程都在等待一个正在被链上下一个过程占用的资源 除非系统控制软件具有探测和恢复系统功能 最初发生在子系统中的锁死可能传播到系统的大部分 从而导致系统的完全停顿 4 4 5Petri网的行为特性 36 4 4 5Petri网的行为特性 37 4 4 5Petri网的行为特性 38 4 4 5Petri网的行为特性 4 可逆行定义8 一Petri网 若对于每一个标识M R M0 M0都是从M可达的 则称该Petri网是可逆的 具有可逆性的petri网被称为可逆网 因此 一个可逆网可以返回初始标识或初始状态 在许多实际应用中 往往只要求系统回到某个特定状态 称为为主宿状态M 而无需回到初始状态 对于R M0 的每个标识M 主宿状态M 都是可达的 可逆性意味着模型可以自身初始化 这对于自动从差错中恢复是极为重要的 39 4 4 5Petri网的行为特性 上图是一个可逆的Petri网 在这个网中 初始标识M0 0 0 1 1 1 经过变迁序列t2t1t3t4可以回到初始标识 M 0 0 1 1 1 Mt2 1 1 0 1 1 Mt1 1 0 1 1 1 Mt3 0 0 1 0 2 Mt4 0 0 1 1 1 40 4 4 5Petri网的行为特性 5 可覆盖性如果一个Petri网有无限多个可达标识 为了用有限个图来表示它 引入符号 来表示无限 对每个正整数n n 这样 就可以在一个有限图中 使每一个标识用图中的一个节点表示 这样的图称为覆盖图 定义9 在一个Petri网中 一个标识M称作可覆盖的 仅当在R M0 中存在一个标识M 使得对于网中的每个库所p 有M p M p 成立 备注 有如下性质 对每个整数n 有 n n n 41 4 4 5Petri网的行为特性 42 4 4 5Petri网的行为特性 6 同步距离系统的一个重要特性是事件间发生的依赖程度 即某个事件的发生依赖于其他事件的发生 例如同时发生 交替发生或以任意次序发生 极端情况是完全独立 定义10 事件t1和t2间的同步距离d12 d12 max n t1 n t2 其中n t1 和n t2 分别为事件t1和t2在启动序列 中的发生次数 为起始于R M0 中的任何标识M的一个启动序列 同步距离是对未引入 时间 概念的系统的动态行为的一种度量 43 4 4 5Petri网的行为特性 并发系统的Petri网 上图表示的是一个并发系统 t2 t3可以同时发生 此时d23 0 也可以一前一后的发生 此时d23 1 44 4 4 5Petri网的行为特性 并发系统的Petri网 d12 两组事件异步 d12 两组事件以d12为距离相互同步 d12 0 两组事件在时间和空间上一起发生 d12 1 两组事件必须交替发生 45 4 4 6Petri网的行为特性分析方法 对于行为特性 目前较成熟的分析方法只能对部分特性进行分析 对其他特性进行分析的方法仍在研究之中 Petri网的行为特性分析方法分为三类 1 分层或化简 2 可达性 可覆盖性 树 3 矩阵方程求解 46 4 4 6Petri网的行为特性分析方法 Petri网的可达树的构建算法 让初始标识M0为树根 并作上 new 的记号 若 new 标识存在 则重复以下各步 否则终止 选择某一 new 标识M 3 1 若M与树中间已有的其它标识相同 则将其记为 old 然后转向其它 new 标识 3 2 若在M下无变迁可实施 则将M记为 deadend 对于M下可实施的变迁t 做以下事情 4 1 实施t由M产生标识M 4 2 若在从树根至M 的路径上存在一标识M 使得M 覆盖M 即M M 则对于那些使M p M p 成立的p 用 取代M p 4 3 以M 为一节点 从M至M 画一有向线 将其记为t 并将M 记为 new 除去M的 new 标识 1 可达性树分析法 47 4 4 6Petri网的行为特性分析方法 Petri网的可达树的构建算法 1 可达性树分析法 48 4 4 6Petri网的行为特性分析方法 基于可达树 可以做以下分析 1 当且仅当树中所有节点上均不出现 时 Petri网是有界的 此时 可以在树中找出某一位置中最大的托肯数K 则该位置是K 有界的 若K是树中所有位置中的最大托肯数 则该Petri网是K 有界的 2 当且仅当树中所有的节点仅包含0或1时 该Petri网是安全的 3 没有任何死点包含 则树中死点的个数就是Petri网死标识的数目 若树中死点之一包含 则Petri网包含无数个死标识 4 某变迁在树中不出现 则该变迁是死变迁 5 在不包含 的树中 若给定任何两个节点之间 都存在一有向路径 在该路径上所有变迁都出现 则该Petri网是活的6 在无 出现的树中 若从任何节点到根节点之间都存在一有向路径 则该Petri网是可逆的 49 4 4 6Petri网的行为特性分析方法 2 状态方程分析法 关联矩阵 4 4 6Petri网的行为特性分析方法 例 在下图中 初始标识为M0 1 0 0 T 输入函数矩阵 输出函数矩阵和关联矩阵分别为 4 4 6Petri网的行为特性分析方法 例 在下图中 初始标识为M0 1 0 0 T 输入函数矩阵 输出函数矩阵和关联矩阵分别为 52 4 4 6Petri网的行为特性分析方法 2 状态方程分析法 状态方程 53 4 4 6Petri网的行为特性分析方法 2 状态方程分析法 状态方程 4 4 6Petri网的行为特性分析方法 2 状态方程分析法 状态方程在可达性分析中的应用 例 在下图中 4 4 6Petri网的行为特性分析方法 2 状态方程分析法 状态方程在可达性分析中的应用 4 4 6Petri网的行为特性分析方法 2 状态方程分析法 状态方程在可达性分析中的应用 4 4 6Petri网的行为特性分析方法 2 状态方程分析法 状态方程在可达性分析中的应用 4 4 6Petri网的行为特性分析方法 2 状态方程分析法 状态方程在可达性分析中的应用 4 4 6Petri网的行为特性分析方法 2 状态方程分析法 状态方程在可达性分析中的应用 4 4 6Petri网的行为特性分析方法 2 状态方程分析法 状态方程在可达性分析中的应用 61 4 4 7Petri网的分类 根据容量函数K和权函数W取值范围不同 可以将Petri网系统分为三种类型 1 K 1和W 1 此时库所元素只能有 有令牌 和 无令牌 两种状态 因而可以理解为 真 与 假 两种状态的布尔运算 网论中将这种库所称为条件 只与条件关联的变迁称为事件 由条件和事件构成的网系统称为基本Petri网系统 2 K 和W 1 这类系统称为Petri网的网系统 也称库所 变迁网 P T网 3 K和W为任意函数 将K和W为任意函数的系统称为库所 变迁系统 P T系统 一般地 将P T网和P T系统统称为低级Petri网系统 LLPT 62 4 4 8Petri网建模举例 63 4 4 8Petri网建模举例 64 4 4 8Petri网建模举例 t 12 65 4 4 9高级Petri网 前面接受的基本Petri网系统 低级Petri网系统 主要有两大不足 1 表达能力有限 稍微复杂一点的系统就要使用大量的库所和变迁 由此所引起的 组合爆炸 问题使得Petri网往往难于理解和分析 2 不能表示事件间的时间关系 为了有效地解决这两个问题 并且在应用中不断改进 人们提出了高级Petri网系统 66 4 4 9高级Petri