Deadlock Control Algorithm Based On Selective Siphon

This thesis focuses on deadlock prevention in flexible manufacturing systems (FMS). The deadlock prevention policy based on critical markings, set covering problem and selective siphon can obtain a supervisor with small size and more permissive behavior. It integrates structural information related to minimal siphons with reachability analysis and obtains the relationship between emptiable siphons and markings, thus avoiding unnecessary control places. On the other hand, this would cause excessive computational cost since we need to enumerate all strict minimal siphons, generate all markings, and solve a set covering problem. And each of the above three problems is in theory exponential with respect to the size of a net. This study improves the policy from two aspects. Then an improved deadlock prevention policy based on selective siphons is proposed. This research is motivated to reduce the computational cost in the traditional deadlock prevention policies that are developed by selective siphons.In this research, firstly we introduce an improved algorithm for generating siphons. There exists extra computation in the siphons generation algorithm that based on the sign incidence matrix. Hence an improved method via adding criteria is derived. And the optimized scheme also makes sense for the further minimality check and the proof is given in the thesis. For the deadlock prevention, we first divide the markings into legal and forbidden ones. Then we could get the essential markings just from forbidden ones. This can greatly reduce the computational cost of emptying patterns of siphons. Finally examples are used to demonstrate the proposed methods.