ALCOMFT-TR-02-57

Leah Epstein and Lene M. Favrholdt
Optimal Preemptive Semi-Online Scheduling to Minimize Makespan on Two Related Machines
Århus. Work packages 3 and 4. May 2002.

Abstract: We study a preemptive semi-online scheduling problem. Jobs with non-increasing sizes arrive one by one to be scheduled on two uniformly related machines. We analyze the algorithms as a function of the speed ratio (q>= 1) between the two machines. We design algorithms of optimal competitive ratio for all values of q, and show that for q>2, idle time needs to be introduced. This is the first preemptive scheduling problem over list, where idle time is provably required.

Postscript file: ALCOMFT-TR-02-57.ps.gz (81 kb).