Unidirectional loop network layout problems in automated manufacturing systems

In this paper, the authors address the design of unidirectional loop network layouts for automated manufacturing environments. They show that the problem is NP-complete. Using a workstation interchange argument, the authors develop dominance relationships for easy identification of local optimal solutions. The present results suggest the need for simple heuristics to solve the problem. The authors identify cases in which the heuristics perform optimally, and they analyze the worst case behavior of the heuristics. The authors develop an optimal branch-and-bound procedure that is computationally efficient for medium-sized problems. They also present a decomposition principle helpful for dealing with large workflow matrices. The authors report computational results on the heuristics and the branch-and-bound procedure. They show that one of the heuristics performs impressively well in terms of solution quality and computational time requirements.