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