生产管理知识_生产系统建模与仿真概述

生产系统建模与仿真ProductionSystemModeling Simulation 面向工程实际的应用型的基础性课程 是工业工程专业的主导课程 课程介绍 从课程的题目中可以看出 离散系统建模与仿真 其对象是 离散系统生产系统是一个典型的离散系统 物流系统也是一个离散系统 目的是 仿真 即用一种抽象的 能够反映系统研究本质的 虚假 系统 来模拟实际系统 而这虚假系统就是系统模型 课程性质 征求答案 什么是仿真 什么是离散系统的仿真 为什么需要做仿真 何时需要做仿真 如何进行仿真 仿真要做那些准备工作 仿真的可信度如何评价 对仿真模型如何作评价 你知道的仿真软件有哪些 各自具有哪些特征 你希望通过本课程的学习获得些什么 课程试图解决的问题 离散事件系统建模与仿真的基本原理离散事件系统建模与仿真的方法Petri网建模与仿真课程的先修课程 生产运作与管理运筹学计算机编程与应用技术概率论与数理统计课程的考核方法 完成相关作业及期末考核 课程介绍 课程主要内容 课程主要内容构成 第一章离散事件仿真的概述第二章离散事件仿真的分析第三章离散事件仿真的案例分析第四章离散事件仿真的逻辑分析 Petri网 第一章离散事件仿真的概述 1 1离散事件系统仿真的基本概念1 2生产系统仿真的特征1 3服务系统仿真的特征1 4离散系统仿真的基本步骤 1 1离散事件系统仿真的基本概念 什么是系统 系统是按照某些规律结合起来的 相互作用 相互依存的所有元素的集合 系统有哪些种类 连续系统 离散系统 变量状态静态系统 动态系统 时域状态确定系统 随机系统 存在随机变量单变量系统 多变量系统 自由度数量 1 1离散事件系统仿真的基本概念 什么是系统仿真 SystematicSimulation 仿真 对现实中的现象通过某种抽象 建立表达现实变化规律或特征的模型 运用一定的手段加以描述 这就是仿真 系统仿真 首先针对真实系统建立模型 然后在模型上进行试验 用模型代替真实系统 从而研究系统性能的方法 系统仿真将能一一仿效实际系统的各种动态活动 并把系统动态过程的状态记录下来 最终得到用户所关心的系统统计性能 1 1离散事件系统仿真的基本概念 为什么要采用系统仿真 系统所涉及到的专业知识较为广泛 如 机械 生产管理 人事管理 产品设计 生产工艺等现实问题的规律是复杂的 一般很难用一确定的数学方程或数学函数显性地或隐性地表达 科学技术的发展难以适应生产系统研究的需要 仿真是系统特征无法用数学方程 数学函数描述时 为了研究系统特征所采用的一种研究方法 我们可以这样说 仿真是一种 不得已而为之 的方法 1 1离散事件系统仿真的基本概念 系统仿真方法适用怎样的领域 系统仿真的方法适用于任何的领域 工程类 非工程类 机械 电子 化工 交通 管理 经济 政治 1 1离散事件系统仿真的基本概念 系统模型有哪些 系统模型 确定型模型 随机型模型 静态 动态 静态 动态 连续 离散 连续 离散 离散事件仿真 蒙特卡洛仿真 什么是离散事件系统 离散事件系统是包含事件的发生在时间或空间上都是离散的 例如交通管理 生产自动线 计算机网络 通信系统和社会经济系统都是离散事件系统 离散事件系统定义为一组元素 实体 的集合 为了达到某些目的 这些元素以某些规则相互作用 关联而集合在一起 例如制造系统由机器 部件以及操作工人组成 银行系统由出纳员和顾客组成 离散事件系统的变量通常用状态变量表示 如 实体的发生与不发生 事物的计数等等 1 1离散事件系统仿真的基本概念 离散事件仿真模型的特点 随机型 具有随机性的状态变量 动态性 随时间演变是模型的重要特征 离散事件 主要的变化发生在离散的时间点上 1 1离散事件系统仿真的基本概念 事件的发生在时间和空间上都是离散的 系统的数字仿真则经常是面向事件的离散事件系统定义为一组元素 实体 的集合 为了达到某些目的 这些元素以某些规则相互作用 关联而集合在一起 离散事件系统状态变量仅仅在可数的一些时间点上才有变化 系统变量是反映系统各部分相互作用的一些事件 系统模型则是反映这些事件状态的数集 仿真结果是产生处理这些事件的时间历程 在离散事件系统中 各事件以某种顺序或在某种条件下发生 并且大都是随机性的 不能用常规的方法加以研究 连续系统事件的发生在时间和空间上都是连续的 在连续系统的数字仿真中 时间通常被分割成均匀的间隔 并以一个基本的时间间隔计时 在连续系统仿真中 系统动力学模型是由表征系统变量之间关系的方程来描述的 仿真的结果为系统变量随时间变化的时间历程 连续系统与离散系统有何区别 1 1离散事件系统仿真的基本概念 离散事件仿真时钟的演变方法有哪些 时间离散系统只在一些特定的时刻 即 t1 t2 上被考察 通常 为了便于研究 各时间间隔选定为整常数 t 常数 事件离散系统状态的变化 即事件时刻是不连续的 跳跃式的 t ti 1 ti i ti为事件发生时间 1 1离散事件系统仿真的基本概念 l某些系统的建模困难 如 对于大比例系统模型 建模会变得十分复杂 程序的编写与程序的运行都是十分艰巨的 但是随着优质的仿真专业软件的诞生 对于这样系统的仿真日趋简便 l仿真需要大量的计算机机时 这一问题随着计算机技术的发展正在逐步得到解决 l仿真需要大量实际的 准确的数据 这是一般企业所难以提供的 因此对仿真结果的准确性带来了影响 导致了人们对仿真能力的怀疑 总之 正是由于上述的种种因素 是人们对仿真留下了不好的印象 这里还要说明的是 仿真只是计算机编程的一种游戏 游戏的规则来自于问题的本身 游戏的范围也是问题所约定的 离散事件仿真运用存在哪些阻碍 1 1离散事件系统仿真的基本概念 离散事件仿真模型如何建立 如何为一个离散事件系统建立一个模型确定一个系统目标或仿真目的建立概念性模型转换为一个详细模型 制定仿真规则转换为一个计算机计算模型 编制程序代码模型的运行检验 特例检验模型的有效性检验 模型检验 可信度检验典型事件的多次重复仿真 循环过程 1 1离散事件系统仿真的基本概念 离散事件仿真模型的三层次模型概念模型层极其概念性的层次模型 通常是语义性的系统描述 模型是如何构成的 什么是模型的状态变量 哪些是动态变量 哪些是重要变量 详细模型层模型的书面整理模型包括哪些方程 哪些伪随机数 哪些辅助变量等模型参数如何输入 计算模型层计算机程序通用编程语言或仿真语言 1 1离散事件系统仿真的基本概念 系统与系统模型的实质关联是什么 系统 研究的本体系统模型 为研究系统所收集的有关信息的集合 通过研究系统模型来揭示系统的性能 它和 系统 的定义比较 两者都是集合 系统是以某些规律结合起来 有相互作用的元素组成 而系统模型是为了研究其结合规律相互作用所收集的有关信息 因为收集的信息有详细 粗略之分 加上收集方法的差异和研究目的的不同 因此对于同一个系统就会出现多种不同的系统模型 模型是为系统服务的 因此 所揭示的性能规律应该是稳定的 1 1离散事件系统仿真的基本概念 离散事件仿真的输入数据该如何收集和处理 仿真的输入数据来源于事件 采集稳定的数据仿真的输入数据应该与实际数据有同样的变化规律 拟合度检验仿真的输入数据应当是相互独立的 相关性检验 1 1离散事件系统仿真的基本概念 离散事件仿真的输出数据应该有哪些分析 仿真结果的可信度分析仿真运行的效率分析仿真结果的性能分析 离散事件系统仿真模型的简例 某一个工作人员每日的工作是处理文件 他从每天开始工作时即处理文件 直至文件处理完毕或工作结束 每一个文件处理完毕后开始下一个文件的处理 工作间隔一小时休息一次 休息时间为5分钟 但必须是在一个文件处理完毕之后 假设不考虑当天收到的文件 那么文件的数量可以预置 并随着每个作业的完成递减 直至为零 1 1离散事件系统仿真的基本概念 实例求解 实例目标 了解仿真求解方法 手工仿真求解平台 Excel求解原理 每个文件的处理时间 工作时间tw 是一个随机过程 符合一定的概率分布 该工作人员一上班就开始处理文件 所以第一个文件处理的开始时间就是仿真的开始时间 0时刻 后续文件的开始时间tf 上一文件的结束时间或休息后的时间 每一个文件处理的结束时间 文件处理的开始时间 文件处理时间 设置一项统计量 累计工作时间tc 休息后的工作时间之和 当tc 1小时 则置为零 同时标识一次休息 仿真时间推进5分钟 1 2生产系统仿真的特征 产品工艺技术与生产管理的结合相同的结果可以有不同的生产工艺生产管理策略对生产运作产生何种影响稳定的生产过程生产流程的稳定生产时间规律化变化生产过程存在不确定变化人工干预生产作业的不确定变化及学习变化机器设备的不确定故障停机 1 3服务系统仿真的特征 服务技术与服务管理的结合相同结果可以有不同的服务流程服务策略对服务运作产生何种影响客户化的服务过程服务流程随着客户需求而改变服务时间的不确定变化服务过程存在不确定变化服务流程的不确定服务时间的不确定服务资源配置的不确定 客户数量 需求的不确定 1 4离散系统仿真的基本步骤 明确离散系统仿真的需要解决的问题系统运作的流程 确定流程或可能流程 系统运作的管理策略 运作规则系统的概念性建模 明确系统构成的元素系统的详细建模 明确系统各元素的参数系统运行编程 根据管理策略形成系统的运行规则系统试运行 系统模型的有效性检验和可信度检验系统正式运行 第二章离散事件仿真的分析 2 1随机数的产生2 2离散事件仿真建模2 3输入数据分析2 4输出数据分析 2 1随机数的产生 为什么要产生随机数 平时我们遇到的随机数符合怎样的分布 随机数生产的方法有哪些 随机事件是所有不确定事件中唯一可以分析的一种事件形式 因此 对于诸多不能明确解析的实际系统中最常见的就是随机系统 随机系统的运行首要解决的问题就是产生随机数 0 1 均匀分布的随机数 线性平移法 适用于均匀分布的随机数产生 同余法 适用于均匀分布的随机数产生 常用方法 逆变换法 密度函数的反函数可求的状况 舍取法 任意给定分布 组合法 标准分布组合形成的复杂分布 经验生成法 特殊的常用分布 运用经验公式产生 2 1随机数的产生 0 1 随机数的检验数字特征检验分布均匀性检验独立性检验 服从N 0 1 在给定显著性水平后 即可根据正态分布确定临界值 据此判断与理论平均值及与X2理论平均值之差异是否显著 从而决定能否将产生的随机数看作是 0 1 均匀分布随机变量的N个独立取祥值 服从自由度为k 1的 2分布 服从N 0 1 2 2离散事件仿真建模 排队系统 由服务机构 服务模式 可以是服务台 加工机器 搬运设备等 到达模式及排队规则组成的集合 库存系统 由订单到达模式 订单规模 补货数量 交货期及补货策略 盘库间隔 到货规则 组成的集合 流程系统 由特定的一簇服务对象按照其自有的运作流程 顺序及滞留时间 将对应的服务机构 排队系统 库存系统 有序地连接在一起组成的集合 前后事件多对一 前后事件一对多 前后事件多对多 事件的返回 离散事件系统 事件的合并 事件的拆分 离散事件系统 设备可用性 设备可以加工工件的前提是设备是可用的 设备可用的必要条件有 1 当前时刻是生产系统工作日志所规定的正常工作时间 而不是休息 保养 大修的时间 2 当前时刻设备是正常状态 而不是处于损坏 维修 冻结 堵塞等状态 3 当前时刻设备具备正常运行所需的所有技术条件 包括操作工人 工装 模具等 4 当前时刻设备空闲或设备的某一工位空闲 离散事件系统 1 单台机器排序问题 n 1 B n个工件全部经由一台机器处理 离散事件系统 常见单台机器排序问题的目标函数1 平均流程时间最短 2 最大延期量最小 目标函数 为n个零件经由一台机器的平均流程时间 定义 目标函数 使平均流程时间最短 Fi Pi Wi Ti max 0 Li Li Ci di 工件i的延误时间Li0延误 生产系统 离散事件系统 Pi 任务i的作业时间Wi 任务i的开始作业时间 根据排序目标的不同 可以选择不同的排序规则 又称为确定零件加工的优先权 常见的排序规则 SPT ShortestProcessTime 优先选择加工时间最短的工件EDD EarliestDueDate优先选择交货期紧的工件FCFS FirstComeFirstServed按工件到达的先后顺序CR CriticalRate优先选择临界比最小的工件CR 交货期 当前日期 剩余加工时间 离散事件系统 2 求平均流程时间最短的排序问题 求平均流程时间最短的作业顺序 采用SPT原则 按工件加工时间的长短 从小到大按排作业 例 一台加工中心 现有5个工件需要该机器加工 相关的加工时间和要求完成时间 交货期 如下表所示 求平均流程时间最短的作业顺序 离散事件系统 解 根据SPT原则 得出 J4 J5 J1 J2 J3有关项目的计算 发生延迟 发生延迟 43 生产系统 离散事件系统 3 求最大延期量最小的排序问题 求最大延期量最小的作业顺序采用EDD原则 例 同上面的例子 按延期量 完工日期 交货期 大小 从小到大排序 解 根据EDD原则 得出J3 J5 J4 J2 J1 生产系统 离散事件系统 18 1 两台机器排序问题的含义 n 2 F Fmax n个工件都必须经过机器1和机器2的加工 即工艺路线是一致的 生产系统 n项任务在两台机器的排序问题 离散事件系统 2 两台机器排序问题的目标 两台机器排序的目标是使生产周期Fmax最短 Fmax的含义见如下图 生产系统 离散事件系统 3 两台机器排序问题的算法约翰逊法 Johnson sLaw 约翰逊法解决这种问题分为4个步骤 1 列出所有工件在两台设备上的作业时间 2 找出作业时间最小者 3 如果该最小值是在设备1上 将对应的工件排在前面 如果该最小值是在设备2上 则将对应的工件排在后面 4 如果同时出现一个以上的最小值 任意选区一个 5 排除已安排好的工件 在剩余的工件中重复步骤 2 4 直到所有工件都安排完毕 生产系统 离散事件系统 例 某一班组有A B两台设备 要完成5个工件的加工任务 每个工件在设备上的加工时间如下表所示 求总加工周期最短的作业顺序 生产系统 离散事件系统 解 由约翰逊法可知 表中最小加工时间值是1个时间单位 它又是出现在设备1上 根据约翰逊法的规则 应将对应的工件4排在第一位 即得 J4 去掉J4 在剩余的工件中再找最小值 不难看出 最小值是2个时间单位 它是出现在设备2上的 所以应将对应的工件J1排在最后一位 即 J4 J1再去掉J1 在剩余的J2 J3 J5中重复上述步骤 求解过程为 J4 J5 J1J4 J2 J5 J1J4 J2 J3 J5 J1当同时出现多个最小值时 可从中任选一个 最后得J4 J2 J3 J5 J1 生产系统 离散事件系统 1 计算加工周期 按零件序号加工 生产系统 离散事件系统 2 计算加工周期 按约翰逊法 生产系统 离散事件系统 a J1 J2 J3 J4 J5 b J4 J2 J3 J5 J1 生产系统 离散事件系统 离散事件系统仿真可在加入随机因素 工时的变化 设备失效 的前提下以更直观的方式获知那种排序规则更好 离散事件系统仿真是在管理规范化的基础上考虑到更为细节的因素 可使生产线的管理策略更好地适应现实世界 生产系统 离散事件系统 2 3输入数据分析 什么是输入数据 什么是输入数据分析 输入数据分析些什么 仿真模型中 用于支撑仿真进行的各个已知元素的特征参数 有很多这样的参数呈现出 假设为 随机的特征 对各个具有随机特征的已知元素的特征参数 运用数理统计的方法来获得其适当的随机概率分布 以支持仿真过程中的随机数产生 随机概率密度函数 什么分布 分布的参数是多少 分布的检验 拟合度检验 独立性检验 2 3输入数据分析 输入数据分析的基本步骤数据过滤 消除非规律性影响因素 分布的假设 通过频率图的形状估计 假设数据的理论分布假设分布的参数估计 估计假设给定理论分布函数的参数分布的拟合度检验 假设理论分布与实际分布值之间的拟合程度检验 f k s 1的 方检验 变量的相关性检验 系统仿真中随机产生的数据应当符合数据本身独立的特征 f n m 1的t检验 2 4输出数据分析 离散事件仿真的数据特点 不确定性 不可重复性 理论上无统计规律 离散事件仿真数据的真实性是什么 给定置信水平的置信区间如何提高置信水平 增加重复运行的仿真次数 置信度为100 的仿真次数为 2 4输出数据分析 仿真输出数据的性能测度 上式成立的条件是的某一仿真性能参数之间是独立的 自相关函数为零 当自相关函数是负值 上式趋于保守 当自相关函数为正值 上式不成立 须进行详细地检验 2 4输出数据分析 终态仿真的输出分析什么是终态仿真 在某一个持续时间TE内的系统仿真 如 生产设备的使用寿命就是这一类的系统仿真 终态仿真的特征 系统仿真是在零时刻开始 开启 至TE时刻 关闭 其中TE可以是一个随机变量 研究的是不同持续时间TE或 开启 时刻状态对系统性能参数的影响 终态仿真的输出分析 独立重复运行法假设系统仿真进行了n次独立重复运行 得到n个系统性能测度的仿真观察值Y1 Y2 Yn 则系统性能测度的估计量为 2 4输出数据分析 设仿真重复进行了R组 r 1 2 R 为其中的一组仿真 令Yri为第r组仿真中的第i次系统性能测度的观察值 i 1 2 nr 此时 对每一次运行r 其样本均值为 r 1 2 R R次独立重复运行后 系统性能测度的估计量为 上式可以看到 标准差的估计量随着R的增加而减小 即仿真的可信度有所提高 2 4输出数据分析 稳态仿真的输出分析什么是稳态仿真 2 4输出数据分析 提高仿真效率的数据处理方法 第四章离散事件仿真的逻辑分析 Petri网 什么是Petri网 在定义Petri网 PetriNet 时 必须要区别PN结构与标识PN MarkedPetriNet 它定义了DES DiscreteEventSystem 可能的状态 事件 及其它们之间的关系 这相当于连续状态变量系统CVDS的状态方程 在PN中 用标识 Marking 描述DES的状态 后者又称PN 它是指具有一定标识的PN 描述处于一定状态下的DES 相当于给定了状态方程的状态变量在一定时刻值的CVDS 定义 PN的结构是由四要素描述的一个有向图 PNS P T I O 满足 1 P p1 pn 是库所 位置 的有限集合 n 0 为位置 库所 的个数 2 T t1 tm 是变迁的有限集合 m 0 为变迁的个数 P T P T 3 I P T N是输入函数 它定义了从P到T的有向弧的重复数或权 Weight 的集合 这里N 0 1 为非负整数集 4 O T P N是输出函数 它定义了从T到P的有向弧的重复数或权的集合 在表示PN结构的有向图中 库所用圆表示 变迁用长方形或粗实线段表示 若从位置p到变迁t的输入函数取值为非负整数w 记为I p t w 则用从p到t的一有向弧并旁注w表示 若从变迁t到位置p的输出函数取值非负整数w 记为O p t w 则用从t到p的一有向弧并旁注w表示 特别地 若w 1 则不必标注 若I p t 0或O p t 0 则不必画弧 I与O均表示为n m非负整数矩阵 O与I之差C O I称为关联矩阵 Petri网的实例 例 一PN结构如图所示 按照PN的定义 该PN结构可描述如下 P p1 p2 p3 T t1 t2 I p1 t1 1 I p2 t1 1 I p3 t1 0 I p1 t2 0 I p2 t2 0 I p3 t2 1 O p1 t1 0 O p2 t1 0 O p3 t1 1 O p1 t2 0 O p2 t2 1 O p3 t2 0 输入函数 输出函数 关联矩阵 第四章离散事件仿真的逻辑分析 Petri网 在PN结构中 p表示了离散事件系统 DES 的局部状态 P表示DES的整体的状态 T表示其所有可能的事件 某一库所所表示的局部状态实现情况 是否实现 实现了几次 用库所中所包含的标记 Token 数目m p 来表示 用库所p中圆点或数量表示标记 特别地 m p 0 则p中无圆点 表示p所代表的局部状态目前没有实现 t与t 分别表示t的所有输入与输出库所的集合 p与p 分别表示库所p的输入与输出变迁 I与O描述所有可能的状态与事件之间的关系 其中I描述事件发生的前提状态 因 而O描述事件发生所实现的状态 果 Petri网有哪些功效 Petri网的实例 续 例如 图题中 1 从p1与p2到t1有弧连接 既I p1 t1 0 I p2 t1 0 说明t1所表示的事件的发生以p1与p2所表示的局部状态为前提条件 2 而从p3到t1无弧连接 既I p3 t1 0 说明t1所表示的事件的发生不取决于p3所表示的局部状态 3 从t1到p3有弧连接 即O p3 t1 0 表明t1所表示的事件发生将影响p3所表示的局部状态 4 而从t1到其它库所无弧连接 表明t1所表示的事件发生将不影响这些库所所表示的局部状态 Petri网的五要素定义 标识PN为一5要素 PN PNS m P T I O m 此处 1 PNS P T I O 为PN结构 它由Petri网的四要素定义给出 2 m P N为标识PN的标识 它为一列向量 其第i个元素m pi 表示第i个库所中的标识数目 m m p1 m p2 m pn T特别地 DES的初始状态用初始标识表示 记为m0 相同结构的标识PN不是唯一的 Petri网的实例 续 例题如图 包括库所中的圆点 一个标识PN 正规地描述如下 PN P T I O m0 P T I O见前例 m0 1 1 0 T 其中第1个元素为m p1 1 第2个元素为m p2 1 第3个元素为m p3 0 第四章离散事件仿真的逻辑分析 Petri网 Petri网的使能 在DES中某一事件必须在所有前提条件 状态 得以满足 实现 的情况下才可能发生 有时 要求某一前提条件 状态 必须满足多次 实现多次 在DES的Petri网中 我们以变迁t表示一事件 用变迁的使能 Enabling 表示事件因前提条件得以满足而能够发生 我们还用t的输入库所 通过指向t的弧连接的库所 表示该事件的发生所需要的前提局部状态 用由输入库所至t的输入函数定义这些要求局部前提状态实现的次数 而局部状态的实现情况由库所中所包含的标识数目来表示 因此 变迁t的使能不仅与其输入函数有关 而且与其所有输入库所中的标识数目有关 为此 引入以下变迁使能规则 使能的例子 Petri网的使能定义一变迁t T在标识m下使能 当且仅当 p t m p I p t 例如 在上例中 变迁t1的使能 t1 p1 p2 由于m p1 1 I p1 t1 1 m p2 1 I p2 t1 1 因此变迁t1使能的 而 t2 p3 由于m p3 0 I p3 t2 1 因此t2不使能 第四章离散事件仿真的逻辑分析 Petri网 Petri网中变迁的发生 激发 Firing 规则 所有前提条件得以满足的事件的发生 将 消耗 这些前提状态 同时改变与该事件有关的局部状态 结果状态 即使得这些结果状态实现一定的次数 在PN中 用使能的变迁的激发来描述事件的发生 所消耗的前提状态及其次数由变迁的输入函数定义并通过从输入库所中移去相应数量的标识来表示 所产生的结果状态及其次数由输出函数确定并用输出库所中增加的标识表示 由于输入库所中的标识的减少以及输出库所中标识的增加 使得PN的标识发生变化 第四章离散事件仿真的逻辑分析 Petri网 激发规则的定义在标识m下使能的变迁t的激发 Firing 将产生新标识m p P m p m p I p t O p t 对于p t m p m p I p t 对于p t m p m p O p t 对于p t p t 既是t的输入又是输出库所 p P m p m p I p t O p t 对于p t p t 既不是t的输入又不是输出库所 m p m p 称标识m 是 通过t的激发 直接从m可达的 记为m t m 状态转换的例子 在右上图所示的PN中 在m0 1 1 0 T下使能的t1激发后 将产生新的标识m1 见右下图 m1 p1 m0 p1 I p1 t1 O p1 t1 1 1 0 0 m1 p2 m0 p2 I p2 t1 O p2 t1 1 1 0 0 m1 p3 m0 p3 I p3 t1 O p3 t1 0 0 1 1 m1 0 0 1 T 上例的计算 似乎给我们告诉了些东西 几种特殊的PN 若PN的所有变迁至多有1个输入弧或输出弧 即I P T 0 1 O T P 0 1 则此PN称为普通PN OrdinaryPetrinet 若PN无自闭环 即某一库所同时是某一变迁的输入与输出库所 则此PN称为纯PN PurePetrinet 若PN的每一库所都恰好有1个输入变迁与1个输出变迁 即 p P p p 1 则该PN称为标识图 Markedgraphs 若PN的每一变迁都恰好有1个输入库所与1个输出库所 t T t t 1 则该PN称为状态机 Statemachine 第四章离散事件仿真的逻辑分析 Petri网 若干制造系统的基本PN模型 缓冲区模型考虑两台机器M1与M2之间的缓冲区B 假设它能够存储k个工件 t1 M1结束当前工件的加工并将该工件放入B中 t2 从B中取出一个工件并在M2上开始加工 pv B的剩余容量 pb B中存放的工件数量 puf 机器M2是空闲的 当缓冲区满时 pb中容纳k个标识 而pv中无标识 此时t1被抑制而不能激发 机器M1堵塞 Blocked 一旦一个工件从缓冲区移至机器M2 pv收到1个标识 则t1立即使能 生产得以恢复 PN的抑制弧 Inhibitorarc 按输入函数的定义 pb中至少有k个标识是t1使能条件 但是 抑制弧的作用应理解为 一旦抑制弧连接的输入库所中拥有与抑制弧的权相等数量的标识 则该抑制弧将抑制该变迁的激发 抑制弧用一端带由小圆并旁注权值k的弧表示 若干制造系统的基本PN模型 存储区溢出 Overflow 当缓冲区存满工件时 其存储容量已耗尽的现象 当存储区溢出时 其前端机器被堵塞 发生溢出时 期望提供存储区溢出的信息 并改变堵塞在机器中工件的路径 将其送至其它机器 而不是原路径上的机器M2 变迁toi的激发将输出溢出指示 由于连接toi与pv的抑制弧的权为0 因此只要pv中包含1个及以上的标识 表明储料取仍然有存储空间 则toi将被抑制激发 不产生溢出指示 当p1中包含1个标识 表示1工件被机器M1加工完毕 等待从M1移出 且pv中无标识 表明缓冲区堆满工件 toi立即激发 输出溢出指示 将p1中的标识送至代表其它路径的入口 图中没有画出 而不是pb 若干制造系统的基本PN模型 FCFS的工件队列PN模型传送带是典型的先来先享受服务 First Come First Serve FCFS 工件队列的例子 因为先放置到传送带上的工件先从传送带的另一端离开 工件在传送带上传送的过程可看作是暂时储存在传输带上 ps表示工件在传送之中 ta表示将工件放入传送带上 传送带所能够传送的最多工件数由ta的抑制弧的权N定义 只要ps中的标识数不超过N 抑制弧不起作用 此时 一当工件到达 ta立即激发 将1标识放入ps中 表示工件在传送之中 只要ps中有标识 一旦pd中有1标识 表示请求将1工件从传输带上移走 则td激发 从ps中取走1标识 一工件离开传送带 若干制造系统的基本PN模型 描述制造系统的并行与同步特征PN模型制造过程中 许多操作同时进行 例如 某一部件由2个零件装配而成 2个零件分别由2条独立的生产线加工 则装配只能在每一零件加工完毕后才能进行 2个零件的加工过程是并行的 Concurrent 通过装配的开始而同步 Synchronized 左图所示的PN 假设p1中的标识表示放置在一托盘上的2个工件到达 t1表示拆卸操作 将一个工件从托盘上移走并放入p2中 如此同时将另一工件连同托盘送至p3 可以看到PN中的一个初始标识现在变为2个标识 也就是说 网中总标识数是可变的 还发现该模型中从t1分出2条不同的路径 每一路径代表一个加工过程 它们是并行的 两个过程在t3处合并从而同步 若干制造系统的基本PN模型 制造系统另一常见的现象是两个以上的操作共享同一资源 例2台机器共享一套刀具 对于资源的竞争将导致冲突 Conflict 在PN中 资源表示为库所 操作表示为变迁 因此 在PN中 资源的冲突表现为某一库所被2个及其以上变迁共享同一个输入库所 根据标识图的定义 它不能描述资源冲突 左图中2个加工过程都需要资源p4进行各自的操作 这是一典型的冲突问题 如前面刚提到 t1与t3同时使能 但只有二者其一能够激发 出现冲突时 必须作出决策一决定谁优先激发 最简单的方法是采用随机确定方法 若t1在冲突中获胜 则t1激发并消耗p4中的标识 最终 t2激发从而将1标识放回p4 表示资源得以释放 基本PN性能 系统的特性可分为行为 Behavioral 与结构 Structural 特性 行为特性是PN与初始标识有关的性能 而结构特性与初始标识无关 它们取决于PN的拓扑结构 重要的结构与行为特性 可达性 Reachability 有界性 Boundness 安全性 Safeness 守衡性 Conservativeness 活性 Liveness 可逆性 Reversibility 基本PN性能 可达性是PN的一个重要行为特性 给定一PN 我们期望知道从初始标识m0可以到达哪些标识 给定一标识mt 是否可以激发一系列变迁从初试标识m0到达该标识 定义 若从m0始标识开始激发一个变迁序列产生标识mr 则称mr是从m0可达的 若只要从m0开始激发一个变迁即可产生mr 则称mr是从m0立即可达的 Immediatelyreachable 所有从m0可达的标识的集合称为可达标识集或可达集 记为R m0 一般地 从m0到mr所激发的变迁序列表示为 sr tj1 tjr 这里j1 jr为1到m之间的整数 从m0激发sr产生mr表示为 m0 sr mr 例 在右图的PN中 m0 1 0 0 1 1 0 0 T m0 s4 m4 这里m4 0 0 1 1 0 0 1 T s4 t3 t4 t1 t2 对于每一个激发的变迁序列sr 都可以关联一个m 1激发向量vr 该向量的第i个元素 对应着变迁ti在sr中出现的次数ni 一般地 vr n1 nm T 对于一定的vr 其对应的激发的变迁序列可能不是唯一的 例如 上面例子中提到的从m0到达m4 v4 1 1 1 1 T所激发的对应变迁序列就有t3 t4 t1 t2与t1 t2 t3 t4两个 基本PN性能 可达性可描述制造系统的两个问题 1 系统按照一定的轨迹运行系统是否能够实现一定的状态 典型的问题是生产调度计划的验证 即按照一定的生产调度计划进行生产 一定的生产任务是否能够得以完成 2 要求到达一定的状态如何确定系统的运行轨迹 典型的问题是生产调度问题 第一个问题可以描述为 给定sr 初始标识m0以及期望达到的标识mr 则有m0 sr mr 若mr mr则答案是肯定的 若mr mr 则答案是否定的 第二个问题可以描述为 给定m0与mr 寻找sr 使得m0 sr mr成立 必须指出sr可能不是唯一的 通常都在一定的准则下选取优化的sr 基本PN性能 有界性与安全性 定义 给定PN P T I O m0 以及其可达集R m0 对于库所p P 若 m R m0 有m p k 则称p是k 有界的 此处k为正整数 若PN的所有库所都是k 有界的 则PN是k 有界的 特别地 k 1时 即当某库所或PN是1 有界的 则称该库所或PN是安全的 若对与任意初始标识m0 PN都是k 有界的 则PN是结构有界的 Structurallybounded 基本PN性能 意义 库所用于表示制造系统中的工件 工具 托盘以及AGV的存放区 工件的存放区就是缓冲区 还用于表示资源的可利用情况 确认这些存放区是否溢出 Overflow 或资源的容量是否溢出是非常重要的 PN的有界性是检查系统是否存在溢出的有效尺度 当库所用于描述一操作 该库所的安全性能够确保不会重复启动一正在进行的操作 我们可直观地看到 右图所示的PN是1 有界的 因此它是安全的 定义 对于一变迁t T 在任一标识m R下 若存在一变迁序列sr 该变迁序列的激发使得此变迁t使能 则称该变迁是活的 Live 若一PN的所有变迁都是活的 则该PN是活的 死变迁 Deadtransition 或者死锁 Deadlock 从反面描述PN的活性 若存在m R 不存在从m开始的变迁序列 该序列的激发使得t使能 则变迁t为死变迁 若存在m R 在此m下无任何变迁使能 则称PN包含一死锁 该标识为死标识 Deadmarking 基本PN性能 死变迁 Deadtransition 或死锁 Deadlock 基本PN性能 出现死锁的原因是不合理的资源分配策略或某些或全部资源的耗尽 在自动制造系统中 许多资源 如机器 包括AGV与机器人在内的物料搬运设备 以及缓冲区存放空间 是共享的 在这样的资源共享系统中 下列4个情况可能同时满足 从而导致锁死 互斥 一资源不可以为2个或2个以上过程同时使用 一过程排斥其它过程对于该资源的占用 占用且等待 一过程已被许可占用某一或某些资源 同时又在请求占用其它资源 无抢占 已分配给某一过程的资源不能从该过程中抢走 除非该过程使用此资源完毕后而释放 循环等待 2个或更多过程排成一个链 链上每一过程都在等待一个正在被链上下一个过程占用的资源 制造系统出现死锁的例子 柔性制造系统的某一机器入 出缓冲区占用着一托盘 其上存放着已加工完毕的零件 而另一存放待加工工件的托盘也被自动导向车 AGV 传送至该入 出缓冲区 假设入 出缓冲区只能存放一个托盘 而AGV也只能放置一个托盘 此时 存放着已加工的零件托盘不能从入 出缓冲区移至AGV上 AGV也不能进入缓冲区将其上面存放着的待加工的工件的托盘送至入 出件堆放区 缓冲区与AGV为2个资源 将托盘从缓冲区移至AGV上与将托盘从AGV上送至缓冲区为2个过程 前者占用着缓冲区而等待着AGV 而后者占用着AGV而等待缓冲区 上述4个条件同时成立 因而出现死锁 基本PN性能 可逆性 Reversibility 与主宿状态 Homestate 制造系统研究中的一个重要问题是如何使得系统自动地从差错中复原 例如 在利用机器人装配中 零件间可能无法配合 从而出现差错 我们希望在不需要人为干预的情况下 就能够从这一差错中复原 若一PN用于描述装配操作 该操作配备有可行的恢复方案 则可逆网意味着自动地从差错中复原是可能的 定义 一PN是可逆的 若对于每一标识m R m0 m0 R m 标识mr R m0 称为主宿状态 若 m R m0 mr是从m可达的 基本PN性能 由上述定义 可逆性表示初始标识m0是从所有可达标识可达的 这意味着模型可以自身初始化 它对于系统自动地从差错中恢复过来是极为重要的 因为经过有限步骤 系统将回到期望的状态 因此 若PN模型不是可逆的 则控制器应该力图使之可逆 若无法做到 则不得不认为干预 可逆性还确保系统的周期特性 例如重复制造系统 这一特性与可逆性与主宿状态密切相关 可逆行是主宿状态的特例 若mr m0 即若主宿状态为初始标识 则系统是可逆的 还必须注意 若PN包括一死锁 则它不可能是可逆的 一般地 有界性 安全性 活性 以及可逆性彼此间是独立的 一个PN可以是 活的 有界的 可逆的 活的 有界的 不可逆的 或者 不是活的 无界的 不可逆的 共有8种组合 基本PN性能 PN不是活的 是有界的 是不可逆的 基本PN性能 定义 对于一PN P T I O m0 若存在一矢量w w1 w2 wn T且wi 0 i 1 2 n 使得对于所有m R m0 wTm wTm0 则称该PN相对于矢量w守衡 若PN相对于w 1 1 1 T守衡 即对于所有m R m0 则称PN为严格守衡的 定义 对于一PN P T I O m0 若存在一矢量w w1 w2 wn T且wi 0 i 1 2 n 但w 0 使得对于所有m R m0 wTm wTm0 则称该PN相对于矢量w部分守衡 基于PN制造系统性能分析 基于可达图与覆盖图的分析 从初始标识m0开始 期望到处PN所有可能的标识 这些标识通过变迁而关联 我们将所有标识以及产生这些标识的变迁用一图形表示 图中的节点为标识 节点之间用表示变迁的带箭头的线或弧连接 带箭头的线起端所连接的标识通过由该线所代表的变迁的激发 产生该线末端所连接的标识 这样的图称为可达图 若PN是无界的或PN所描述的系统具有无限个状态 则可达图将无止境扩展 取而代之 我们将构建覆盖树 Coverabilitytree 它是无限可达图的有限表达方法 基于PN制造系统性能分析 定义 标识m2覆盖m1 即m2 m1 若 p P m2 p m1 p 移入一特别符号 它代表 准 无限大 用于表示任意大的标识数 遵循以下四个运算规则 使得对于任意正数k 都有 1 k 2 3 k 4 k 基于PN制造系统性能分析 算法 覆盖树构建方法 1 让初始标识m0为树根 并作上 new 的记号 2 若有 new 标识存在 则做以下事情 否则 若没有 new 表示 则终止 3 选择某一 new 标识m 1 若m与树中间已有的其它标识相同 则将其记为 old 然后转向其它 new 标识 2 若在m下无变迁使能 则将m记为 deadend 死点 4 对于m下使能的变迁t 做以下事情 1 激发t由m产生标识m 2 若在从树根至m 的路径上存在一标识m 使得m 覆盖m 但m m 即m m 则对于那些使m p m p 成立的p 用 取代m p 3 以m 为一节点 从m至m 画一有向线 将其并记为t 并将m 记为 new 5 除去m的 new 标志 基于PN制造系统性能分析 例 构建图 a 所示的具有无限储料空间之间缓冲区的二机器生产线的覆盖树 初始标识为m0 10010 T 在m0下只有t1使能 激发t1将产生m1 01010 T 由于m1即不大于m0又不等于m0 因此将记为 new 并从m0至m1画一有向线并记为t1 m1为当前唯一的 new 标识 在m1下只有t2使能 激发t2将产生标识m2 10110 由于m2 m0且m2 p3 m0 p3 因此 根据步骤4 2 在m2 10110 T中用 取代m p3 从而得到标识m2 10 10 T 在当前唯一的 new 标识下 t1与t3使能 激发t1将产生m3 01 10 T 它不等于从m0至m3路径上任何标识 虽然它大于m1 01010 T 但没有必要进行步骤4 2 原因是其第3个元素已经是 激发t3产生m4 10 101 T 10 01 T 根据 k 目前存在m3 01 10 T与m4 10 01 T2个 new 标识 在m3 01 10 T下 t2与t3使能 激发t2产生m5 01 110 T 01 10 T 它等于先前产生的m3 因此记为 old 激发t3产生m6 01 01 T 它是一 new 标识 目前仍然存在2个 new 标识 m3 10 01 T与m6 01 01 T 继续进行 直至无 new 标识存在 基于PN制造系统性能分析 根据上述方法 由图 b 所示的覆盖树可知 图 a 所示的PN是无界的 且除了p3其它库所是安全的 还可知该PN不包含死变迁 因为所有变迁都在树中出现 由于树中出现 我们无法作出该PN是否活的与可逆的结论 基于PN制造系统性能分析 基于覆盖树或可达树 可以做如下分析 当且仅当树中所有节点上均不出现 时 PN网是有界的 此时 我们可以在树中找出某一库所中最大的标识数 比如说k 则该库所是k 有界的 若k是树中所有库所中的最大的标识数 则PN是k 有界的 当且仅当树中所有的节点上仅包含0或1时 则PN网是安全的 没有任何死点包含 则树中死点的个数就是PN死标识的数目 若树中死点之一包含 则PN包含无数个死标识 若某变迁在树中不出现 则该变迁是死变迁 在不包含 的树中 若给定任何两个节点之间 都存在一有向路径 在该路径上所有变迁都出现 则PN是活的 在无 出现的树中 若从任何节点到根节点之间都存在一有向路径 则PN是可逆的 上述 5 仅适用于不包含 的覆盖树 即可达树的活性分析 也即有界PN的活性分析 这是因为在出现 的覆盖树中 由于 的移入而损失一些信息 有研究表明 两个不同的PNs具有相同的覆盖树 其中之一个PN是活的 而另一个不是活的 3 基于PN制造系统性能分析 定义 一PN是关于初始表示m0一致的 若其覆盖树上存在一有向回路 不必要是基本回路 所有变迁都在起上出现至少一次 若该回路 只包含某些变迁 则为部分一致的 定义 一PN是关于初始标识m0重复的 若其覆盖树上存在一有向回路 不必要是基本回路 该有向回路包含所有的变迁无数次 若该有向回路经包含某些变迁 则为部分重复的 连贯性 Consistency 与重复性 Repetitiveness 有向回路 Directedcircuit 的概念 一有向回路为从某一节点 库所或变迁 出发并返回该节点的路径 若在有向回路上除了起始节点外 其它的节点出现的次数不多于一次 则该有向回路称为基本有向回路或基本回路 基于不变量的PN分析 是一种基于矩阵线性代数 这一方法的优点是依据简单的线性代数方程 就能正规地确定PN性能 这里所建立的线性代数方程决定着由PN所描述的分布系统的动态特性 这与同自动控制理论中状态方程的概念 但其解局限于非负整数 因为它表示某一变迁激发的次数 用mk表示第k次运行 k 0 后PN的标识 一次运行就是激发一个变迁序列 它可能包括若干变迁的激发 一个变迁可能在一次运行中激发多次 则第k 1次运行后PN的表示为 mk 1 mk Cvk k 0 1 这里vk为激发记数向量 它为一 m 1 向量 其第i个元素表示在第k 1次运行中变迁ti激发了的次数 上式称为PN的状态方程 特别地 若一次运行仅包含激发某一变迁1次 即vk只有1个元素为1 而其它元素均为0 则上式将表示PN的激发规则 mk Cvk 0 对于所有k 0上式可用于检验在mk下激发某一变迁序列是否合法 基于PN制造系统性能分析 定义3 P 不变量为一 n 1 非负整数向量x 并满足 xTC 0 2 而T 不变量为 m 1 非负向量y 并满足 Cy 0 3 将 1 式两边左乘xT 得到xTmk 1 xTmk xTCvk 由 2 则有xTmk 1 xTmk k 0 4 特别地 从k 0开始递推有 xTm0 xTm1 xTm2 xTm3 xTm 常数 即xTm xTm0 常数 5 上式表明由P 不变量加权的所有库所中初始标识数之和为常量 或者说 P 不变量的非0元素是相应的库所中标识数的权值 使得在任何从m0可达的m下所有库所中的标识加权和为常数 称这些库所被该P 不变量覆盖 基于PN制造系统性能分析 假设经过激发某一变迁序列 该序列记数向量为v PN从初始标识又返回初始标识 则由 1 有 m0 m0 Cv必有Cv 0 因此 v为一T 不变量 即y v 这表明T 不变量中的非负元素为将PN的标