Worst-case performance analysis of some approximation algorithms for minimizing makespan and flowtime

Peruvemba Sundaram Ravi (), Levent Tunçel () and Michael Huang ()
Additional contact information
Peruvemba Sundaram Ravi: School of Business and Economics, Wilfrid Laurier University
Levent Tunçel: University of Waterloo

Journal of Scheduling, 2016, vol. 19, issue 5, No 3, 547-561

Abstract: Abstract 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: $$\frac{5m-2}{4m-1}$$ 5 m - 2 4 m - 1 , where m is the number of machines. We study the structure of potential minimal counterexamples to this conjecture, provide some new tools and techniques for the analysis of such algorithms, and prove that to verify the conjecture, it suffices to analyze the following case: for every $$m \ge 4$$ m ≥ 4 , $$n \in \{4m, 5m\}$$ n ∈ { 4 m , 5 m } , where n is the number of jobs.

Keywords: Parallel identical machines; Makespan; Total completion time; Approximation algorithms for scheduling (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-015-0467-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:19:y:2016:i:5:d:10.1007_s10951-015-0467-4

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-015-0467-4

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().