基于混合整数规划的S4PR网死锁预防控制器设计

摘要

柔性制造系统是一种典型的资源分配型系统。并发运行的生产流程会竞争有限的生产资源，一旦某些流程占有了一部分资源，并开始互相等待其他流程所占有的资源，则会导致死锁，使生产系统进入停滞，带来损失。Petri网是一类主要的对资源分配型系统进行建模的数学工具，其中，S4PR网以其良好的建模能力和适中的分析难度的优势，在近年来被广泛应用于死锁预防策略的研究中。在死锁预防策略中，经典的基于信标控制的控制器设计方法通常根据适用于S4PR网的信标最大受控条件，通过一系列的繁杂步骤来构造P-不变量，进而得到控制器的结构。然而我们发现，基于现有的控制器设计方法，在某些结构下并不能设计出满足S4PR网信标最大受控条件的控制器。并且，这类设计方法通常不考虑不可观、不可控变迁的存在。针对这些问题，本文基于S4PR网对基于信标控制的控制器设计方法展开了研究，完成的工作主要有:
　　(1)改进了现有的基于S4PR网的信标受控条件，降低了对需要构造的P-不变量的限制，使其能应用于任意结构的S4PR网。在此基础上，提出了一种利用求解MIP优化问题来构造P-不变量进而设计控制器的方法。该方法将改进的信标受控条件以及控制器结构特点转化为优化约束条件，并将优化目标函数设定为控制区域的最小化，以保留最高的行为允许度。与经典方法相比，该方法保留了计算效率高、所设计的控制器结构简单的优点。由于采用了MIP技术，该方法避免了由网结构分析而导致的繁琐的P-不变量构造，并且能够适用于存在不可观变迁的系统。
　　(2)在完成工作(1)的基础上，对该控制器设计方法进行了改进。由于该方法为了避免产生由控制器诱发的新非最大受控信标，在设计控制器的过程中要求控制器的输出弧指向源变迁，而不必要地禁止了许多合法状态。因此，本文又提出了一种二段式的控制器设计方法，同样利用求解MIP优化问题来实现。在第一阶段，控制器只监控信标的补集库所来使其最大受控;若此时产生了包含该控制器的死标识信标，则由第二阶段通过将新信标的补集库所也纳入监控范围的方式对已设计的控制器进行再次设计，直到控制器不再诱发新的死标识信标。与现有的二段式控制器设计方法相比，本文提出的方法具有控制器结构简单、调整更精确的优点，并且能比现有方法获得更高的行为允许度。
　　实验结果表明，本文提出的两种方法确实能够适用于经典方法不适用的网结构，在保留了计算效率高、结构简单的优点的同时，在行为允许度上也有不同程度的提高，在这三个衡量Petri网死锁预防策略性能的重要指标上均有良好表现。

目录

声明

致谢

摘要

1 绪论

1．1 本文的研究背景及意义

1．2 国内外研究现状

1．3 本文的研究内容和组织结构

2 Petri网基础理论

2．1 Petri网的基本概念

2．2 S4PR网的定义及性质

2．3 本章小结

3 基于MIP的死锁预防控制器设计方法

3．1 基于S4PR网的改进型信标最大受控条件

3．2 基于MIP优化的控制器设计方法

3．3 死锁预防策略算法

3．4 应用实例

3．5 本章小结

4 二段式死锁预防控制器设计方法

4．1 控制器设计方法

4．2 死锁预防策略算法

4．3 应用实例

4．4 本章小结

5 总结与展望

5．1 总结

5．2 展望

参考文献

附录1 定义3．1的MIP优化问题代码

附录2 定义4．1的MIP优化问题代码

附录3 定义4．2的MIP优化问题代码

作者简历及攻硕期间取得的成果