Optimal preemptive semi-online scheduling to minimize makespan on two related machines

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.