Minimizing the Weighted Number of Tardy jobs on a Two-Machine Flowshop

Abstract

In this paper, we describe an exact algorithm to solve the weighted number of tardy jobs two-machine flow shop scheduling problem. The algorithm uses branch-and-bound; a surrogate relaxation resulting in a multiple- choice knapsack provides the bounds. Extensive computational experiments indicate problems with 100 jobs can be solved quickly.