Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

https://hal.univ-lorraine.fr/hal-01267626
Contributor : Catherine Angevelle <>
Submitted on : Thursday, February 4, 2016 - 4:10:09 PM
Last modification on : Wednesday, October 28, 2020 - 9:52:04 AM

Identifiers

  • 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. 2014 INTERNATIONAL CONFERENCE ON CONTROL, DECISION AND INFORMATION TECHNOLOGIES (CODIT), Nov 2014, Metz, France. pp.288-291. ⟨hal-01267626⟩

Share

Metrics

Record views

160