Synthesis Of Petri Nets-based Deadlock Prevention Controllers For Flexible Manufacturing Systems

Making best use of shared resources to increase the productivity is crucial to the design of flexible manufacturing systems (FMS). However, due to the inappropriate allocation of shared resources, deadlocks may occur in FMS, leading to unnecessary costs, such as long down-time and low utilization of some expensive resources. Therefore, deadlock problems in FMS have been studied by many researchers in these decades. Petri nets (PN) have been recognized as one of the most powerful tools to model discrete event dynamic systems (DEDS). Since FMS is a typical class of DEDS, more and more researchers choose PN to model and analyze FMS. The three main approaches to cope with deadlocks are deadlock detection/recovery, deadlock avoidance and deadlock prevention. Deadlock prevention has been studied more often because it carries out the computation once and off-line. Deadlock prevention policies can be evaluated with respect to their performances in terms of permissiveness, computational efficiency and structural complexity. In the Petri nets framework, based on the existing research works, several efficient deadlock prevention methods for different types of FMS are proposed in this dissertation, which are summarized as follows:(1) For a typical class of FMS, a mixed integer programming (MIP) method to directly compute essential siphons is presented. Then the traditional iterative siphon control (ISC) method is introduced and revised. Subsequently, a revised ISC deadlock prevention approach based on the sequence control of essential siphons is proposed. The proposed approach simplifies the structural complexity of the controlled system, guarantees the maximal permissiveness, and increases the computational efficiency. Besides, a polynomial-time algorithm is proposed to avoid the net transformation, which may generate some redundant controllers. From the experimental results of a benchmark example, the proposed approach can provide an optimal control solution when compared with the other existing methods.(2) For a typical class of FMS, based on the proposed essential siphons'sequence control approach, an ISC policy is proposed, which enforces the constraints on the markings of complementary sets of siphons. Based on the proposed policy, every added control place is ordinary place, which avoids net transformation. Subsequently, a revised redundancy check method is proposed; the method can minimize the size of the control subnet while increase the computational efficiency. From the experimental results of the benchmark example, the proposed policy can achieve sub-optimal permissiveness while typically use less monitors than the other highly permissive policies, and it also increase the computational efficiency.(3) The traditional buffer pre-allocation and partition policy is applied to a class of more generalized FMS. Then two subclasses of PN are defined to illustrate the extended application. Subsequently, a revised buffer partition policy is proposed for deadlock prevention. Compared with the traditional buffer partition policy, the proposed policy can achieve more permissiveness while it can be validated in more cases. Besides, the proposed policy has the advantage in robustness over the other existing methods, which can reduce the computational and hardware cost of re-design the controllers when the initial system state changes frequently.(4) Based on the concept of strict minimal siphons, a net transformation method is proposed. The method can transform a class of PN, which is defined in this paper, to a widely studied class of PN with a much smaller size. Then for a special class of FMS in which buffers are contained, a mixed deadlock prevention approach is proposed, which combines the buffer pre-allocation rule, the proposed net transformation method and the ISC approach. From the results of several typical FMS examples, the proposed approach can achieve a well tradeoff among permissiveness, computational efficiency and structural complexity.Finally, conclusions and future research studies on the design of deadlock prevention for FMS are illustrated.