Siphons can be used to characterise deadlock states and solve deadlock problems in Petri nets that model flexible manufacturing systems. This article presents a novel deadlock prevention policy for Petri nets using siphon extraction. At each iteration, a siphon extraction algorithm finds a maximal deadly marked siphon, classifies the places in it, and decides a necessary siphon from the classified places. Accordingly, the deadlock prevention policy adds a proper control place (CP) to make each necessary siphon marked or max-controlled until the controlled system is live. By adopting the classification of places, deciding necessary siphons, and adding the proper CPs, the proposed deadlock prevention policy avoids a complete siphon enumeration, adds a small number of CPs, and leads to a liveness-enforcing supervisor with a simple structure compared with closely related approaches in the literature. Finally, a case study shows its appealing behavioural permissiveness.
6 May 2012 in Journal of Intelligent Manufacturing
This paper develops a concept of control transition equation (CTE) and the corresponding deadlock control algorithm (DCA) using control transitions (CTs) to eliminate deadlocks in Petri nets. By analysing the reachability graph (RG) of an original net with deadlocks, this DCA firstly find all deadlock markings (DMs) and then the corresponding CTs are solved on the basis of the proposed CTE. Secondly, a linear programming problem that can minimise the number of CTs is applied to these CTs. In addition, in order to furtherly simplify the structure of these CTs, the reconstruction of the necessarily added CTs is performed by a circulating sequence number method. Finally, a live controlled system with the simpler structure is obtained by adding the desired CTs to , which can reach the same number of states as the original plant model , i. e. live maximally reachable number. The proposed DCA is different from deadlock prevention policies using control places (CPs) in most existing literature and whose correctness and efficiency are verified via the theoretical analysis and the relevant several examples.
1 November 2014 in IET Control Theory & Applications
Both deadlocks and livelocks can result in the serious problems in running process of a flexible manufacturing system (FMS). This study proposes an iterative control policy for an FMS modelled with Petri nets on the basis of a combination of revised mixed integer programming and the concept of max′‐controlled siphon, which can not only solve the smart siphons associated with deadlocks and livelocks in Petri nets directly, but also make them max′‐controlled. Accordingly, an original Petri net system with deadlocks and livelocks can be turned into the live controlled one with a simple structure, and meanwhile no smart siphons can be found in it. It lays foundations for further analysis and control on deadlocks and livelocks. Compared with the existing methods in the literature, the proposed one is more general and effective. A theoretical analysis and several examples are given to demonstrate its efficiency and practical potentials.