Flow shop scheduling with two distinct job due dates

We consider flow shop scheduling problems with two distinct job due dates. Motivated by the NP-hardness of these problems with arbitrary job processing times, we focus on their solvability with ordered or proportionate job processing times. We show that the proportionate flow shop problem with variable machine speeds remains NP-hard. We then show that the no-wait problem with ordered jobs and a maximal last machine is solvable in O(n(2)) time. We also show that the corresponding problem with the minimum number of tardy jobs objective is solvable in O(n(4)) time. Finally, we consider hierarchical bi-criteria proportionate flow shop scheduling problems with two distinct due dates and the primary objective of minimizing the number of tardy jobs. We show that these problems are solvable in O(n(3)) time when the secondary objective is the minimization of either total tardiness or maximum tardiness.

Automated summary

This paper investigates flow shop scheduling problems with two distinct job due dates and explores their solvability under different job processing times. The study provides algorithms and time complexities for these problems. Moreover, it offers solutions and time complexities for hierarchical bi-criteria proportionate flow shop scheduling problems.