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

IMADA HOME | SDU HOME | Previous page Last modified: 2012-05-19 by Lene Monrad Favrholdt <lenem@imada.sdu.dk>