- Optimal Preemptive Semi-Online Scheduling to Minimize Makespan on
Two Related Machines
- Leah Epstein, Lene M. Favrholdt
Operations Research Letters, 30(4): 269-275, 2002
We study a preemptive semi-online scheduling problem. Jobs with
non-increasing weights 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
The publication is available from ScienceDirect (subscription may be required).