File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Competitive deadline scheduling via additional or faster processors

TitleCompetitive deadline scheduling via additional or faster processors
Authors
KeywordsCompetitiveness
Deadline scheduling
Extra-resource analysis
On-line algorithms
Issue Date2003
PublisherSpringer New York LLC. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1094-6136
Citation
Journal Of Scheduling, 2003, v. 6 n. 2, p. 213-223 How to Cite?
AbstractThis paper studies on-line scheduling in a single-processor system that allows preemption. The aim is to maximize the total value of jobs completed by their deadlines. It is known that if the on-line scheduler is given a processor faster (say, two times faster) than the off-line scheduler, then there exists an on-line algorithm called SLACKER that can achieve an O(1) competitive ratio. In this paper, we show that using additional unit-speed processors instead of a faster processor is a possible but not cost effective way to achieve an O(1) competitive ratio. Specifically, we find that-θ(log k) unit-speed processors are required, where k is the importance ratio. Another contribution of this paper is an improved analysis of the competitiveness of SLACKER; this new analysis enables us to show that SLACKER, when extended to multi-processor systems, can still guarantee an O(1) competitive ratio.
Persistent Identifierhttp://hdl.handle.net/10722/48428
ISSN
2015 Impact Factor: 1.023
2015 SCImago Journal Rankings: 1.053
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorKoo, CYen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorNgan, TWen_HK
dc.contributor.authorTo, KKen_HK
dc.date.accessioned2008-05-22T04:12:44Z-
dc.date.available2008-05-22T04:12:44Z-
dc.date.issued2003en_HK
dc.identifier.citationJournal Of Scheduling, 2003, v. 6 n. 2, p. 213-223en_HK
dc.identifier.issn1094-6136en_HK
dc.identifier.urihttp://hdl.handle.net/10722/48428-
dc.description.abstractThis paper studies on-line scheduling in a single-processor system that allows preemption. The aim is to maximize the total value of jobs completed by their deadlines. It is known that if the on-line scheduler is given a processor faster (say, two times faster) than the off-line scheduler, then there exists an on-line algorithm called SLACKER that can achieve an O(1) competitive ratio. In this paper, we show that using additional unit-speed processors instead of a faster processor is a possible but not cost effective way to achieve an O(1) competitive ratio. Specifically, we find that-θ(log k) unit-speed processors are required, where k is the importance ratio. Another contribution of this paper is an improved analysis of the competitiveness of SLACKER; this new analysis enables us to show that SLACKER, when extended to multi-processor systems, can still guarantee an O(1) competitive ratio.en_HK
dc.format.extent249247 bytes-
dc.format.extent3039 bytes-
dc.format.extent3039 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypetext/plain-
dc.format.mimetypetext/plain-
dc.languageengen_HK
dc.publisherSpringer New York LLC. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1094-6136en_HK
dc.relation.ispartofJournal of Schedulingen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.rightsThe original publication is available at www.springerlink.comen_HK
dc.subjectCompetitivenessen_HK
dc.subjectDeadline schedulingen_HK
dc.subjectExtra-resource analysisen_HK
dc.subjectOn-line algorithmsen_HK
dc.titleCompetitive deadline scheduling via additional or faster processorsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1094-6136&volume=6&issue=2&spage=213&epage=223&date=2003&atitle=Competitive+Deadline+Scheduling+via+Additional+or+Faster+Processorsen_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturepostprinten_HK
dc.identifier.doi10.1023/A:1022998111685en_HK
dc.identifier.scopuseid_2-s2.0-0042639686en_HK
dc.identifier.hkuros91593-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0042639686&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume6en_HK
dc.identifier.issue2en_HK
dc.identifier.spage213en_HK
dc.identifier.epage223en_HK
dc.identifier.isiWOS:000221412400007-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridKoo, CY=7006652508en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridNgan, TW=6602433224en_HK
dc.identifier.scopusauthoridTo, KK=36785812300en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats