A Tighter Extra-Resource Analysis of Online Deadline Scheduling

Authors: Lam, Tak-Wah¹; Ngan, Tusen-Wan²; To, Kar-Keung³

Source: Journal of Combinatorial Optimization, Volume 9, Number 2, March 2005 , pp. 157-165(9)

Publisher: Springer

Buy & download fulltext article:

Price: $47.00 plus tax (Refund Policy)

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 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.

Keywords: online algorithms; competitive analysis; extra-resource analysis; firm deadline scheduling; earliest deadline first

Document Type: Research article

DOI: http://dx.doi.org/10.1007/s10878-005-6854-6

Affiliations: 1: Department of Computer Science, University of Hong Kong, Hong Kong, Email: twlam@cs.hku.hk 2: Department of Computer Science, Rice University, Houston, Email: twngan@cs.rice.edu 3: Department of Computer Science, University of Hong Kong, Hong Kong, Email: kkto@cs.hku.hk

Publication date: 2005-03-01