Computational performances of a simple interchange heuristic for a scheduling problem with an availability constraint - LAAS - Laboratoire d'Analyse et d'Architecture des Systèmes Accéder directement au contenu
Article Dans Une Revue Computers & Industrial Engineering Année : 2014

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

Résumé

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.
Fichier non déposé

Dates et versions

hal-02074379 , version 1 (20-03-2019)

Identifiants

Citer

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

Altmetric

Partager

Gmail Facebook X LinkedIn More