An O(n2) algorithm for the variable common due date, minimal tardy jobs bicriteria two-machine flow shop problem with ordered machines

We consider the ordinary NP- hard two-machine flow shop problem with the objective of determining simultaneously a minimal common due date and the minimal number of tardy jobs. We present an O(n2) algorithm for the problem when the machines are ordered, that is, when each job has its smaller processing time on the first (second) machine. We also discuss the applicability of the proposed algorithm to the corresponding single-objective problem in which the common due date is given.

► We consider an assignable common due date minimal number of tardy jobs problem. ► We then consider the two-machine flow shop case with ordered machines. ► We present an O(n2) algorithm for this special case. ► We also apply our algorithm to the similar problem with a given common due date.