Minimum weighted number of tardy jobs on an m-machine flow-shop with a critical machine

We study a flow-shop problem, where each of the jobs is limited to no more than two operations. One of these operations is common for all the jobs, and is performed on the same (”critical”) machine. Reflecting many applications, jobs are assumed to be processed in blocks on the critical machine. All the jobs share a common due-date, and the objective is minimum weighted number of tardy jobs. We prove that the problem is NP-hard. Then we formulate the problem as an integer program, and introduce a pseudo-polynomial dynamic programming algorithm, proving that the problem is NP-hard in the ordinary sense. We also propose an efficient heuristic, which is shown numerically to produce very close-to-optimal schedules. Finally, we show that the special case of identical weights is polynomially solvable.