File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Improved competitive algorithms for online scheduling with partial job values

TitleImproved competitive algorithms for online scheduling with partial job values
Authors
KeywordsOnline Algorithms
Partial Job Values
Resource Augmentation
Scheduling
Issue Date2004
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs
Citation
Theoretical Computer Science, 2004, v. 325 n. 3, p. 467-478 How to Cite?
AbstractThis 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 x 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. © 2004 Elsevier B.V. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/151911
ISSN
2015 Impact Factor: 0.643
2015 SCImago Journal Rankings: 0.720
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorChin, FYLen_US
dc.contributor.authorFung, SPYen_US
dc.date.accessioned2012-06-26T06:30:43Z-
dc.date.available2012-06-26T06:30:43Z-
dc.date.issued2004en_US
dc.identifier.citationTheoretical Computer Science, 2004, v. 325 n. 3, p. 467-478en_US
dc.identifier.issn0304-3975en_US
dc.identifier.urihttp://hdl.handle.net/10722/151911-
dc.description.abstractThis 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 x 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. © 2004 Elsevier B.V. All rights reserved.en_US
dc.languageengen_US
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcsen_US
dc.relation.ispartofTheoretical Computer Scienceen_US
dc.subjectOnline Algorithmsen_US
dc.subjectPartial Job Valuesen_US
dc.subjectResource Augmentationen_US
dc.subjectSchedulingen_US
dc.titleImproved competitive algorithms for online scheduling with partial job valuesen_US
dc.typeConference_Paperen_US
dc.identifier.emailChin, FYL:chin@cs.hku.hken_US
dc.identifier.authorityChin, FYL=rp00105en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1016/j.tcs.2004.02.046en_US
dc.identifier.scopuseid_2-s2.0-4544224232en_US
dc.identifier.hkuros98373-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-4544224232&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume325en_US
dc.identifier.issue3en_US
dc.identifier.spage467en_US
dc.identifier.epage478en_US
dc.identifier.isiWOS:000224235000009-
dc.publisher.placeNetherlandsen_US
dc.identifier.scopusauthoridChin, FYL=7005101915en_US
dc.identifier.scopusauthoridFung, SPY=7201970079en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats