Computational performances of a simple interchange heuristic for a scheduling problem with an availability constraint

Julien Moncel 1 Jérémie Thiery 2 Ariel Waserhole 2
1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
LAAS - Laboratoire d'analyse et d'architecture des systèmes
2 G-SCOP_ROSP - ROSP
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
Abstract : This paper deals with a scheduling problem on a single machine with an availability constraint. The problem is known to be NP-complete and admits several approximation algorithms. In this paper we study the approximation scheme described in He et al. [Y. He, W. Zhong, H. Gu, Improved algorithms for two single machine scheduling problems, Theoretical Computer Science 363 (2006) 257–265]. We provide the computation of an improved relative error of this heuristic, as well as a proof that this new bound is tight. We also present some computational experiments to test this heuristic on random instances.
Document type :
Journal articles
Complete list of metadatas

https://hal.archives-ouvertes.fr/hal-02074379
Contributor : Julien Moncel <>
Submitted on : Wednesday, March 20, 2019 - 3:52:45 PM
Last modification on : Friday, January 10, 2020 - 9:10:16 PM

Identifiers

Citation

Julien Moncel, Jérémie Thiery, Ariel Waserhole. Computational performances of a simple interchange heuristic for a scheduling problem with an availability constraint. Computers and Industrial Engineering, Elsevier, 2014, 67, pp.216-222. ⟨10.1016/j.cie.2013.08.017⟩. ⟨hal-02074379⟩

Share

Metrics

Record views

69