Deadlock prevention, deadlock detection, and deadlock avoidance strategies are used to solve the deadlock problems of flexible manufacturing systems. The theory of regions is recognized as the unique method for obtaining maximally permissive (i.e., optimal) controllers in the existing literature. All legal and live maximal behavior of a Petri net model can be preserved by using a marking/transition-separation instance (MTSI). However, obtaining them is an extremely time consuming problem. This work proposes crucial MTSIs that allow designers to employ much fewer MTSIs to deal with deadlocks. The advantage of the proposed policy is that an optimal deadlock controller can be obtained with drastically reduced computation. Experimental results, by varying the markings of given net structures, indicate that it is the most efficient policy to obtain such controllers.

A transition-controlled deadlock detection and recovery prevention policy is presented for a subclass of Petri nets used to model flexible manufacturing systems. The subclass is called systems of simple sequential processes with resources (S ³ PR). The proposed policy is different from the standard deadlock prevention policies. Instead of adding control places, this policy adds a controlled transition to solve a group of deadlocked markings that have the same graph-based property. Finally, the results of our study indicate that the proposed policy appears to be more permissive than those existing ones that add control places.

The theory of regions has been recognised as the powerful method of deadlock prevention policy for obtaining maximally permissive controllers. It is well known that all legal and live maximal behaviour of Petri net models can be preserved by using marking/transition-separation instances (MTSIs) or event-state-separation-problem (ESSP) methods. However, they encountered great difficulties in solving all sets of inequalities that is an extremely time-consuming problem. Moreover, the number of linear programming problems (LPPs) of legal markings is also exponential with net size when a plant net grows exponentially. This work proposes a novel methodology to reduce the number of MTSIs, ESSPs and LPPs. To do so, the reachability condition equations in the theory of region can be reduced under the reduction approach. The problem of LPPs can then be reduced. Additionally, crucial marking/transition-separation instances is developed in our deadlock prevention policy that allows designers to employ few MTSIs to deal with deadlocks. The advantage of the proposed policy is that a maximally permissive controller can be obtained with drastically reduced computation. Finally, experimental results infer that our proposed policy seems to be the most efficient policy among existing methods.

Nowadays, many kinds of flexible manufacturing systems are used to process many complex manufacturing works due to their machine flexibility and routing flexibility. However, such competition (i.e. robots and machines) for shared resources by concurrent job processes can lead to the problem of a system deadlock. In existing researches, almost experts adopted place-based as controllers to solve the deadlock problems of flexible manufacturing systems whatever the concept of siphons or the reachability graph method are used. Among them, only the reachability graph ones can obtain maximally permissive live states. In this article, the authors try to propose one novel transition-based deadlock prevention concept to solve flexible manufacturing system’s deadlock problem. In addition, two algorithms are developed to support above concept. The experimental results indicate that the proposed policy not only can obtain maximally permissive controllers but also recover all original deadlock markings.

This paper focuses on solving deadlock problems of flexible manufacturing systems (FMS) based on Petri nets theory. Precisely, one novel control transition technology is developed to solve FMS deadlock problem. This new proposed technology can not only identify the maximal saturated tokens of idle places in Petri net model (PNM) but also further reserve all original reachable markings whatever they are legal or illegal ones. In other words, once the saturated number of tokens in idle places is identified, the maximal markings of system reachability graph can then be checked. Two classical S³PR (the Systems of Simple Sequential Processes with Resources) examples are used to illustrate the proposed technology. Experimental results indicate that the proposed algorithm of control transition technology seems to be the best one among all existing algorithms.