(Logo)   IMADA
University of Southern Denmark IMADA - Department of Mathematics and Computer Science

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 required.

The publication is available from ScienceDirect (subscription may be required).