Approximation schemes for scheduling on parallel machines

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

Research output: Contribution to journalArticle

116 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

All Science Journal Classification (ASJC) codes

  • Software
  • Engineering(all)
  • 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