Polynomial-complexity deadlock avoidance policies for automated manufacturing systems

Based on Petri net models, this paper addresses the deadlock avoidance problem in automated manufacturing systems. First, for manufacturing systems without center resources, it is proved that the systems have only two kinds of reachable states-safe and deadlock. An optimal or maximally permissive deadlock avoidance policy with polynomial online-computation complexity is obtained through one-step look-ahead. Then, for a general system, an auxiliary Petri net is introduced. By applying the presented design method of optimal deadlock avoidance policy to the auxiliary net, a suboptimal polynomial-complexity deadlock avoidance policy for the general system is obtained.