Skip to Main content Skip to Navigation
Journal articles

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).
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/inria-00339767
Contributor : Ruslan Sadykov <>
Submitted on : Tuesday, November 18, 2008 - 6:29:46 PM
Last modification on : Thursday, September 10, 2020 - 3:42:50 PM

Identifiers

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⟩

Share

Metrics

Record views

112