On Configuration Of The Initial Marking And Deadlock Detection For A Class Of Petri Nets

The design of models is the first step for control, validation, performance analysis, and simulation for flexible manufacturing systems (FMS). This thesis extends the liveness characterization results on a subclass of Petri nets, L-S3PR. A polynomial algorithm is developed to decide whether a more general class of Petri nets, S3PR, has potential deadlock, which can model a wide class of FMS. The concept of resource circuit and the way to find them from a net structure are proposed successively. The thesis shows the approach to obtain a minimal siphon from a resource circuit. It is also proved that if a minimal siphon derived from a resource circuit does not contain the support of any P-semiflow, it is not a potential deadlock. A minimal siphon that can be emptied is the real cause of the not-liveness in an S3PR.In addition to the net structure, the inappropriate initial marking can cause deadlock too. Setting the net to be deadlock-free by configuring the initial marking according to the constraints group is illustrated for designing and modifying the system model. It provides appropriate relations between the number of tokens in idle places and that in the resource places when dealing with S3PR (L-S3PR). As a result, without changing the structure of the system, we can quickly reconfigure the system to respond to the change of demand. The agility of FMS can be guaranteed.This thesis also proposes a correct algorithm that is used in the development of a deadlock prevention policy for a class of FMS where deadlocks are caused by unmarked siphons in their Petri net models. The algorithm is designed to derive a minimal siphon from a maximal unmarked one that can be obtained due to the mixed integer programming based deadlock detection. It is also proved the siphons that can be derived using the algorithm are minimal on the ground of siphon s'definition.