In: IEEE Trans. on Robotics and Automation, Vol. 10, No. 2, pages 196-209. 1994.
Abstract: This paper develops a new method for synthesizing deadlock avoidance controllers (DACs) that realize job and machine dispatching policies of a flexible manufacturing systems (FMS) into deadlock-free control actions. Such controllers not only keep the FMS capable of repeating any of its operations, i.e., live, but also achieve a high resource utilization under any given dispatching policy. The proposed methodology is based on an untimed Petri net formalism. It consists of four ingredients: (i) a bottom up approach for synthesizing a controlled production Petri net (CPPN) model of a FMS, (2) a necessary and sufficient liveness condition based on decomposition of the CPPN into controlled production subnets and the concept of minimal resource requirements, (3) a sufficient procedure to test whether the liveness condition is kept after a control action is executed, and (4) an algorithm that combines the test procedure with the given dispatching policy to generate valid and utilization maximizing control actions. The method is of polynomial time complexity and its results are in a much larger class of controls than that of an existing deadlock avoidance scheme.
Keywords: Petri nets, controller synthesis, deadlock avoidance, manufacturing systems.