Flexible manufacturing system structural control and the neighborhood policy, part 1. Correctness and scalability

Structural Control Policies (SCPs) are real-time flexible manufacturing system (FMS) operating policies that guarantee deadlock-free operation. SCPs must be correct and scalable. A correct SCP guarantees deadlock-free operation whereas a scalable (polynomial) SCP remains computationally tractable as FMS size increases. The NP-completeness of state safety (is there a sequence of state transitions leading to the empty state?) implies that a correct and scalable SCP will reject some safe states. SCP efficiencyis the ratio of policy admissible space to FMS safe state space. This paper, the first of a two-part series, discusses FMS structural control and presents a correct and scalable SCP referred to as the Neighborhood Policy. SCP efficiency issues will be discussed in the second part.