A branch-and-check algorithm for minimizing the sum of the weights of the late jobs on a single machine with release dates

In this paper we consider the scheduling problem of minimizing the sum of the weights of the late jobs on a single machine (1|rj| [sum] wj Uj ). A branch-and-check algorithm is proposed, where a relaxed integer programming formulation is solved by branch-and-bound and infeasible solutions are cut off using unfeasibility cuts. We suggest two ways to generate cuts. First we show how the algorithm by Carlier [7] can be modified to produce tightened "no-good" cuts. We then demonstratehow to create cuts by using constraint propagation. The branch-and check algorithm proposed is implemented in the Mosel modelling and optimization language. Computational experiments show that our algorithm outperforms the exact approach of P©