Premium
Proportionate flow shop: New complexity results and models with due date assignment
Author(s) -
Panwalkar S.S.,
Koulamas Christos
Publication year - 2015
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/nav.21615
Subject(s) - flow shop scheduling , permutation (music) , job shop scheduling , flow (mathematics) , mathematical optimization , class (philosophy) , sequence (biology) , computer science , mathematics , routing (electronic design automation) , artificial intelligence , computer network , physics , geometry , biology , acoustics , genetics
It is known that the proportionate flow shop minimum makespan F m / p r p t / C maxproblem is solved optimally by any permutation job sequence. We show that the F m / p r p t / C maxproblem is at least ordinary NP‐hard when missing operations are allowed and present some solvable cases. We then consider the standard proportionate flow shop problem (with no missing operations) and show that the solution algorithms for a class of single‐machine due date assignment problems can be extended/generalized to the corresponding proportionate flow shop problems. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 98–106, 2015