Abstract
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 ¿ 8. Moreover, we prove that for no m 2 there does exist any approximation algorithm with a better worst-case guarantee.
Original language | English |
---|---|
Pages (from-to) | 127-131 |
Number of pages | 5 |
Journal | Operations Research Letters |
Volume | 18 |
Issue number | 3 |
DOIs | |
Publication status | Published - 1995 |