A correct and scalable deadlock avoidance policy for flexible manufacturing systems

Configuration flexibility and deadlock-free operation are two essential properties of control systems for highly automated flexible manufacturing systems. Configuration flexibility, the ability to quickly modify manufacturing system components and their logical relationships, requires automatic generation of control executables from high level system specifications. These control executables must guarantee deadlock-free operation. The resource order policy is a configurable controller that provides the deadlock-free guarantee for buffer space allocation. It uses a total ordering of system machines and routing information to generate a set of configuration specific linear constraints. These constraints encode the system state along,vith a buffer capacity function and define a deadlock-free region of operation. Constraint generation and execution are of polynomial complexity.