Back to search

University of Waterloo

Techniques for Proving Approximation Ratios in Scheduling

Abstract

dc:description.abstract

The problem of finding a schedule with the lowest makespan in the class of all flowtime-optimal schedules for parallel identical machines is an NP-hard problem. Several approximation algorithms have been suggested for this problem. We focus on algorithms that are fast and easy to implement, rather than on more involved algorithms that might provide tighter approximation bounds. A set of approaches for proving conjectured bounds on performance ratios for such algorithms is outlined. These approaches are used to examine Coffman and Sethi's conjecture for a worst-case bound on the ratio of the makespan of the schedule generated by the LD algorithm to the makespan of the optimal schedule. A significant reduction is achieved in the size of a hypothesised minimal counterexample to this conjecture.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2010

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ravi, Peruvemba Sundaram

Subjects

dc:subject × 6

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/5552

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Ravi, Peruvemba Sundaram. Techniques for Proving Approximation Ratios in Scheduling. University of Waterloo, 2010. http://hdl.handle.net/10012/5552