Premium
Asymptotically optimal linear time algorithms for two‐stage and three‐stage flexible flow shops
Author(s) -
Koulamas Christos,
Kyparisis George J.
Publication year - 2000
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/(sici)1520-6750(200004)47:3<259::aid-nav5>3.0.co;2-k
Subject(s) - stage (stratigraphy) , flow (mathematics) , algorithm , computer science , mathematics , mathematical optimization , geometry , biology , paleontology
We consider two‐stage and three‐stage flexible flow shops with parallel machines in each stage and the minimum makespan objective. We develop linear time algorithms for these problems with absolute worst‐case bounds either sharper or no worse than the currently available ones and we accomplish this with lower complexity algorithms. We also demonstrate the asymptotic optimality of a class of algorithms for multistage flexible flow shop problems (which includes the proposed algorithms) under certain probabilistic assumptions on the job processing times. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 259–268, 2000