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

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.