• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

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

Thumbnail
View/Open
cahier305.PDF (193.3Kb)
Date
2013
Dewey
Recherche opérationnelle
Sujet
scheduling problem; differential approximability
Journal issue
Discrete Optimization
Volume
10
Number
1
Publication date
2013
Article pages
61-68
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.disopt.2012.11.002
URI
https://basepub.dauphine.fr/handle/123456789/6305
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Kacem, Imed
Paschos, Vangelis
Type
Article accepté pour publication ou publié
Abstract (EN)
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.