An optimal algorithm for preemptive on-line scheduling

The authors investigate the problem of on-line scheduling jobs on m identical parallel machines where preemption is allowed. The goal is to minimize the makespan. They derive an approximation algorithm with worst-case guarantee m^m/(m^m-(m-1)^m) for every m≥2, which increasingly tends to e/(e-1)≅1.58 as m⇒•. Moreover, the authors prove that for no m≥2 there does exist any approximation algorithm with a better worst-case guarantee.