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 -