  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, 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 conjecture and prove
that the conjecture holds for the cases (i) n > 5m, (ii) m = 2, (iii) m = 3,
and (iv) m greater than or equal to 4, n less than or equal to 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 greater than or equal to 4,
n is either equal to 4m or 5m.
