# On-line scheduling of unit time jobs with rejection: minimizing the total completion time

Epstein, Leah
and
Noga, John
and
Woeginger, Gerhard J.
(2002)
*On-line scheduling of unit time jobs with rejection: minimizing the total completion time.*
Operations Research Letters, 30
(6).
pp. 415-420.
ISSN 0167-6377

PDF
Restricted to UT campus only : Request a copy 144kB |

Abstract: | We consider on-line scheduling of unit time jobs on a single machine with job-dependent penalties. The jobs arrive on-line (one by one) and can be either accepted and scheduled, or be rejected at the cost of a penalty. The objective is to minimize the total completion time of the accepted jobs plus the sum of the penalties of the rejected jobs.
We give an on-line algorithm for this problem with competitive ratio . Moreover, we prove that there does not exist an on-line algorithm with competitive ratio better than 1.63784. |

Item Type: | Article |

Copyright: | © 2002 Elsevier |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Research Group: | |

Link to this item: | http://purl.utwente.nl/publications/74863 |

Official URL: | http://dx.doi.org/10.1016/S0167-6377(02)00160-8 |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page

Metis ID: 208618