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
141Kb

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:	Discrete Mathematics and Mathematical Programming (DMMP)
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

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 208618