Approximation schemes for scheduling on parallel machines

Noga Alon; Yossi Azar; Gerhard J. Woeginger; Tal 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

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

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

182 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 language	English (US)
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
State	Published - 1998
Externally published	Yes

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

Access to Document

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

Cite this

@article{51d712dd19284f1abbc7de62bb3b8b0d,

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

keywords = "Approximation algorithm, Approximation scheme, Combinatorial optimization, Scheduling theory, Worst-case ratio",

author = "Noga Alon and Yossi Azar and Woeginger, \{Gerhard J.\} and Tal Yadid",

year = "1998",

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

language = "English (US)",

volume = "1",

pages = "55--66",

journal = "Journal of Scheduling",

issn = "1094-6136",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Approximation schemes for scheduling on parallel machines

AU - Alon, Noga

AU - Azar, Yossi

AU - Woeginger, Gerhard J.

AU - Yadid, Tal

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.

KW - Approximation algorithm

KW - Approximation scheme

KW - Combinatorial optimization

KW - Scheduling theory

KW - Worst-case ratio

UR - https://www.scopus.com/pages/publications/0012487196

UR - https://www.scopus.com/inward/citedby.url?scp=0012487196&partnerID=8YFLogxK

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

AN - SCOPUS:0012487196

SN - 1094-6136

VL - 1

SP - 55

EP - 66

JO - Journal of Scheduling

JF - Journal of Scheduling

IS - 1

ER -

Approximation schemes for scheduling on parallel machines

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this