Weighted completion time minimization on a single-machine with a fixed non-availability interval: Differential approximability

Abstract : This paper is the first successful attempt on differential approximability study for a scheduling problem. Such a study considers the weighted completion time minimization on a single machine with a fixed non-availability interval. The analysis shows that the Weighted Shortest Processing Time (WSPT) rule cannot yield a differential approximation for the problem under consideration in the general case. Nevertheless, a slight modification of this rule provides an approximation with a differential ratio of 3-root 5/2 approximate to 0.38.
Type de document :
Article dans une revue
Discrete Optimization, Elsevier, 2013, 10 (1), pp.61-68. 〈10.1016/j.disopt.2012.11.002〉
Liste complète des métadonnées

https://hal.univ-lorraine.fr/hal-01267631
Contributeur : Catherine Angevelle <>
Soumis le : jeudi 4 février 2016 - 16:10:13
Dernière modification le : jeudi 11 janvier 2018 - 06:17:30

Lien texte intégral

Identifiants

Collections

Citation

Imed Kacem, Vangelis Th. Paschos. Weighted completion time minimization on a single-machine with a fixed non-availability interval: Differential approximability. Discrete Optimization, Elsevier, 2013, 10 (1), pp.61-68. 〈10.1016/j.disopt.2012.11.002〉. 〈hal-01267631〉

Partager

Métriques

Consultations de la notice

47