WORST-CASE PERFORMANCE ANALYSIS OF SOME APPROXIMATION ALGORITHMS FOR MINIMIZING MAKESPAN AND FLOW-TIME

Abstract. In 1976, Coffman and Sethi conjectured that a natural extension of LPT list sched-uling to the bicriteria scheduling problem of minimizing makespan over flowtime optimal sched-ules, called LD algorithm, has a simple worst-case performance bound: 5m−2 4m−1, where m is the number of machines. We study structure of potential minimal counterexamples to this conjec-ture and prove that the conjecture holds for the cases (i) n> 5m, (ii) m = 2, (iii) m = 3, and (iv) m ≥ 4, n ≤ 3m, where n is the number of jobs. We further conclude that to verify the conjecture, it suffices to analyze the following case: for every m ≥ 4, n ∈ {4m, 5m}. 1