File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Aggressive online deadline scheduling

TitleAggressive online deadline scheduling
Authors
KeywordsEarliest deadline first
Extra-resource analysis
Firm deadline scheduling
Online algorithms
Issue Date2004
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/entcs
Citation
Electronic Notes In Theoretical Computer Science, 2004, v. 91, p. 148-157 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 significantly improve the competitiveness [J. ACM 47 (2000) 617] or even be 1-competitive [Proc. SODA (2001) 755, Proc. SPAA (2002) 133]. 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. © 2004 Published by Elsevier B.V.
Persistent Identifierhttp://hdl.handle.net/10722/89080
ISSN
2015 SCImago Journal Rankings: 0.462
References

 

DC FieldValueLanguage
dc.contributor.authorLam, TWen_HK
dc.contributor.authorNgan, TWJen_HK
dc.contributor.authorTo, KKen_HK
dc.contributor.authorWong, PWHen_HK
dc.date.accessioned2010-09-06T09:52:08Z-
dc.date.available2010-09-06T09:52:08Z-
dc.date.issued2004en_HK
dc.identifier.citationElectronic Notes In Theoretical Computer Science, 2004, v. 91, p. 148-157en_HK
dc.identifier.issn1571-0661en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89080-
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 significantly improve the competitiveness [J. ACM 47 (2000) 617] or even be 1-competitive [Proc. SODA (2001) 755, Proc. SPAA (2002) 133]. 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. © 2004 Published by Elsevier B.V.en_HK
dc.languageengen_HK
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/entcsen_HK
dc.relation.ispartofElectronic Notes in Theoretical Computer Scienceen_HK
dc.rightsElectronic Notes in Theoretical Computer Science. Copyright © Elsevier BV.en_HK
dc.subjectEarliest deadline firsten_HK
dc.subjectExtra-resource analysisen_HK
dc.subjectFirm deadline schedulingen_HK
dc.subjectOnline algorithmsen_HK
dc.titleAggressive online deadline schedulingen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1571-0661&volume=91&spage=148&epage=157&date=2004&atitle=Aggressive+Online+Deadline+Schedulingen_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1016/j.entcs.2003.12.010en_HK
dc.identifier.scopuseid_2-s2.0-18944371991en_HK
dc.identifier.hkuros91513en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-18944371991&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume91en_HK
dc.identifier.spage148en_HK
dc.identifier.epage157en_HK
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridNgan, TWJ=6602433224en_HK
dc.identifier.scopusauthoridTo, KK=36785812300en_HK
dc.identifier.scopusauthoridWong, PWH=9734871500en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats