基于MIP算法的系统Petri网模型中的死锁预防

摘要

自然世界及工程实际中的许多现象都可以归结为离散事件动态系统(DEDS),这些系统无一例外的要求具有无阻塞性,及系统运行无死锁.科学界针对这一问题提出了许多先进的控制理论及方法,其中Petri网由于具有离散性,并发性,随机性,可以较好的描述此类系统而得到了广泛应用.传统的基于Petri网的死锁预防策略一般遵循控制系统Petri网模型中的所有严格极小信标被清空从而达到控制整个系统使之无死锁的这一基本思想.然而,由于系统Petri网模型中的信标的个数随着网规模呈指数增长,基于这一思想的控制策略往往不可行.一种基于基本信标的死锁预防策略应运而生,该理论指出只要网系统的基本信标得到控制,其他的严格极小信标也随之得到控制,而且与严格极小信标不同的是,基本信标的个数是强受限于网系统的规模的.本文在此研究的基础上,论证了网系统中的基本信标的不唯一性,控制不同的基本信标可以得到不同的控制效果,进而提出了最优基本信标的概念并给出了相应的计算方法,应用这一计算方法可以在多项式时间内求得一组最优基本信标,也就是说,控制该组基本信标相对于其他的基本信标可以使得系统Petri网模型具有最多的可达状态,这在实际中,意味着系统具有更大的灵活性.但是上述理论虽然只需要控制基本信标即可以控制整个系统,但是由于从属信标满足一定的可控性条件才能完全受控,这意味着在控制算法的生成过程中所有的信标都要参与,从而大大增加了系统控制的复杂性.本文在基本信标理论基础上,提出了一种基于MIP算法的死锁预防策略,该策略指出了一种思路,可以控制基本信标,而后利用MIP算法给出的系统无死锁条件作为目标函数,可以在多项式时间内计算出使得所有的从属信标受控系统需满足的条件,从而使得整个系统的控制策略更加可行.

目录

文摘

英文文摘

创新性声明及关于论文使用授权的说明

第一章绪论

1.1研究背景与意义

1.2本文完成的主要工作

第二章Petri网理论

2.1基本定义

2.2基本性质

第三章基于Petri网的系统建模与分析

3.1基于Petri网的系统建模

3.2基于Petri网的系统分析

第四章常用Petri网网络模型

4.1 S3PR

4.2 RCN合并网

4.3 AC网

4.4 FC网

第五章Petri网中的基本信标

5.1 Petri网中的基本信标与从属信标

5.2基于基本信标的死锁预防策略

第六章基本信标计算方法Ⅰ

第七章基本信标计算方法Ⅱ

7.1弱从属信标存在的必要条件

7.2算法的时间复杂性验证

7.3实例

第八章MIP(混合整数规划法)算法

8.1死锁检测

8.2混合整数规划法

第九章基于MIP算法的Petri网活性检验

9.1 MIP算法在AC，FC网系统中的应用

9.2 MIP算法在S3pR网系统中的应用

第十章 基于MIP算法的Petri网中的死锁预防策略Ⅰ

第十一章基于MIP算法的Petri网中的死锁预防策略Ⅱ

第十二章基于MIP算法的Petri网中的死锁预防策略在FMS的应用

结束语

致谢

参考文献

在读期间研究成果