基于Petri网灵巧信标的自动制造系统死锁控制策略研究

This project aims to cope with deadlock control problems in automated manufacturing systems (AMSs). Since deadlock occurrence can make the partial or whole AMS stop and lead to heavy economic losses, deadlock control policies must be considered as an important part during AMS designing process. How to design the reasonable supervisors with liveness to eliminate deadlock problems have become the hot topics on international research during the past two decades in terms of behavioral permissiveness, structural complexity, and computational complexity. This project intends to develop optimal designing of live supervisors using the controlled smart siphons, which consists of three topics shown as follows: (1) For G-system net, definition of smart siphons that can characterize its deadlock status and the corresponding algorithm of solution and control are proposed. (2) By solving the objective parameters through linear programming problems (LPPs), economic implementation is added to the major criteria to evaluate live supervisors such that a live supervisor with low computational time, simpler structure, more behavioral permissiveness, and low implementation cost can be obtained. (3)In order to enrich the theory of siphons in Petri nets, definition of smart siphons that can characterize livelock status in ordinary or generalized Petri nets and the corresponding algorithm of solution and control are proposed as well.

本申请项目致力于自动制造系统(Automated Manufacturing System, AMS)的死锁控制问题。由于死锁的发生会导致部分或整个AMS的运行停止，可造成重大的经济损失。因此，死锁控制策略的研究是AMS设计时必须考虑的重要内容。基于行为许可性，结构复杂性和计算复杂性，设计出合理的活性Petri网控制器来消除死锁问题，是近二十年来国际上死锁问题研究的热点。本项目拟从三个方面开展基于受控灵巧信标的活性Petri网控制器设计及其优化的研究：（1）针对建模能力更强，目前研究较少G-system网，提出表征其死锁状态的灵巧信标定义，相应的求解与控制算法；（2）通过求解目标参数的线性规划问题，将经济实现性添加到活性Petri网控制器的评价指标中，获取信标计算时间少，结构简单，许可行为数多和实现代价低的活性控制器；（3）提出表征Petri网活锁状态的灵巧信标定义，相应的求解与控制算法。

AMS以多品种、小批量，经济和快速响应产品需求变化等特性，在目前的产品制造领域中占据了主导地位。而死锁问题是AMS设计时必须考虑和加以解决的。借助Petri网的建模能力强、便于分析和图形化等优点，相关学者和研究人员在AMS的建模，运行和性能评价等方面，尤其是死锁控制策略的设计取得了许多成果。本项目主要进行了导致Petri网死锁和活锁(livelock)的灵巧信标，活性Petri网控制器实现代价评估和普通Petri网的活性最大可达数(maximally reachable number, MRN)等问题的研究，相应的主要研究方法，内容及其成果如下：(1) 基于G-system网SS的迭代式求解与max’-controlled，提出的G–system网的死锁控制策略所获取的活性受控G–system网系统许可行为数目，相比已有文献中的结果，得到了进一步的提升。(2) 基于多目标参数线性规划方法，提出了对死锁预防策略(deadlock prevention policy, DCP)所构建的活性Petri网控制器实现代价的评价算法。通过表征所添加的控制库所(control place, CP)实施代价参数f1，对应的输入、输出变迁实施代价参数f2和综合满意度系数λ的求解，该算法对活性Petri网控制器给出了A级(λ>0.8)，B级(λ∈[0.5,0.8])和C级(λ<0.5)的评判，弥补了相关空白。(3) 基于Petri网的结构分析方法，提出了表征Petri网活锁状态SS的定义，相应的求解与受控算法。算例的数值验算结果表明：此算法能够迭代式求解出导致deadlock和livelock的SS，获取的活性受控Petri网系统(N*,M*)在结构复杂性与行为许可性上，比对已有文献中的结果，均得到一定程度的化简和提升，且适用于普通Petri网和一般Petri网的重要子类－S4R网。 (4) 通过对每个求解的基本信标和不满足可控条件的从属信标添加CP和控制变迁(control transition, CT)方式，提出了具有最大可达数的普通Petri网死锁控制策略。这既不同于已有文献中的仅添加CP来消除死锁的策略，而且，相应的(N*,M*)可达数目与未受控的原网(N0,M0)是相同的，即最大可达数MRN，其行为许可性达到了峰值。同时也意味着AMS共享资源可得到进一步的充分利用。