A branch-and-check algorithm for minimizing the sum of the weights of the late jobs on a single machine with release dates - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue European Journal of Operational Research Année : 2008

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

Résumé

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).

Dates et versions

inria-00339767 , version 1 (18-11-2008)

Identifiants

Citer

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, 2008, 189 (3), pp.1284--1304. ⟨10.1016/j.ejor.2006.06.078⟩. ⟨inria-00339767⟩
23 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More