Two-machine flowshop scheduling to minimize the number of tardy jobs

The authors consider the two-machine flowshop problem with the objective of minimizing the total number of tardy jobs. Since this problem is known to be strongly NP-hard, algorithms are described for four polynomially solvable special cases. In addition, several heuristic algorithms are developed to find optimal or near optimal schedules. Results of computational tests in solving problems up to 60 jobs are reported and directions for future research are provided.