Sadykov, Ruslan
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 demonstrate
how 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©♭ridy et al. [22], which, to our knowledge, is the best reported in the literature.
Bibliographic reference |
Sadykov, Ruslan. A branch-and-check algorithm for minimizing the sum of the weights of the late jobs on a single machine with release dates. CORE Discussion Papers ; 2005/57 (2005) |
Permanent URL |
http://hdl.handle.net/2078.1/4653 |