Extra Processors versus Future Information
in Optimal Deadline Scheduling
Chiu-Yuen Koo, Tak-Wah Lam, Tsuen-Wan "Johnny" Ngan, and Kar-Keung To
|
Abstract. This paper is concerned
with the design of online scheduling algorithms that exploit extra
resources. 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 on
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.
|
Download: ps