Optimization Online


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

Peruvemba Sundaram Ravi(pravi***at***wlu.ca)
Levent Tuncel(ltuncel***at***math.uwaterloo.ca)
Michael Huang(Michael-Huang***at***u.northwestern.edu)

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 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.

Keywords: parallel identical machines, makespan, total completion time, approximation algorithms for scheduling

Category 1: Combinatorial Optimization (Approximation Algorithms )

Category 2: Applications -- OR and Management Sciences (Scheduling )


Download: [PDF]

Entry Submitted: 12/17/2013
Entry Accepted: 01/01/2014
Entry Last Modified: 12/17/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society