Minimizing the weighted number of tardy jobs on a two-machine flow shop
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. Scope and purpose In many industrial sectors, satisfying due dates is a critical issue. Thus, lateness-related measures such as the (weighted) number of tardy jobs are relevant performance measures of schedules in these industries. Our paper studies the weighted number of tardy jobs two-machine flow shop problem, and proposes an exact algorithm that solves large problems.
scheduling surrogate relaxation combinatorial optimization branch-and-bound