An iterative lower bound algorithm for the Single-Machine Scheduling Problem Under a Non-Availability Constraint for Maximum Delivery Time Minimization - Université de Lorraine
Conference Papers Year : 2014

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.
No file

Dates and versions

hal-01267626 , version 1 (04-02-2016)

Identifiers

  • HAL Id : hal-01267626 , version 1

Cite

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⟩
82 View
0 Download

Share

More