Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval
Kubzin, Mikhail A.
Strusevich, Vitaly A.
In this note, we consider the scheduling problem of minimizing the sum of the weighted completion times on a single machine with one non-availability interval on the machine under the non-resumable scenario. Together with a recent 2-approximation algorithm designed by Kacem [I. Kacem, Approximation algorithm for the weighted flow-time minimization on a single machine with a fixed non-availability interval, Computers & Industrial Engineering 54 (2008) 401-410], 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 worst-case performance ratio of 2+[epsilon].
Single machine scheduling Machine non-availability Total weighted completion time Approximation algorithm
In order to set up a list of libraries that you have access to,
you must first login
or sign up.
Then set up a personal list of libraries from your profile page by
clicking on your user name at the top right of any screen.