Flexible routing and deadlock avoidance in automated manufacturing systems

Deadlock avoidance policies guarantee deadlock free buffer space allocation to concurrent competing parts in flexible manufacturing systems. Typically, these policies require enumeration of 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. Setup 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 polynomial bounds on deadlock-free operation