第四章 制造系统建模方法
另外，也可以根据系统实际，制定控制系统运行的 调度规则，合理地安排系统的活动次序，提高系统 的运行效率。下面以图4-6所示的ACD为例，分析 规则在系统仿真中的作用。
第四章 制造系统建模方法
另外，也可以根据系统实际，制定控制系统运行的 调度规则，合理地安排系统的活动次序，提高系统 的运行效率。以图4-6为例，调度规则作用。
一般地，系统状态随着系统规模按指数方式增加， 存在“状态爆炸”问题，由此导致模型求解时计 算量的急剧增加，给模型的求解带来困难。
第四章 制造系统建模方法
根据建模手段和目标，可以将DEDS模型分为三 个层次： • 逻辑层次 • 代数层次 • 统计性能层次。
第四章 制造系统建模方法
逻辑层次：分析和研究事件与系统状态的对应 关系。 主要数学工具：形式语言／有限自动机、活动 循环图法、Petri网、马尔可夫链（Markov chain）等。 代数层次：研究DEDS的代数特性和运动过程。 主要数学工具：极大极小代数等
第四章 制造系统建模方法
ACD法有直观、形象等优点，但也有明显的缺点： ①当系统结构复杂、实体数量多时，活动循环图将十 分复杂，给建模与分析等带来困难。 ②ACD法只能描述系统的稳态特征，而不研究系统 的瞬态（如动作的开始、结束等）。 ③ACD法缺乏定量的分析工具。 上述缺点限制了ACD法的推广。
第四章 制造系统建模方法
4.1系统建模方法概述 连续系统可以借助相关数学理论，对系统加以描述和求解。 离散事件系统研究最早以排队现象和排队网络为对象。 上世纪70年代前后，FMS、大规模计算机、网络通信、机场调度等复杂离散
事件系统的相继出现，推动了离散事件动态系统（DEDS )理论的形成和发展。
第四章 制造系统建模方法
第四章 制造系统建模方法
(3)队列（queue)。队列用来表示实体处于静止 或等待状态。
一般，队列用圆圈来表示，并在圆圈中注明队 列的性质。
(4）实体的行为模式：在ACD模型中，实体行为 始终遵循“…→活动→队列→活动→ …”的交替变化 规则，称为实体的行为模式。
第四章 制造系统建模方法
(5)直联活动和虚拟队列 如某一活动完成后，其后续活动就立即开始， 则称后续活动为直联活动。 为遵循实体的行为模式（状态交替变化），在这 两个活动之间插入一个等待时间为零的队列，这 种队列称为虚拟队列。
第四章 制造系统建模方法 完成各实体活动循环图之后，可将活动循环图集 成起来，构成活动循环图。D表示持续时间。
图4.3 机械加工系统的活动循环图
第四章 制造系统建模方法
系统中的实体之间存在合作关系。 合作活动：只有当参与合作活动的实体都在该活动的 前置队列存在时。
如“安装”是机床和工人的合作活动：要同时有工 人在“等待” 状态和机床处于“空闲”状态。
在绘制活动循环图时，可将实体按照某种行为特征 加以分类。
例如，将机床分为“加工”与“空闲”状态，工 人分为“工作”与“等待”状态等。
另外，还可以对同类型的实体进行分类，如将机 床分为“铣床”与“车床”，工人分为“操作工” 和“维修工”等。
第四章 制造系统建模方法
ACD法常用术语有： （1)实体（entity )。实体是指组成系统的各种要素，
它是ACD中产生活动的主体。 例如，FMS中的机床、工件、托盘、小车、机械
手等。 可用文字说明或不同线型表示不同的实体。 实体数量可在实体名称后用圆括号加数字说明。
第四章 制造系统建模方法
（2)活动（activity)。活动表示实体正处于某 种动作状态。
一般用矩形框表示。 活动名称用文字标注在矩形框中。 活动持续时间（也称活动周期），可标注在 活动的矩形框下方。
第四章 制造系统建模方法
ACD模型通过定义活动的优先权（priority）和制定 活动的规则（rule）等方法加以解决此类问题。 优先权方法：根据活动的重要性给活动分配不同的 级别，当两个活动可以同时发生时，优先级高的活 动优先安排。
对于多数机械加工系统，“安装”活动的优先级应 高于“休息”活动的优先级。
第四章 制造系统建模方法
4.3马尔可夫过程 马尔可夫过程（Markov process）是研究离散事件 动态系统状态空间的重要方法，它的数学基础是随机 过程理论。如果一个随机过程的概率分布函数具有如 下特性:
第四章 制造系统建模方法
马尔可夫特性：当给定t时刻随机过程的状态为 Xn，则该过程的后续状态及其出现的概率与t之 前的历史无关。即，过程当前的状态包括了过 程所有的历史信息，而与当前状态之前的历史 无关，这种性质也称作无后效性或无记忆性 （memoryless）。
p、q就是状态转移的概率
第四章 制造系统建模方法
也可采用状态转移率矩阵来描述
第四章 制造系统建模方法
系统经过多次转移后，通常会达到一个与时 间无关的稳定状态。即各状态逗留的概率不 再发生变化。
求解系统处于各种状态的稳态概率是研究离 散事件系统特性的重要手段。系统各状态稳 定概率通常有以下两种解法：
第四章 制造系统建模方法
（6）合作活动 如果一个活动要求有多于一个（或一类）的实体 参加才能开始，则称这种活动为合作活动。
第四章 制造系统建模方法
例：某机械加工系统 两个实体：一台半自动机床和一个操作工人。 工人：安装工件和取下工件。 工件安装完毕后，机床自动完成工件加工。 加工完毕，机床停止，直到工人安装一个新的工 件，再开始下一个加工循环。
第四章 制造系统建模方法
对于连续型随机变量X，满足无记忆特性的概 率分布函数为：
第四章 制造系统建模方法
离散状态空间的马尔可夫过程也称为马尔可夫 链（Markov Chain，MC）。对于离散时间马 尔可夫链（DTMC），驻留时间必定是满足几 何分布的随机变量。以s表示随机过程在一个状 态i的驻留时间，则有：
第四章 制造系统建模方法
对于复杂离散事件系统，为降低建模和分析的难 度，通常将系统分解为若干既相对独立又相互作 用的子系统。
在完成局部和低层次系统建模的基础上，再构建 整个系统模型。
如进销存系统： 采购子系统、销售子系统和库存管理子系统。
第四章 制造系统建模方法
⑤存在状态爆炸性和计算可行性问题。 离散事件系统的状态数量与系统变量之间呈排列 组合的关系。
因此，在ACD建模时，需要考虑实体的到达活 动，即实体从系统外越过边界进人系统的活动。
第四章 制造系统建模方法
4.2.3 ACD模型的仿真运行 ACD模型反映了系统中的实体及其所具有的活动。 ACD模型如何运行？ 以图4-5中的工人而言，系统运行时他将面临“活 动选择”问题，即当某一时刻“安装”和“休息” 两个活动都可以开始时，究竟应该选择哪一个活动 作为下一个活动？
第四章 制造系统建模方法
状态驻留时间是检验随机过程是否属于马尔 可夫过程的重要标志。
可采用以下几种方法：①检查一个随机过程 是否满足马尔可夫特性。 ②状态驻留时间分布是否是无记忆的。③过程 从一个状态到另一个状态的概率是否仅依赖于 要离开的状态和目的状态。
第四章 制造系统建模方法 马尔可夫模型常使用状态转移图来描述系统的运行情 况。 图4-7为一个可修复系统的状态转移图，系统存在 “正常（S)”和“故障（F)”两种状态。
第四章 制造系统建模方法
当机床的前置队列为“空闲”时（表示系统中有机 床可以利用），工人将先进行“安装”活动。
只有在“安装”活动不能进行且符合“休息”活动 的时间安排时，工人才能“休息”。
如果“休息”活动的级别比“安装”活动的级别高， 可能会因工人的“休息”活动而使得机床处于“空 闲”状态，影响系统的效率。
第四章 制造系统建模方法
统计性能层次：研究随机条件下DEDS的统计 性能特性及其优化问题。 主要建模工具：排队论、库存模型、摄动分析 法、半马尔可夫离散事件动态系统是一门处于发展中的学科。 目前还没有形成统一的和具有普适性的建模理论 与方法。 本章以制造系统为主要建模对象，介绍几种体系 较完整且得到较多工程应用的离散事件系统建模 方法。
DEDS系统的特征： ①离散事件是构成系统的基本要素，也是导致系统状 态演变并触发新的事件的基本原因。 ②离散事件发生的时刻受系统结构、参数、状态以及 环境的共同影响，具有随机性和不确定性，使得系统 状态的变化也具有不确定性。
第四章 制造系统建模方法
③研究DEDS的过程就是分析因离散事件发生而 导致的系统状态演变的过程，研究的目标包括： 控制不期望事件的发生，使事件按预定的时刻或 顺序发生。 ④DEDS的运行和控制多基于人为的运行规则或 决策逻辑，而不是物理学定律。
第四章 制造系统建模方法
该机械加工系统由三台半自动机床（图中以①、②、 ③表示）和一个工人组成，初始时三台机床均处于 “空闲”状态，工人处于“等待”状态。
若三台机床“加工”活动和“安装”活动的周期各 不相等，工人应该先为哪一台机床提供“安装”服务？ “加工”周期最长或最短？ “安装”周期最长或最短？
如果只满足其中一个条件，则另一个实体将在队列 中等待，从而造成设备和资源闲置、系统性能下降。
第四章 制造系统建模方法
当一个活动开始时，相应的实体从前置队列（静止 状态）中移至该活动状态。
在ACD图中，令牌（token）表示实体当前的状态。 当活动结束时，令牌从该活动移人相关的后续队列。 一个活动完成后，实体被释放，从而为后续活动创 造条件。
第四章 制造系统建模方法
图4.1机床的活动循环图
4.2工人的活动循环图
第四章 制造系统建模方法
ACD模型是按照实体类型建立的，与同类型实体的数 量无关。
即使系统中的实体类型和活动周期不同，只要系统的 行为模式相同，也可以用同一个ACD图加以描述。
第四章 制造系统建模方法 为了表示不同类型的实体数量，可在各实体名 称后面括号中的数字表示，缺省值为1。