Skip to Main content Skip to Navigation
Reports

A branch and bound approach for earliness-tardiness scheduling problems with different due dates

Abstract : The problem of scheduling n jobs on a single machine in order to minimize the weighted sum of earliness and tardiness in NP-complete when jobs have different due dates. In most of the papers dedicated to this problem, authors assume that there is no idle time between two consecutive jobs. However, as indicated by several authors, this assumption is not consistent with the earliness-tardiness criterion. It is the reason why we do not make this assumption in this paper. To reach an optimal solution, we propose a branch-and-bound approach which takes advantage of some dominance properties and lower bounding procedures. Numerical experiments show that the algorithm can solve this problem with up to twenty jobs in a reasonable amont of time.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00074180
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 2:41:44 PM
Last modification on : Thursday, February 11, 2021 - 2:48:12 PM
Long-term archiving on: : Tuesday, April 12, 2011 - 3:48:15 PM

Identifiers

  • HAL Id : inria-00074180, version 1

Collections

Citation

Haoxun Chen, Chengbin Chu, Jean-Marie Proth. A branch and bound approach for earliness-tardiness scheduling problems with different due dates. [Research Report] RR-2495, INRIA. 1995, pp.19. ⟨inria-00074180⟩

Share

Metrics

Record views

155

Files downloads

184