On-line Scheduling with Tight Deadlines
Chiu-Yuen Koo, Tak-Wah Lam, Tsuen-Wan Ngan, Kunihiko Sadakane, and Kar-Keung To
Abstract.
This paper is concerned with the on-line problem of scheduling jobs
with tight deadlines in a uni-processor system. It has been
known for long that in such a setting, no on-line algorithm is
1-competitive (i.e., optimal) in the sense of matching the optimal
offline algorithm on the total value of jobs that meet the deadlines;
indeed, no algorithm can be better than k-competitive, where k is the
importance ratio of the jobs. Recent work, however, reveals
that the competitive ratio can be improved to a constant if the
on-line scheduler is equipped with a processor O(1) times faster,
and further to one when using a processor O(log k) times faster.
This paper presents a new on-line algorithm for scheduling jobs
with tight deadlines and shows that it is 1-competitive when using
a processor that is only O(1) times faster.
|
Download: ps