Article ID: | iaor20163650 |
Volume: | 19 |
Issue: | 5 |
Start Page Number: | 547 |
End Page Number: | 561 |
Publication Date: | Oct 2016 |
Journal: | Journal of Scheduling |
Authors: | Tunel Levent, Huang Michael, Ravi Peruvemba |
Keywords: | scheduling, production, combinatorial optimization |
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 the LD algorithm, has a simple worst‐case performance bound: