Approximation schemes for scheduling on parallel machines

N. Alon, Y. Azar, G.J. Woeginger, T. Yadid

    Research output: Contribution to journalArticleAcademicpeer-review

    144 Citations (Scopus)


    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
    Pages (from-to)55-66
    Number of pages12
    JournalJournal of Scheduling
    Issue number1
    Publication statusPublished - 1998


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

    Cite this