Unidirectional Loop Network Layout Problem in Automated Manufacturing Systems

Autor:	Michael W. Kim, Panagiotis Kouvelis
Rok vydání:	1992
Předmět:	Mathematical optimization Identification (information) Workflow Computer science Flexible manufacturing system Decomposition method (constraint satisfaction) Management Science and Operations Research Heuristics Computer Science Applications
Zdroj:	Operations Research. 40:533-550
ISSN:	1526-5463 0030-364X
Popis:	In this paper, we address the design of unidirectional loop network layouts for automated manufacturing environments. We show that the problem is NP-complete. Using a workstation interchange argument, we develop dominance relationships for easy identification of local optimal solutions. Our results suggest the need for simple heuristics to solve the problem. We identify cases in which the heuristics perform optimally, and we analyze the worst case behavior of the heuristics. We develop an optimal branch-and-bound procedure that is computationally efficient for medium-sized problems. We also present a decomposition principle helpful for dealing with large workflow matrices. We report computational results on the heuristics and the branch-and-bound procedure. We show that one of the heuristics performs impressively well in terms of solution quality and computational time requirements.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::d23ba02ba5f1d4fa4cd6699844452054 https://doi.org/10.1287/opre.40.3.533 Zobrazit plný text záznamu Plný text ve formátu PDF