Design Of Petri Nets Based Supervisors For Flexible Manufacturing Systems

In flexible manufacturing systems (FMS), limited resources are used to process different types of jobs concurrently. If these resources are assigned improperly, there may be deadlocks, where each of a set of two or more jobs keeps waiting indefinitely for the other jobs in the set to release resources. A deadlock in an FMS means that the whole system or a part of it cannot evolve any more, which greatly decreases the efficiency of the system. Therefore, a deadlock in an FMS should be prevented such that the system can be more productive. As a mathematical tool, Petri nets can be used to model, analyze and control an FMS. As a structural object of Petri nets, siphons have close relation with deadlocks. Deadlocks can be eliminated by designing monitors for the siphons of a Petri net. In ordinary Petri nets, an unmarked strict minimal siphon can prevent the related transitions from firing. A siphon is controlled if it is always marked, which can be guaranteed by the property of P-invariants. In generalized Petri nets, a strict minimal siphon does not mean the occurrence of a deadlock, and a marked siphon does not mean the absence of a deadlock. Based on the concept of max-controlled siphons, a strict minimal siphon in a generalized Petri net is always overly controlled. However, according to the concept of max-controlled siphons, we cannot design a proper monitor for any strict minimal siphons in generalized Petri nets. The design of monitors can directly affect the permissive behavior of a liveness-enforcing Petri net supervisor. Behavior permissiveness is one of the most important criterion in evaluating the performance of a supervisor. The problem is deciding how to design monitors for such siphons and obtain a supervisor with more permissive behavior. This dissertation aims at designing supervisors for flexible manufacturing systems. The main results proposed in this research are as follows:1. In theory, the number of siphons in a Petri net always grows exponentially with respect to the size of the net. Hence it is difficult to compute all the siphons of a Petri net. Based on mixed integer programming (MIP), an iterative deadlock prevention policy for S4R nets is developed. For an S4R net, a non-max-marked siphon is computed by solving an MIP problem at each iteration. Then the siphon is max-controlled through a P-invariant by adding a monitor to the net. This process is carried out until no non-max-marked siphon can be found in the net. Without enumeration of all the siphons, a liveness-enforcing Petri net supervisor with more permissive behavior is derived when all the siphons in an S4R net are max-controlled. A method to remove redundant monitors is also developed. By this method, a liveness-enforcing Petri net supervisor with simple structure can be obtained.2. The concept of max'-controlled siphons in a more general form is formulated. A sufficient condition that a siphon is self-max'-controlled is derived. A self-max'-controlled siphon does not cause deadlocks any more. When all the strict minimal siphons in a WS3PR net are self-max'-controlled, the net is self-live. There is no deadlock in a self-live net. A system can be self-live if its resources are in a proper number and well distributed.3. By analyzing the structure of Petri nets, the concepts of equivalent P-invariants and net systems are developed. Two equivalent nets have the same fire sequences of transitions. We can find an equivalent WS3PR for an S3PR. All the strict minimal siphons in the WS3PR can be made self-max'-controlled by reconfiguring the weights of the arcs of the net. Then a self-live WS3PR net is obtained. From the self-live WS3PR, a liveness-enforcing Petri net supervisor for the S3PR is derived. A sufficient condition that an equivalent WS3PR of an S3PR can be made self-live is developed. By the proposed policy we can get a liveness-enforcing Petri net supervisor with less monitors than the number of resources and more permissive behavior.4. The behavior permissiveness of a liveness-enforcing Petri net supervisor depends on the monitors of the siphons. The monitors designed according to the concept of max-controlled would decrease the permissive behavior of a liveness-enforcing Petri net supervisor. Based on the concept of max'-controlled siphons, three methods on designing monitors for siphons are proposed. A proper monitor can be designed for each strict minimal siphon of a well marked S4R by the proposed methods. A deadlock prevention policy is then developed. The efficiency of the proposed methods is demonstrated from some examples.5. Not all the Petri net systems have a maximally permissive liveness-enforcing Petri net supervisor. A sufficient condition that a WS3PR net does not have a P-invariant based maximally permissive liveness-enforcing Petri net supervisor is formulated by an-alyzing the structure and states of the net. If a WS3PR net contains a strict minimal siphon that cannot be optimally controlled, the whole net does not have a liveness-enforcing Petri net supervisor with maximally permissive behavior. If a Petri net that has some legal markings and some illegal markings that can cause incompatible con-straints, it does not have a maximally permissive liveness-enforcing Petri net supervisor.