Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed nonavailability interval
In this note, we consider the scheduling problem of minimizing the sum of the weighted completion times on a single machine with one nonavailability interval on the machine under the nonresumable scenario. Together with a recent 2approximation algorithm designed by Kacem [I. Kacem, Approximation algorithm for the weighted flowtime minimization on a single machine with a fixed nonavailability interval, Computers & Industrial Engineering 54 (2008) 401410], this paper is the first successful attempt to develop a constant ratio approximation algorithm for this problem. We present two approaches to designing such an algorithm. Our best algorithm guarantees a worstcase performance ratio of 2+[epsilon].
Year of publication: 
2009


Authors:  Kellerer, Hans ; Kubzin, Mikhail A. ; Strusevich, Vitaly A. 
Published in: 
European Journal of Operational Research.  Elsevier, ISSN 03772217.  Vol. 199.2009, 1, p. 111116

Publisher: 
Elsevier 
Keywords:  Single machine scheduling Machine nonavailability Total weighted completion time Approximation algorithm 
Saved in favorites
Similar items by person

Kellerer, Hans, (2009)

Kellerer, Hans, (2009)

Twomachine flow shop nowait scheduling with a nonavailability interval
Kubzin, Mikhail A., (2004)
 More ...