Development of Critical-Siphon Theory to Fastest Deadlock Controller for Flexible Manufacturing Systems and Computer-Integrated Manufacturing

National Chengchi University, Management Information System Department, 11605 Taipei City, Taiwan

Abstract

Since decades, Flexible Manufacturing System (FMS) is a significant part of automated production and manufacturing. In the development of FMS, deadlock prevention becomes a crucial point. This paper present a critical-siphon theory to demonstrate exactly one monitor for quality FMS is required for the set of siphons in the family of a 2-compound siphons and how to assign its initial markings. The theory is aiming to avoid redundant monitors in FMS and the unnecessary associated computational burden so that the quality of a class of Flexible Manufacturing Systems can be assured latest in the run-time. Neither reachability graph nor minimal siphon needs to be computed achieving polynomial complexity- essential for large systems. This paper redevelops the theory more formally and further applies this approach to two well-known S³PR to obtain a controller full or near maximally permissive in the context of deadlock resolution and Quality Assurance. This paper further categorizes mixture siphons into partial and full ones and the sequence among them to add monitors associated with one or different 2-compound siphons. As a result, there is no need to enumerate all siphons and the time complexity involved is polynomial. This is the first of its kind of works among all current results on the benchmark.