S4PR网的严格极小信标计算及活性控制器优化方法

摘要

柔性制造系统中，生产进程之间互相等待对方占有的资源会导致死锁，使系统性能恶化，给生产带来损失。S4PR网是一类具有良好建模能力的Petri网子类，被广泛运用于柔性制造系统建模、性能分析及死锁控制策略的研究中。基于S4PR网的柔性制造系统死锁预防策略研究成为近年来理论界关注的热点。经典的死锁预防方法需要对Petri网模型中的每一个严格极小信标添加一个控制库所和相关连接弧来实现对死锁的控制。该方法首先需要求解严格极小信标，而Petri网中信标数量的增长在理论上与网模型规模的增大呈指数关系，由此导致采用经典方法预防死锁时，面临信标计算复杂度高、死锁预防控制器结构过于复杂、行为允许度低三方面的困扰。针对这一问题，本文基于S4PR网展开了对柔性制造系统死锁预防策略的研究，具体工作和结论如下：
　　 1、提出了一种计算S4PR网中全部严格极小信标的方法。该方法首先根据资源库所之间的结构关系构建C-R图，然后通过相关计算公式、定理及算法给出由C-R图得到严格极小信标集合的具体过程。尽管在最坏情况下，该方法的计算时间复杂度是指数级的，但相比传统的遍历方法，仍具有两方面的优势：一是其计算的问题规模由网中所有的库所个数降低为网中资源库所的个数(通常情况下，资源库所个数要远少于网中全部库所的个数)；二是该方法无需对网模型进行可达性分析，从而避免了状态组合爆炸问题。实例表明，本文提出的方法在一定程度上降低了信标求解的时间复杂度，同时也为下一步进行S4PR网活性控制器的优化奠定了基础。
　　 2、提出了一种基于线性整数规划方法的活性S4PR控制器优化方法。该方法以三元组的方式定义了Petri网监控器，以及S4PR网组合冗余型监控器的概念。同时证明，在一个已对网中每一个严格极小信标均设置了监控器的活性S4PR控制器中，仅删除组合冗余型监控器的控制库所和相关连接弧，而保留它的基，那么该活性控制器仍然是活的。以这一理论为基础，本文给出了活性S4PR控制器的优化算法，该算法既简化了活性网系统的结构复杂度，又提高了网系统的行为允许度。
　　 实验结果表明，本文提出的方法在计算时间复杂度、活性控制器结构复杂度和行为允许度三个衡量Petri网死锁预防方法的重要指标上均表现良好，形成了一种有效的S4PR网死锁解决方案。