基于线性规划的Petri网结构分析

论文摘要

柔性制造系统（FMS）通过资源共享的方式生产加工出各种各样的产品,基于对有限资源的竞争,死锁现象可能会出现在FMS中。如果死锁发生,就会导致系统被阻塞,系统的效率和生产力就会降低。因此,在FMS系统的设计与控制过程中,必须考虑死锁问题。Petri网是一种适合对FMS系统进行建模和仿真控制的工具。基于结构分析在FMS的死锁控制中起着重要的作用。Petri网结构中,信标和资源环是两种特殊的结构,它们和死锁有很强关联。理论上信标和资源环的数量与Petri网规模呈指数增长。有效地计算Petri网中全部的极小信标与资源环成为科研工作亟需解决的问题。本文提出了一种利用整数线性规划计算一般Petri网模型中全部极小信标以及全部资源环的方法。基于可达图的Petri网分析方法一般能够实现死锁的最优控制,但需要计算网模型的全部可达状态,该方法受状态爆炸问题的制约。基于避免计算Petri网全部可达状态,结合信标与可达图理论,本文提出一种只搜索部分可达图就能得到Petri网死区标识集（DZ）的策略。本文主要研究内容如下:1、本文提出了一种利用整数线性规划计算一般Petri网模型中全部极小信标和全部资源环的方法。根据信标与资源环的定义,我们针对每个库所来设计满足信标和资源环的约束条件。通过总结全部库所的约束条件,制定出计算极小信标和资源环的算法。然后,向原有的算法添加新的约束来排除已经得到的信标和资源环。直到计算出所有极小信标和所有资源环,计算过程才会结束。2、结合分支定界法以及整数线性规划,本文提出一种求解死标识的方法,接着提出一种计算普通Petri网死区标识集（DZ）的策略。该策略将信标理论和可达图分析相结合,根据死标识集计算出模型的死区标识集。本文提出的策略只搜索部分可达图,成功避免计算系统的全部可达状态,因此适用于大规模的系统死锁控制研究。3、首先由死区标识集（DZ）可以计算出模型的首遇坏标识集合（FBMs）。然后,采用集合覆盖方法处理FBMs得到首遇坏标识集的极小覆盖集(（44）*FBM),实验结果表明该方法可以得到与传统方法相同的极小覆盖集。

论文目录

• 摘要
• ABSTRACT
• 符号对照表
• 缩略语对照表
• 第一章 绪论
•   1.1 论文研究背景和意义
•   1.2 国内外研究现状
•   1.3 论文研究内容及组织结构
• 第二章 Petri网基本理论
•   2.1 基本定义
•   2.2 结构分析
•   2.3 可达图
•   2.4 小结
• 第三章 基于线性规划求解极小信标和资源环
•   3.1 求解Petri网极小信标算法
•     3.1.1 LPMS的设计原理
•     3.1.2 算例
•     3.1.3 实验结果与分析
•   3.2 求解Petri网环路算法
•     3.2.1 算法LPC0设计原理
•     3.2.2 算法LPC1设计原理
•     3.2.3 算例
•     3.2.4 实验结果与分析
•   3.3 求解Petri网资源环算法
•     3.3.1 算法LPCS设计原理
•     3.3.2 算例
•     3.3.3 实验结果与分析
•   3.4 小结
• 第四章 计算Petri网模型中的死区标识
•   4.1 FDM算法设计原理
•     4.1.1 FDM算法基本思想
•     4.1.2 FDM算法流程
•     4.1.3 FDM算法内容
•   4.2 算例
•   4.3 实验结果与分析
•     4.3.1 实验数据
•     4.3.2 实验结论
•   4.4 小结
• 第五章 总结和展望
•   5.1 总结
•   5.2 展望
• 参考文献
• 致谢
• 作者简介

文章来源

类型: 硕士论文

作者: 杨少华

导师: 陈玉峰,吴启俊

关键词: 整数线性规划,结构分析,约束条件,可达标识

来源: 西安电子科技大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机软件及计算机应用

单位: 西安电子科技大学

分类号: TP301.1;O221.1

DOI: 10.27389/d.cnki.gxadu.2019.001953

总页数: 80

文件大小: 2963K

下载量: 84