Minimizing the maximum starting time on-line
We study the scheduling problem of minimizing the maximum starting time on-line. The goal is to minimize the last time that a job starts. We show that while the greedy algorithm has a competitive ratio of $Theta(log m)$, we can give a constant competitive algorithm for this problem. We also show that the greedy algorithm is optimal for resource augmentation in the sense that it requires 2<em>m-</em>1 machines to have a competitive ratio of 1, whereas no algorithm can achieve this with 2<em>m-</em>1 machines.
|Software Engineering [SEN]|
Epstein, L, & van Stee, R. (2001). Minimizing the maximum starting time on-line. Software Engineering [SEN]. CWI.