The Library
An optimal algorithm for preemptive on-line scheduling
Tools
Tools
Tools
Chen, Bo, van Vliet, André and Woeginger, Gerhard J. (1995) An optimal algorithm for preemptive on-line scheduling. Operations Research Letters, 18 (3). pp. 127-131. doi:10.1016/0167-6377(95)00039-9 ISSN 0167-6377.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/0167-6377(95)00039-9
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 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 | ||||
| Publisher: | Elsevier BV | ||||
| ISSN: | 0167-6377 | ||||
| Official Date: | October 1995 | ||||
| Dates: |
|
||||
| Volume: | 18 | ||||
| Number: | 3 | ||||
| Number of Pages: | 5 | ||||
| Page Range: | pp. 127-131 | ||||
| DOI: | 10.1016/0167-6377(95)00039-9 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
