This paper presents a comparison study of the computational complexity of the general job shop protocol and the flow line protocol in a flexible manufacturing system. It is shown that a certain 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. 1 Introduction In a general flexible manufacturing system (FMS) where resources are shared, a key role in part routing, job selection, and resource assignment is played by the FMS controller. Given the same resources of machines, robots, fixtures, tooling, and so on, different structures result under different routing/assignment strategies by the controller. Unstructured strategies are generally classified as the so-called job shop organization, while structured protocols ...
Abdallah, Chaouki T.; F.L. Lewis; and B.G. Horne. "On The Computational Complexity Of The Manufacturing Job Shop And Reentrant Flow Line." (2012). http://digitalrepository.unm.edu/ece_fsp/43