Integrating flexible routing and algebraic deadlock avoidance policies in automated manufacturing systems

Deadlock avoidance policies guarantee deadlock free buffer space allocation to concurrent computing parts in flexible manufacturing systems. Typically, these policies require enumeration of the routes that parts follow. In systems with flexible routing, where parts can choose from a set of machines at each processing step, route enumeration can be of exponential complexity. Set-up and execution of deadlock avoidance constraints are rendered computationally intractable. The objective of this work is to develop a control model that allows for several processing alternatives at each step while maintaining deadlock free operation and avoiding complete route enumeration.