We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Ideal preemptive schedules on two processors.
- Authors
Coffman, Jr., E. G.; Scthuraman, J.; Timkovsky, V. G.
- Abstract
An ideal schedule minimizes both makespan and total flow time. It is known that the Coffman-Graham algorithm [Acta Informatica 1,2002-13, 1972] solves in polynomial time the problem of finding an ideal nonpreemptive schedule of unit-execution-time jobs with equal release dates and arbitrary precedence constraints on two identical parallel processors. This paper presents an extension of the algorithm that solves in polynomial time the preemptive counterpart of this problem. The complexity status of the preemptive problem of minimizing just the total flow time has been open.
- Subjects
ALGORITHMS; POLYNOMIALS; ALGEBRA; COMPUTER algorithms
- Publication
Acta Informatica, 2003, Vol 39, Issue 8, p597
- ISSN
0001-5903
- Publication type
Article
- DOI
10.1007/s00236-003-0119-6