An optimal algorithm for preemptive on-line scheduling
UNSPECIFIED. (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.
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|
|Journal or Publication Title:||OPERATIONS RESEARCH LETTERS|
|Publisher:||ELSEVIER SCIENCE BV|
|Official Date:||October 1995|
|Number of Pages:||5|
|Page Range:||pp. 127-131|
Actions (login required)
Downloads per month over past year