A tighter extra-resource analysis of online deadline scheduling

A tighter extra-resource analysis of online deadline scheduling

0.00 Avg rating0 Votes
Article ID: iaor20053105
Country: Netherlands
Volume: 9
Issue: 2
Start Page Number: 157
End Page Number: 165
Publication Date: Mar 2005
Journal: Journal of Combinatorial Optimization
Authors: , ,
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 guarante very competitive performance, or even be 1-competitive. 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.

Reviews

Required fields are marked *. Your email address will not be published.