Approximation algorithms for no idle time scheduling on a single machine with release times and delivery times - Université de Lorraine Accéder directement au contenu
Article Dans Une Revue Discrete Applied Mathematics Année : 2014

Approximation algorithms for no idle time scheduling on a single machine with release times and delivery times

Résumé

This paper is the first attempt to successfully design efficient approximation algorithms for the single-machine maximum lateness minimization problem when jobs have different release dates and tails (or delivery times) under the no idle time assumption (i.e., the schedule cannot contain any idle time between two consecutive jobs on the machine). Our work is motivated by interesting industrial applications to the production area (Chrétienne (2008) [3]). Our analysis shows that modifications of the classical algorithms of Potts and Schrage can lead to the same worst-case performance ratios obtained for the relaxed problem without the no idle time constraint. Then, we extend the result developed by Mastrolilli (2003) [13] for such a relaxed problem and we propose a polynomial time approximation scheme with efficient time complexity.

Domaines

Informatique

Dates et versions

hal-01783535 , version 1 (02-05-2018)

Identifiants

Citer

Imed Kacem, Hans Kellerer. Approximation algorithms for no idle time scheduling on a single machine with release times and delivery times. Discrete Applied Mathematics, 2014, 164, pp.154 - 160. ⟨10.1016/j.dam.2011.07.005⟩. ⟨hal-01783535⟩
50 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More