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)

Approximation results for flow shop scheduling problems with machine availabilty constraints
Kubzin, Mikhail A., (2009)
 More ...