Worst-Case Performance Analysis of Some Approximation Algorithms for Minimizing Makespan and Flow-Time

Peruvemba Sundaram Ravi, Levent Tuncel, Michael Huang

In 1976, Coffman and Sethi conjectured that a natural extension of LPT list scheduling to the bicriteria scheduling problem of minimizing makespan over flowtime optimal schedules,…