dc.contributor.author | Kacem, Imed | |
dc.contributor.author | Paschos, Vangelis | |
dc.date.accessioned | 2011-05-19T13:05:30Z | |
dc.date.available | 2011-05-19T13:05:30Z | |
dc.date.issued | 2013 | |
dc.identifier.uri | https://basepub.dauphine.fr/handle/123456789/6305 | |
dc.language.iso | en | en |
dc.subject | scheduling problem | en |
dc.subject | differential approximability | en |
dc.subject.ddc | 003 | en |
dc.title | Weighted completion time minimization on a single-machine with a fixed non-availability interval: differential approximability | en |
dc.type | Article accepté pour publication ou publié | |
dc.description.abstracten | 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 studied problem in the general case. Nevertheless,
a slight modification of this rule provides an approximation with a
differential ratio of
3−√5
2 ≈ 0.38. | en |
dc.relation.isversionofjnlname | Discrete Optimization | |
dc.relation.isversionofjnlvol | 10 | |
dc.relation.isversionofjnlissue | 1 | |
dc.relation.isversionofjnldate | 2013 | |
dc.relation.isversionofjnlpages | 61-68 | |
dc.relation.isversionofdoi | http://dx.doi.org/10.1016/j.disopt.2012.11.002 | |
dc.description.sponsorshipprivate | oui | en |
dc.relation.isversionofjnlpublisher | Elsevier | |
dc.subject.ddclabel | Recherche opérationnelle | en |