An optimal algorithm for preemptive on-line scheduling
Chen, Bo, Dr., van Vliet, André and Woeginger, Gerhard J.. (1995) An optimal algorithm for preemptive on-line scheduling. Operations Research Letters, 18 (3). pp. 127-131. ISSN 0167-6377Full text not available from this repository.
Official URL: http://dx.doi.org/10.1016/0167-6377(95)00039-9
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 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 --> infinity. Moreover, we prove that for no m greater than or equal to 2 there does exist any approximation algorithm with a better worst-case guarantee.
|Item Type:||Journal Article|
|Subjects:||H Social Sciences > HD Industries. Land use. Labor > HD28 Management. Industrial Management|
|Divisions:||Faculty of Social Sciences > Warwick Business School > Operational Research & Management Sciences
Faculty of Social Sciences > Warwick Business School
|Journal or Publication Title:||Operations Research Letters|
|Official Date:||October 1995|
|Number of Pages:||5|
|Page Range:||pp. 127-131|
Actions (login required)