Open AccessAggressive Online Deadline Scheduling
Author(s) -
TakWah Lam,
TsuenWan Ngan,
KarKeung To,
Prudence W. H. Wong
Publication year - 2004
Publication title -
electronic notes in theoretical computer science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.242
H-Index - 60
ISSN - 1571-0661
DOI - 10.1016/j.entcs.2003.12.010
Subject(s) - computer science , competitive analysis , online algorithm , scheduling (production processes) , earliest deadline first scheduling , distributed computing , processor scheduling , dynamic priority scheduling , rate monotonic scheduling , parallel computing , algorithm , upper and lower bounds , resource (disambiguation) , mathematical optimization , computer network , schedule , operating system , mathematics , mathematical analysis
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.link_to_subscribed_fulltex
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom