Power of Preemption for Minimizing Total Completion Time on Uniform Parallel Machines

For scheduling problems on parallel machines, the power of preemption is defined as the supremum ratio of the cost of an optimal nonpreemptive schedule over the cost of an optimal preemptive schedule (for the same input), where the cost is defined by a fixed common cost function. We present a tight analysis of the power of preemption for the problem of minimizing the total completion time on m≥ 2 uniformly related machines, showing that its value for m=2 is equal to 1.2, and its overall value is approximately 1.39795.