File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1142/S0129054105003170
- Scopus: eid_2-s2.0-33746209092
- WOS: WOS:000229549200013
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Online scheduling of unit jobs with bounded importance ratio
Title | Online scheduling of unit jobs with bounded importance ratio |
---|---|
Authors | |
Keywords | Competitive analysis Importance ratio Online scheduling Quality of service |
Issue Date | 2005 |
Publisher | World 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? |
Abstract | We 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 Identifier | http://hdl.handle.net/10722/88910 |
ISSN | 2023 Impact Factor: 0.6 2023 SCImago Journal Rankings: 0.373 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Fung, SPY | en_HK |
dc.contributor.author | Chin, FYL | en_HK |
dc.contributor.author | Shen, H | en_HK |
dc.date.accessioned | 2010-09-06T09:50:01Z | - |
dc.date.available | 2010-09-06T09:50:01Z | - |
dc.date.issued | 2005 | en_HK |
dc.identifier.citation | International Journal Of Foundations Of Computer Science, 2005, v. 16 n. 3, p. 581-598 | en_HK |
dc.identifier.issn | 0129-0541 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/88910 | - |
dc.description.abstract | We 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.language | eng | en_HK |
dc.publisher | World Scientific Publishing Co Pte Ltd. The Journal's web site is located at http://www.worldscinet.com/ijfcs/ijfcs.shtml | en_HK |
dc.relation.ispartof | International Journal of Foundations of Computer Science | en_HK |
dc.subject | Competitive analysis | en_HK |
dc.subject | Importance ratio | en_HK |
dc.subject | Online scheduling | en_HK |
dc.subject | Quality of service | en_HK |
dc.title | Online scheduling of unit jobs with bounded importance ratio | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://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+Ratio | en_HK |
dc.identifier.email | Chin, FYL:chin@cs.hku.hk | en_HK |
dc.identifier.authority | Chin, FYL=rp00105 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1142/S0129054105003170 | en_HK |
dc.identifier.scopus | eid_2-s2.0-33746209092 | en_HK |
dc.identifier.hkuros | 98364 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-33746209092&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 16 | en_HK |
dc.identifier.issue | 3 | en_HK |
dc.identifier.spage | 581 | en_HK |
dc.identifier.epage | 598 | en_HK |
dc.identifier.isi | WOS:000229549200013 | - |
dc.publisher.place | Singapore | en_HK |
dc.identifier.scopusauthorid | Fung, SPY=7201970079 | en_HK |
dc.identifier.scopusauthorid | Chin, FYL=7005101915 | en_HK |
dc.identifier.scopusauthorid | Shen, H=7404522601 | en_HK |
dc.identifier.issnl | 0129-0541 | - |