An iterative lower bound algorithm for the Single-Machine Scheduling Problem Under a Non-Availability Constraint for Maximum Delivery Time Minimization

Abstract : We consider the single machine scheduling problem with release dates and tails, provided that the machine is unavailable during a fixed interval. This problem is strongly NP-hard. We use the Jackson's preemptive algorithm with precedence constraints to compute a lower bound and the Schrage's sequence as an upper bound. Then, we propose an improved lower bound which is based on an iterative procedure. Numerical experiments show the effectiveness of the bounds.
Type de document :
Communication dans un congrès
Kacem, I and Laroche, P and Roka, Z. 2014 INTERNATIONAL CONFERENCE ON CONTROL, DECISION AND INFORMATION TECHNOLOGIES (CODIT), Nov 2014, Metz, France. pp.288-291, 2014
Liste complète des métadonnées

https://hal.univ-lorraine.fr/hal-01267626
Contributeur : Catherine Angevelle <>
Soumis le : jeudi 4 février 2016 - 16:10:09
Dernière modification le : mercredi 22 novembre 2017 - 10:56:26

Identifiants

  • HAL Id : hal-01267626, version 1

Collections

Citation

Walid Hfaiedh, Cherif Sadfi, Imed Kacem, Atidel B. Hadj-Alouane. An iterative lower bound algorithm for the Single-Machine Scheduling Problem Under a Non-Availability Constraint for Maximum Delivery Time Minimization. Kacem, I and Laroche, P and Roka, Z. 2014 INTERNATIONAL CONFERENCE ON CONTROL, DECISION AND INFORMATION TECHNOLOGIES (CODIT), Nov 2014, Metz, France. pp.288-291, 2014. 〈hal-01267626〉

Partager

Métriques

Consultations de la notice

55