Approximation schemes for scheduling on parallel machines

Noga Alon, Yossi Azar, Gerhard J. Woeginger, Tal Yadid

Research output: Contribution to journalArticlepeer-review

170 Scopus citations

Abstract

We discuss scheduling problems with m identical machines and n jobs where each job has to be assigned to some machine. The goal is to optimize objective functions that solely depend on the machine completion times. As a main result, we identify some conditions on the objective function, under which the resulting scheduling problems possess a polynomial-time approximation scheme. Our result contains, generalizes, improves, simplifies, and unifies many other results in this area in a natural way.

Original languageEnglish (US)
Pages (from-to)55-66
Number of pages12
JournalJournal of Scheduling
Volume1
Issue number1
DOIs
StatePublished - 1998
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • General Engineering
  • Management Science and Operations Research
  • Artificial Intelligence

Keywords

  • Approximation algorithm
  • Approximation scheme
  • Combinatorial optimization
  • Scheduling theory
  • Worst-case ratio

Fingerprint

Dive into the research topics of 'Approximation schemes for scheduling on parallel machines'. Together they form a unique fingerprint.

Cite this