Please use this identifier to cite or link to this item:
Title: Improved competitive algorithms for online scheduling with partial job values
Authors: Chin, F. Y. L.
Fung, S. P. Y.
First Published: 2004
Citation: Theoretical Computer Science, 2004, 325 (3), pp.467-478
Abstract: This paper considers an online scheduling problem arising from Quality-of-Service (QoS) applications. We are required to schedule a set of jobs, each with release time, deadline, processing time and weight. The objective is to maximize the total value obtained for scheduling the jobs. Unlike the traditional model of this scheduling problem, in our model unfinished jobs also get partial values proportional to their amounts processed. No non-timesharing algorithm for this problem with competitive ratio better than 2 is known. We give a new non-timesharing algorithm GAP that improves this ratio for bounded values of m, where m can be the number of concurrent jobs or the number of weight classes. The competitive ratio is improved from 2 to 1.618 (golden ratio) which is optimal for m=2, and when applied to cases with m>2 it still gives a competitive ratio better than 2, e.g. 1.755 when m=3. We also give a new study of the problem in the multiprocessor setting, giving an upper bound of 2 and a lower bound of 1.25 for the competitiveness. Finally, we consider resource augmentation and show that O(logα) speedup or extra processors is sufficient to achieve optimality, where α is the importance ratio. We also give a tradeoff result, showing that in fact a small amount of extra resources is sufficient for achieving close-to-optimal competitiveness.
DOI Link: 10.1016/j.tcs.2004.02.046
ISSN: 0304-3975
Type: Article
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
There are no files associated with this item.

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.