Deadlock avoidance algorithm for flexible manufacturing systems by calculating effective free space of circuits

Modern flexible manufacturing systems (FMS) are highly automated and flexible in which raw parts of various types are processed concurrently. Deadlock issue arises easily in these systems due to shared equipment usage and high production flexibility. This paper presents a deadlock avoidance algorithm for FMS with free choices in part routing by calculation of effective free space of circuits of the digraph model. The algorithm is highly permissive since the effective free space calculation captures more parts flow dynamics, especially when there exist multiple knots in the digraph model. It runs in polynomial time once the set of circuits is computed offline. Simulation results are provided.