1994
An optimal algorithm for preemptive on-line scheduling
Publication
Publication
We investigate the problem of on-line scheduling jobs on m identical parallel machines where preemption is allowed. The goal is to minimize the makespan. We derive an approximation algorithm with worst case guarantee mm/(mm−(m−1)m) for every m≥2, which increasingly tends to e/(e−1)≈1.58 as m→∞. Moreover, we prove that for no m≥2 there does exist any approximation algorithm with a better worst case guarantee.
| Additional Metadata | |
|---|---|
| doi.org/10.1016/0167-6377(95)00039-9, hdl.handle.net/1765/100284 | |
| Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | |
| Organisation | Department of Econometrics |
|
Chen, B., van Vliet, A., & Woeginger, G. (1994). An optimal algorithm for preemptive on-line scheduling. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). doi:10.1016/0167-6377(95)00039-9 |
|
