Extra Processors versus Future Information
in Optimal Deadline Scheduling
Chiu-Yuen Koo, Tak-Wah Lam, Tsuen-Wan Ngan, and Kar-Keung To
|
Abstract. This paper is concerned
with the extra-resource analysis of online scheduling algorithms.
In particular, it studies how to make use of multiple processors to
counteract the lack of future information in online deadline scheduling.
Our results extend the previous work that are primarily based of
using a faster processor to obtain a performance guarantee.
The challenge arises from the fact that jobs are sequential in nature
and cannot be executed on more than one processor at the same time.
Thus, a faster processor can speed up a job while multiple unit-speed
processors cannot help.
|
Download: pdf