An iterative lower bound algorithm for the single-machine scheduling problem under a non-availability constraint for maximum delivery time minimization

Author

Hfaiedh, Walid ; Sadfi, Cherif ; Kacem, Imed ; Hadj-Alouane, Atidel B.

Author_Institution

Ecole Nat. d´Ing. de Tunis, Univ. de Tunis El Manar, Tunis, Tunisia

fYear

2014

fDate

3-5 Nov. 2014

Firstpage

288

Lastpage

291

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.

Keywords

computational complexity; iterative methods; minimisation; single machine scheduling; Jackson preemptive algorithm; NP-hard problem; Schrage sequence; iterative lower bound algorithm; iterative procedure; maximum delivery time minimization; nonavailability constraint; precedence constraints; single-machine scheduling problem; Availability; Job shop scheduling; Optimal scheduling; Processor scheduling; Schedules; Single machine scheduling; Upper bound;

fLanguage

English

Publisher

ieee

Conference_Titel

Control, Decision and Information Technologies (CoDIT), 2014 International Conference on

Conference_Location

Metz

Type

conf

DOI

10.1109/CoDIT.2014.6996908

Filename

6996908