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