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

Ruslan Sadykov

No 2005057, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

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 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©

Date: 2005-09
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2005.html (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2005057

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().