A branch-and-check algorithm for minimizing the sum of the weights of the late jobs on a single machine with release dates
(2005)
Files
dp2005_57.pdf
Open Access - Adobe PDF
- 320.98 KB
Details
- Authors
- Abstract
- 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.
- Affiliations
Citations
Sadykov, R. (2005). 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). https://hdl.handle.net/2078.5/128631