TY - JOUR
T1 - Optimal Preemptive Semi-Online Scheduling to Minimize Makespan on Two Related Machines
AU - Epstein, Leah
AU - Favrholdt, Lene Monrad
PY - 2002
Y1 - 2002
N2 - 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.
AB - 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.
U2 - 10.1016/s0167-6377(02)00179-7
DO - 10.1016/s0167-6377(02)00179-7
M3 - Journal article
SN - 0167-6377
VL - 30
SP - 269
EP - 275
JO - Operations Research Letters
JF - Operations Research Letters
IS - 4
ER -