Minimizing tardy jobs in a flowshop with common due date

This paper considers the two-machine flowshop scheduling problem where the total time for which a shop is available to complete a given number of jobs is constrained to a known number. This problem is equivalent to the flowshop scheduling problem to minimize the total number of tardy jobs against a common due date. It has been recently proven to be NP-hard in the ordinary sense. A compact multidimensional knapsack problem formulation of the problem is introduced together with several structural properties. A branch and bound procedure is proposed to find an optimal solution to the problem. Computational results show that the proposed algorithm is capable of finding optimal solutions to problems with up to 900 jobs.