A deadlock prevention approach for flexible manufacturing systems without complete siphon enumeration of their Petri net models

Siphons are very important in the analysis and control of deadlocks in a Petri net. However, it is quite time-consuming or even impossible to get the complete siphon enumeration of a Petri net. This paper focuses on the deadlock prevention problems in flexible manufacturing systems that are modeled with (SPR)-P-4, a general class of Petri nets. The analysis of (SPR)-P-4 leads us to characterize deadlock situations in terms of insufficiently marked siphons. The method proposed in this paper is an iterative approach. At each iteration, a non-max-marked siphon is computed by solving a mixed integer linear programming problem. Then the siphon is max-marked through a P-invariant by adding a monitor place. This process is carried out until no non-max-marked siphon can be found in the net. As a result all the siphons in the net are max-controlled. Then the net becomes live. Without computing all the siphons, a monitor-based liveness-enforcing Petri net supervisor can be found with more permissive behavior. A number of flexible manufacturing examples are used to demonstrate the proposed methods.