File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Online scheduling of unit jobs with bounded importance ratio

TitleOnline scheduling of unit jobs with bounded importance ratio
Authors
KeywordsCompetitive analysis
Importance ratio
Online scheduling
Quality of service
Issue Date2005
PublisherWorld Scientific Publishing Co Pte Ltd. The Journal's web site is located at http://www.worldscinet.com/ijfcs/ijfcs.shtml
Citation
International Journal Of Foundations Of Computer Science, 2005, v. 16 n. 3, p. 581-598 How to Cite?
AbstractWe consider the following online scheduling problem. We are given a set of jobs, each having an integral release time and deadline, unit processing length, and a nonnegative real weight. In each time unit one job is to be scheduled, and the objective is to maximize the total value (weight) obtained by scheduling the jobs. This problem arises in the scheduling of packets in network switches supporting quality-of-service (QoS). Previous algorithms for this problem are 2-competitive. In this paper we propose a new algorithm that achieves an improved competitive ratio when the importance ratio is bounded. Specifically, for job weights within the range [1..B], our algorithm is 2 - 1/([lg B] + 2)-competitive, and the bound is tight. © World Scientific Publishing Company.
Persistent Identifierhttp://hdl.handle.net/10722/88910
ISSN
2015 Impact Factor: 0.467
2015 SCImago Journal Rankings: 0.394
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorFung, SPYen_HK
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorShen, Hen_HK
dc.date.accessioned2010-09-06T09:50:01Z-
dc.date.available2010-09-06T09:50:01Z-
dc.date.issued2005en_HK
dc.identifier.citationInternational Journal Of Foundations Of Computer Science, 2005, v. 16 n. 3, p. 581-598en_HK
dc.identifier.issn0129-0541en_HK
dc.identifier.urihttp://hdl.handle.net/10722/88910-
dc.description.abstractWe consider the following online scheduling problem. We are given a set of jobs, each having an integral release time and deadline, unit processing length, and a nonnegative real weight. In each time unit one job is to be scheduled, and the objective is to maximize the total value (weight) obtained by scheduling the jobs. This problem arises in the scheduling of packets in network switches supporting quality-of-service (QoS). Previous algorithms for this problem are 2-competitive. In this paper we propose a new algorithm that achieves an improved competitive ratio when the importance ratio is bounded. Specifically, for job weights within the range [1..B], our algorithm is 2 - 1/([lg B] + 2)-competitive, and the bound is tight. © World Scientific Publishing Company.en_HK
dc.languageengen_HK
dc.publisherWorld Scientific Publishing Co Pte Ltd. The Journal's web site is located at http://www.worldscinet.com/ijfcs/ijfcs.shtmlen_HK
dc.relation.ispartofInternational Journal of Foundations of Computer Scienceen_HK
dc.subjectCompetitive analysisen_HK
dc.subjectImportance ratioen_HK
dc.subjectOnline schedulingen_HK
dc.subjectQuality of serviceen_HK
dc.titleOnline scheduling of unit jobs with bounded importance ratioen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0129-0541&volume=16&issue=3&spage=581&epage=598&date=2005&atitle=Online+Scheduling+of+Unit+Jobs+with+Bounded+Importance+Ratioen_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1142/S0129054105003170en_HK
dc.identifier.scopuseid_2-s2.0-33746209092en_HK
dc.identifier.hkuros98364en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33746209092&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume16en_HK
dc.identifier.issue3en_HK
dc.identifier.spage581en_HK
dc.identifier.epage598en_HK
dc.identifier.isiWOS:000229549200013-
dc.publisher.placeSingaporeen_HK
dc.identifier.scopusauthoridFung, SPY=7201970079en_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridShen, H=7404522601en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats