Proportionate flow shop: New complexity results and models with due date assignment

Abstract It is known that the proportionate flow shop minimum makespan problem is solved optimally by any permutation job sequence. We show that the problem 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