Online scheduling of two uniform machines to minimize total completion times
Peihai Liu, Xiwen Lu · Journal of Industrial and Management Optimization · 2008
In this paper, we study the online scheduling problem on two uniform machines with speeds 1 and $s \geq 1$, in which jobs are arriving over time. We consider both the preemptive and the non-preemptive machine environments. We first present a 2.618-competitive algorithm for the non-preemptive setting with the objective to minimize the total completion times. In the preemptive setting with the objective to minimize the total weighted completion times, we give an online algorithm which has a competitive ratio of 2.