Competitive deadline scheduling via additional or faster processors

Abstract

This paper studies on-line scheduling in a single-processor system that allows preemption. The aim is to maximize the total value of jobs completed by their deadlines. It is known that if the on-line scheduler is given a processor faster (say, two times faster) than the off-line scheduler, then there exists an on-line algorithm called SLACKER that can achieve an O(1) competitive ratio. In this paper, we show that using additional unit-speed processors instead of a faster processor is a possible but not cost effective way to achieve an O(1) competitive ratio. Specifically, we find that-θ(log k) unit-speed processors are required, where k is the importance ratio. Another contribution of this paper is an improved analysis of the competitiveness of SLACKER; this new analysis enables us to show that SLACKER, when extended to multi-processor systems, can still guarantee an O(1) competitive ratio.