Approximation schemes for scheduling on parallel machines

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

doi:10.1002/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J

Approximation schemes for scheduling on parallel machines

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

Research output: Contribution to journal › Article › Academic › peer-review

126 Citations (Scopus)

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 language	English
Pages (from-to)	55-66
Number of pages	12
Journal	Journal of Scheduling
Volume	1
Issue number	1
DOIs	https://doi.org/10.1002/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J https://doi.org/10.1002/(SICI)1099-1425(199806)1;1<55;;AID-JOS2>3.0.CO;2-J
Publication status	Published - 1998

Access to Document

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

Cite this

@article{5e0478ad4d1a47fa8a89fd737b474a5d,

title = "Approximation schemes for scheduling on parallel machines",

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.",

author = "N. Alon and Y. Azar and G.J. Woeginger and T. Yadid",

year = "1998",

doi = "10.1002/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J",

language = "English",

volume = "1",

pages = "55--66",

journal = "Journal of Scheduling",

issn = "1094-6136",

publisher = "Springer",

number = "1",

}

TY - JOUR

T1 - Approximation schemes for scheduling on parallel machines

AU - Alon, N.

AU - Azar, Y.

AU - Woeginger, G.J.

AU - Yadid, T.

PY - 1998

Y1 - 1998

N2 - 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.

AB - 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.

U2 - 10.1002/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J

DO - 10.1002/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J

M3 - Article

VL - 1

SP - 55

EP - 66

JO - Journal of Scheduling

JF - Journal of Scheduling

SN - 1094-6136

IS - 1

ER -