File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Improved competitive algorithms for online scheduling with partial job values

TitleImproved competitive algorithms for online scheduling with partial job values
Authors
Issue Date2003
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2003, v. 2697, p. 425-434 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. We give a new non-timesharing algorithm GAP for this problem for bounded m, where m is 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 a is the importance ratio. We also give a tradeoff result between competitiveness and the amount of extra resources. © Springer-Verlag Berlin Heidelberg 2003.
Persistent Identifierhttp://hdl.handle.net/10722/152370
ISSN
2023 SCImago Journal Rankings: 0.606
References

 

DC FieldValueLanguage
dc.contributor.authorChin, FYLen_US
dc.contributor.authorFung, SPYen_US
dc.date.accessioned2012-06-26T06:37:41Z-
dc.date.available2012-06-26T06:37:41Z-
dc.date.issued2003en_US
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2003, v. 2697, p. 425-434en_US
dc.identifier.issn0302-9743en_US
dc.identifier.urihttp://hdl.handle.net/10722/152370-
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. We give a new non-timesharing algorithm GAP for this problem for bounded m, where m is 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 a is the importance ratio. We also give a tradeoff result between competitiveness and the amount of extra resources. © Springer-Verlag Berlin Heidelberg 2003.en_US
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_US
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_US
dc.titleImproved competitive algorithms for online scheduling with partial job valuesen_US
dc.typeArticleen_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.scopuseid_2-s2.0-35048884197en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-35048884197&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume2697en_US
dc.identifier.spage425en_US
dc.identifier.epage434en_US
dc.publisher.placeGermanyen_US
dc.identifier.scopusauthoridChin, FYL=7005101915en_US
dc.identifier.scopusauthoridFung, SPY=7201970079en_US
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats