On-line scheduling of small open shops
UNSPECIFIED (2001) On-line scheduling of small open shops. DISCRETE APPLIED MATHEMATICS, 110 (2-3). pp. 133-150. ISSN 0166-218XFull text not available from this repository.
We investigate the problem of on-line scheduling open shops of two and three machines with an objective of minimizing the schedule makespan. We first propose a 1.848-competitive permutation algorithm for the non-preemptive scheduling problem of two machines and show that no permutation algorithm can be better than 1.754-competitive. Secondly, we develop a (27/19)-competitive algorithm for the preemptive scheduling problem of three machines, which is most competitive. (C) 2001 Elsevier Science B.V. All rights reserved.
|Item Type:||Journal Article|
|Subjects:||Q Science > QA Mathematics|
|Journal or Publication Title:||DISCRETE APPLIED MATHEMATICS|
|Publisher:||ELSEVIER SCIENCE BV|
|Date:||15 June 2001|
|Number of Pages:||18|
|Page Range:||pp. 133-150|
Actions (login required)