File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A tighter extra-resource analysis of online deadline scheduling

TitleA tighter extra-resource analysis of online deadline scheduling
Authors
KeywordsCompetitive analysis
Earliest deadline first
Extra-resource analysis
Firm deadline scheduling
Online algorithms
Issue Date2005
PublisherSpringer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905
Citation
Journal Of Combinatorial Optimization, 2005, v. 9 n. 2, p. 157-165 How to Cite?
AbstractThis paper is concerned with online algorithms for scheduling jobs with deadlines on a single processor. It has been known for long that unless the system is underloaded, no online scheduling algorithm can be 1-competitive, i.e., matching the performance of the optimal offline algorithm. Nevertheless, recent work has revealed that some online algorithms using a moderately faster processor (or extra processors) can guarantee very competitive performance Kalyanasundaram and Pruhs, 2000 or even be 1-competitive Koo et al., 2002; Lam and To, 2001. This paper takes a further step to investigate online scheduling algorithms with an even higher performance guarantee (i.e., better than 1-competitive algorithms) and in particular, presents an extra-resource analysis of the earliest-deadline-first strategy (EDF) with respect to such a higher performance guarantee. © 2005 Springer Science + Business Media, Inc.
Persistent Identifierhttp://hdl.handle.net/10722/48415
ISSN
2015 Impact Factor: 1.08
2015 SCImago Journal Rankings: 1.093
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorLam, TWen_HK
dc.contributor.authorNgan, TWJen_HK
dc.contributor.authorTo, KKen_HK
dc.date.accessioned2008-05-22T04:12:25Z-
dc.date.available2008-05-22T04:12:25Z-
dc.date.issued2005en_HK
dc.identifier.citationJournal Of Combinatorial Optimization, 2005, v. 9 n. 2, p. 157-165en_HK
dc.identifier.issn1382-6905en_HK
dc.identifier.urihttp://hdl.handle.net/10722/48415-
dc.description.abstractThis paper is concerned with online algorithms for scheduling jobs with deadlines on a single processor. It has been known for long that unless the system is underloaded, no online scheduling algorithm can be 1-competitive, i.e., matching the performance of the optimal offline algorithm. Nevertheless, recent work has revealed that some online algorithms using a moderately faster processor (or extra processors) can guarantee very competitive performance Kalyanasundaram and Pruhs, 2000 or even be 1-competitive Koo et al., 2002; Lam and To, 2001. This paper takes a further step to investigate online scheduling algorithms with an even higher performance guarantee (i.e., better than 1-competitive algorithms) and in particular, presents an extra-resource analysis of the earliest-deadline-first strategy (EDF) with respect to such a higher performance guarantee. © 2005 Springer Science + Business Media, Inc.en_HK
dc.format.extent205009 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 Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905en_HK
dc.relation.ispartofJournal of Combinatorial Optimizationen_HK
dc.rightsThe original publication is available at www.springerlink.comen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectCompetitive analysisen_HK
dc.subjectEarliest deadline firsten_HK
dc.subjectExtra-resource analysisen_HK
dc.subjectFirm deadline schedulingen_HK
dc.subjectOnline algorithmsen_HK
dc.titleA tighter extra-resource analysis of online deadline schedulingen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1382-6905&volume=9&issue=2&spage=157&epage=165&date=2005&atitle=A+Tighter+Extra-Resource+Analysis+of+Online+Deadline+Schedulingen_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturepostprinten_HK
dc.identifier.doi10.1007/s10878-005-6854-6en_HK
dc.identifier.scopuseid_2-s2.0-24144495450en_HK
dc.identifier.hkuros103183-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-24144495450&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume9en_HK
dc.identifier.issue2en_HK
dc.identifier.spage157en_HK
dc.identifier.epage165en_HK
dc.identifier.isiWOS:000228972200002-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridNgan, TWJ=6602433224en_HK
dc.identifier.scopusauthoridTo, KK=36785812300en_HK
dc.identifier.citeulike196210-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats