基于Petri网的FMS建模与调度研究

论文摘要

柔性制造系统(FMS)的设计、实现过程是相当复杂的，它具有耗资大、风险大、技术密集的特点，所以需要在系统投入实施和运行之前，找到一种合适的方法对柔性制造系统进行清楚准确地建模并对其构成要素及整体静态／动态特性加以分析，这样可在设计之初发现并克服系统模型可能存在的致命错误，同时可以简化系统实时监控中的故障诊断和恢复工作。另一方面，调度和控制也是制造系统中的关键问题，在对FMS建模的基础上根据给定的一些调度和控制原则对生产的动态执行情况进行仿真，实时地输入与设备、规则有关信息，并对与系统性能有关的数据加以处理、评价，可以达到系统修正和寻优的目的。目前，由于Petri网不仅能描述资源的共享、冲突、互斥、并发和不确定性，而且能进行定量分析和定性分析，Petri网理论已成为柔性制造系统中建模与分析的主流技术之一。 本文主要研究基于Petri网的柔性制造系统的建模与调度方法，针对一些典型的具有NP难度的柔性制造系统调度问题，提出几种简单、有效、实用的基于Petri网的启发式算法。主要研究工作和取得的成果如下： (1) 开发了一个FMS的Petri网建模与调度仿真的软件平台，该平台为FMS的调度研究提供了方便的测试运行环境。软件实现了Petri网的静态和动态特性，可以很方便地调入各种FMS的Petri网输入文件，也可自动生成大量满足指定条件的测试模型，另外通过调度函数的使用就可以在其中测试不同的调度算法，使得使用者的主要精力只需集中在所要解决的问题上。 (2) 通过实验发现L1算法并不像其文献中所说的那样具有可容性，此问题在另一些文献中也被提到并作了修改，但改进算法在某些情况下仍然会抛弃掉最优路径上的一些节点，针对此问题，提出了一种采用改进的最优节点选择的方法，弥补了以前方法的不足。此外，为了提高算法的收敛速度，还提出了一种在保证结果最优的前提下采用快速收敛条件的启发式调度方法。 (3) 提出了一种在FMS系统的Petri网模型中采用A~*算法和深度优先算法(DF)相结合的混合搜索策略，并使用改进的最优节点选择规则来寻找系统的调度方案，此方法能加快算法的收敛速度的同时又能控制搜索结果的质量。 (4) 提出了一种针对较大规模FMS系统进行调度的LPS算法，这是一种非可容性算法，采用了改进的子节点处理方法、与混合派遣规则相结合的启发函数以及移动窗口等概念，有效减小了算法在可达图中寻路时对节点的搜索范围，使得对于较大规模的FMS系统算法也能很快收敛。并且通过对一组FMS问题的测试表明，该方法结果要优于其它同类算法。

论文目录

• 摘要
• Abstract
• 目录
• 图清单
• 表清单
• 1 绪论
• 1.1 所研究问题及其理论意义和实用价值
• 1.2 FMS的Petri网方法及其国内外研究概况
• 1.3 本文所要解决的问题
• 1.4 课题来源
• 1.5 本文结构
• 1.6 本文的主要工作及创新点
• 2 柔性制造系统和Petri网
• 2.1 引言
• 2.2 离散事件动态系统概述
• 2.2.1 DEDS的特征
• 2.2.2 各种DEDS理论方法简介
• 2.2.2.1 形式语言与自动机
• 2.2.2.2 极大-加法代数
• 2.2.2.3 排队论
• 2.2.2.4 马尔科夫链
• 2.2.2.5 摄动分析
• 2.2.3 Petri网
• 2.3 Petri网定义及其特性
• 2.3.1 Petri网的定义
• 2.3.2 Petri网的运行规则
• 2.3.3 基本性能
• 2.3.3.1 可达性
• 2.3.3.2 有界性与安全性
• 2.3.3.3 活性
• 2.3.3.4 可逆性
• 2.3.4 Petri网的可达图
• 2.3.5 赋时Petri网
• 2.4 柔性制造系统的DEDS建模
• 2.4.1 柔性制造系统的特点
• 2.4.2 Petri网在柔性制造系统中的应用概况
• 2.5 本章小结
• 3 基于Petri网的FMS系统建模
• 3.1 引言
• 3.2 FMS系统的Petri网模型的构建
• 3.2.1 FMS系统的Petri网模型定义
• 3.2.2 自顶向下的Petri网建模
• 3.3 Petri网模型的运行和演算规则
• 3.3.1 模型运行的状态方程
• 3.3.2 模型演算示例
• 3.3.3 派遣规则
• 3.3.4 剩余工作时间RWT
• 3.3.5 最小资源时间RST
• 3.3.6 随机测试问题的构建
• 3.4 仿真软件的实现
• 3.4.1 基本数据结构
• 3.4.2 软件运行函数描述
• 3.4.3 Petri网模型在软件中的使用
• 3.4.4 软件的输出形式
• 3.5 本章小结
• *方法的FMS调度'>4 改进A^*方法的FMS调度
• 4.1 引言
• 4.2 已有方法的缺陷
• 4.3 改进方法一
• 4.3.1 改进的调度算法
• 4.3.2 调度实例
• 4.3.3 可容性启发函数及其计算示例
• 4.3.4 实例分析
• 4.4 改进方法二
• 4.5 仿真实验
• 4.5.1 1000组测试问题的选取
• 4.5.2 算法性能的比较
• 4.6 本章小结
• 5 基于混合启发式算法的FMS调度
• 5.1 引言
• 5.2 已有方法的比较
• *算法和DF算法'>5.2.1 A^*算法和DF算法
• 5.2.2 实例分析
• 5.3 混合启发式搜索算法
• 5.3.1 算法描述及其特点
• 5.3.2 算法特性与证明
• 5.3.3 仿真运算
• 5.3 对复杂FMS系统的仿真测试
• 5.4 本章小结
• 6 较大规模的FMS系统调度方法研究
• 6.1 引言
• 6.2 问题的背景
• 6.2 LPS算法
• *算法子节点处理方法'>6.3.1 改进的A^*算法子节点处理方法
• 6.3.2 与派遣规则相结合的启发函数
• 6.3.3 移动窗口法
• 6.3.4 LPS算法的步骤
• 6.4 与其它方法的比较
• 6.5 本章小结
• 7 结论与展望
• 7.1 全文总结
• 7.2 进一步的研究工作
• 致谢
• 参考文献
• 附录 10×10测试问题的Petri网输入文件
• 攻读博士期间发表或已录用的论文与参加科研情况