File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1016/j.entcs.2003.12.010
- Scopus: eid_2-s2.0-18944371991
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Article: Aggressive online deadline scheduling
Title | Aggressive online deadline scheduling |
---|---|
Authors | |
Keywords | Earliest deadline first Extra-resource analysis Firm deadline scheduling Online algorithms |
Issue Date | 2004 |
Publisher | Elsevier 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? |
Abstract | This 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 Identifier | http://hdl.handle.net/10722/89080 |
ISSN | 2023 SCImago Journal Rankings: 0.221 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Lam, TW | en_HK |
dc.contributor.author | Ngan, TWJ | en_HK |
dc.contributor.author | To, KK | en_HK |
dc.contributor.author | Wong, PWH | en_HK |
dc.date.accessioned | 2010-09-06T09:52:08Z | - |
dc.date.available | 2010-09-06T09:52:08Z | - |
dc.date.issued | 2004 | en_HK |
dc.identifier.citation | Electronic Notes In Theoretical Computer Science, 2004, v. 91, p. 148-157 | en_HK |
dc.identifier.issn | 1571-0661 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/89080 | - |
dc.description.abstract | This 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.language | eng | en_HK |
dc.publisher | Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/entcs | en_HK |
dc.relation.ispartof | Electronic Notes in Theoretical Computer Science | en_HK |
dc.rights | Electronic Notes in Theoretical Computer Science. Copyright © Elsevier BV. | en_HK |
dc.subject | Earliest deadline first | en_HK |
dc.subject | Extra-resource analysis | en_HK |
dc.subject | Firm deadline scheduling | en_HK |
dc.subject | Online algorithms | en_HK |
dc.title | Aggressive online deadline scheduling | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1571-0661&volume=91&spage=148&epage=157&date=2004&atitle=Aggressive+Online+Deadline+Scheduling | en_HK |
dc.identifier.email | Lam, TW:twlam@cs.hku.hk | en_HK |
dc.identifier.authority | Lam, TW=rp00135 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1016/j.entcs.2003.12.010 | en_HK |
dc.identifier.scopus | eid_2-s2.0-18944371991 | en_HK |
dc.identifier.hkuros | 91513 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-18944371991&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 91 | en_HK |
dc.identifier.spage | 148 | en_HK |
dc.identifier.epage | 157 | en_HK |
dc.publisher.place | Netherlands | en_HK |
dc.identifier.scopusauthorid | Lam, TW=7202523165 | en_HK |
dc.identifier.scopusauthorid | Ngan, TWJ=6602433224 | en_HK |
dc.identifier.scopusauthorid | To, KK=36785812300 | en_HK |
dc.identifier.scopusauthorid | Wong, PWH=9734871500 | en_HK |
dc.identifier.issnl | 1571-0661 | - |