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

Abstract : In this paper we consider the scheduling problem of minimizing the weighted number of late jobs on a single machine ($1\mid r_j\mid\sum w_j U_j$). 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 infeasibility cuts. We suggest two ways to generate cuts. First, tightened "no-good" cuts are derived using a modification of the algorithm by Carlier (1982, EJOR, v.11, 42-47) which was developed for the problem of minimizing maximum lateness on a single machine. Secondly we show how to create cuts by using constraint propagation. The proposed algorithm is implemented in the Mosel modeling and optimization language. Computational experiments on instances with up to 140 jobs are reported. A comparison is presented with the exact approach of Péridy at al. (2003, EJOR, v.148, 591-603).
Type de document :
Article dans une revue
European Journal of Operational Research, Elsevier, 2008, 189 (3), pp.1284--1304. 〈10.1016/j.ejor.2006.06.078〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00339767
Contributeur : Ruslan Sadykov <>
Soumis le : mardi 18 novembre 2008 - 18:29:46
Dernière modification le : mardi 18 novembre 2008 - 18:29:46

Identifiants

Citation

Ruslan Sadykov. A branch-and-check algorithm for minimizing the sum of the weights of the late jobs on a single machine with release dates. European Journal of Operational Research, Elsevier, 2008, 189 (3), pp.1284--1304. 〈10.1016/j.ejor.2006.06.078〉. 〈inria-00339767〉

Partager

Métriques

Consultations de la notice

44