# Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval

Kellerer, Hans, Kubzin, Mikhail A. and Strusevich, Vitaly A. (2009) *Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval.* European Journal of Operational Research, 199 (1). pp. 111-116. ISSN 0377-2217 (doi:10.1016/j.ejor.2008.11.003)

## Abstract

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+ε. © 2008 Elsevier B.V. All rights reserved.

Item Type: | Article |
---|---|

Uncontrolled Keywords: | single machine scheduling, machine non-availability, total weighted completion time, approximation algorithm |

Subjects: | T Technology > T Technology (General) Q Science > QA Mathematics > QA75 Electronic computers. Computer science |

School / Department / Research Groups: | School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Department of Mathematical Sciences School of Computing & Mathematical Sciences > Statistics & Operational Research Group |

Related URLs: | |

Last Modified: | 31 Mar 2011 18:20 |

URI: | http://gala.gre.ac.uk/id/eprint/1302 |

### Actions (login required)

View Item |