This paper presents a comparison study of the computational complexity of the general job shop protocol and the more structured flow line protocol in a flexible manufacturing system. It is shown that the representative problem of finding resource invariants is NP-complete in the case of the job shop, while in the flow line case it admits a closed form solution. The importance of correctly selecting part flow and job routing protocols in flexible manufacturing systems to reduce complexity is thereby conclusively demonstrated.
IEEE Transactions on Systems
Computational complexity, Control systems, Flexible manufacturing systems
Abdallah, Chaouki T.; F. L. Lewis; and B. G. Horne. "Computational complexity of determining resource loops in re-entrant flow lines." IEEE Transactions on Systems (2000): 222-229. doi:10.1109/3468.833105.