AN OPTIMAL ALGORITHM FOR PREEMPTIVE ONLINE SCHEDULING

Authors
CHEN B VANVLIET A WOEGINGER GJ
Citation
B. Chen et al., AN OPTIMAL ALGORITHM FOR PREEMPTIVE ONLINE SCHEDULING, Operations research letters, 18(3), 1995, pp. 127-131
Citations number
2
Categorie Soggetti
Operatione Research & Management Science","Operatione Research & Management Science
Journal title
Operations research letters → ACNP
ISSN journal
01676377
Volume
18
Issue
3
Year of publication
1995
Pages
127 - 131
Database
ISI
SICI code
0167-6377(1995)18:3<127:AOAFPO>2.0.ZU;2-5
Abstract
We investigate the problem of on-line scheduling jobs on m identical p arallel machines where preemption is allowed. The goal is to minimize the makespan. We derive an approximation algorithm with worst-case gua rantee m(m)/(m(m) - (m - 1)(m)) for every m greater than or equal to 2 , which increasingly tends to e/(e - 1) approximate to 1.58 as m --> i nfinity. Moreover, we prove that for no m greater than or equal to 2 t here does exist any approximation algorithm with a better worst-case g uarantee.