A PTAS for minimizing weighted completion time on uniformly related machines (extended abstract)

Chandra Chekuri, Sanjeev Khanna

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the well known problem of scheduling jobs with release dates to minimize their average weighted completion time. When multiple machines are available, the machine environment may range from identical machines (the processing time required by a job is invariant across the machines) at one end of the spectrum to unrelated machines (the processing time required by a job on each machine is specified by an arbitrary vector) at the other end. While the problem is strongly NP-hard even in the case of a single machine, constant factor approximation algorithms are known for even the most general machine environment of unrelated machines. Recently a PTAS was discovered for the case of identical parallel machines [1]. In contrast, the problem is MAX SNP-hard for unrelated machines [11]. An important open problem was to determine the approximability of the intermediate case of uniformly related machines where each machine has a speed and it takes p/s time to process a job of size p on a machine with speed s. We resolve the complexity of this problem by obtaining a PTAS. This improves the earlier known approximation ratio of (2 + ε).

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 28th International Colloquium, ICALP 2001, Proceedings
Pages848-861
Number of pages14
StatePublished - Dec 1 2001
Externally publishedYes
Event28th International Colloquium on Automata, Languages and Programming, ICALP 2001 - Crete, Greece
Duration: Jul 8 2001Jul 12 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2076 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other28th International Colloquium on Automata, Languages and Programming, ICALP 2001
CountryGreece
CityCrete
Period7/8/017/12/01

Keywords

  • Aerage completion time
  • Polynomial time approximation scheme
  • Sheduling
  • Uiformly related machines
  • Wighted completion time

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A PTAS for minimizing weighted completion time on uniformly related machines (extended abstract)'. Together they form a unique fingerprint.

Cite this