To read the full version of this content please select one of the options below:

On near-optimal deadlock control for a class of generalized Petri nets using reachability graph

YiFan Hou (School of Mechano-Electronic Engineering, Xidian University, Xi’an, China)
Murat Uzam (Electrical and Electronics Engineering, Meliksah University, Kayseri, Turkey)
Mi Zhao (Shihezi University, Shihezi, China)
ZhiWu Li (Xidian University, Xi’an, China)

Engineering Computations

ISSN: 0264-4401

Article publication date: 7 August 2017



Deadlock is a rather undesirable phenomenon and must be well solved in flexible manufacturing systems (FMS). This paper aims to propose a general iterative deadlock control method for a class of generalized Petri nets (GPN), namely, G-systems, which can model an FMS with assembly and disassembly operations of multiple resource acquisition. When given an uncontrolled G-system prone to deadlocks, the work focuses on the synthesis of a near-optimal, non-blocking supervisor based on reachability graph (RG) analysis.


The concept of a global idle place (GIP) for an original uncontrolled G-system is presented. To simplify the RG computation of an uncontrolled G-system, a GIP is added temporarily to the net model during monitor computation steps. Starting with one token and then by gradually increasing the number of tokens in the GIP at each iteration step, the related net system is obtained. The minimal-covered-set of all bad markings of the related net system suffering from deadlock can be identified and then removed by additional monitors through an established place-invariant control method. Consequently, all related systems are live, and the GIP is finally removed when the non-blockingness of the controlled system is achieved. Meanwhile, the redundancy of monitors is also checked.


A typical G-system example is provided to demonstrate the applicability and effectiveness of the proposed method. Experiments show that the proposed method is easy to use and provides very high behavioral permissiveness for G-system. Generally, it can achieve an optimal or a near-optimal solution of the non-blocking supervisor.


In this work, the concept of GIP for G-systems is presented for synthesis non-blocking supervisors based on RG analysis. By using GIP, an effective deadlock control method is proposed. Generally, the proposed method can achieve an optimal or a near-optimal, non-blocking supervisor for an uncontrolled G-system prone to deadlocks.



This work was supported in part by the Natural Science Foundation of China under Grant Nos. 61374068, 61403296 and 61563045 in part by the research grant of the Scientific and Technological Research Council of Turkey under the project number TüBiTAK-112M229.


Hou, Y., Uzam, M., Zhao, M. and Li, Z. (2017), "On near-optimal deadlock control for a class of generalized Petri nets using reachability graph", Engineering Computations, Vol. 34 No. 6, pp. 1896-1922.



Emerald Publishing Limited

Copyright © 2017, Emerald Publishing Limited