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.
Type de document :
Rapport
[Research Report] RR-2495, INRIA. 1995, pp.19
Liste complète des métadonnées

https://hal.inria.fr/inria-00074180
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 14:41:44
Dernière modification le : samedi 17 septembre 2016 - 01:06:55
Document(s) archivé(s) le : mardi 12 avril 2011 - 15:48:15

Fichiers

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

113

Téléchargements de fichiers

93