Ideal preemptive schedules on two processors

An ideal schedule minimizes both makespan and total flow time. It is known that the Coffman-Graham algorithm [Acta Informatica 1, 200-213, 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.

Authors and Affiliations

1. Department of Electrical Engineering, Columbia University, NY 10027, New York, USA

   E. G. Coffman

2. Department of Industrial Engineering & Operations Research, Columbia University, NY 10027, New York, USA

   J. Sethuraman

3. Department of Industrial Engineering & Operations Research, CGI Group Inc., 1 Dundas St. W.,Ste. 2700, Toronto, Ontario M5L, Canada 1G1

   V. G. Timkovsky

4. Department of Computing & Software, McMaster University, L8S 4L7, Hamilton, Ontario, Canada

   V. G. Timkovsky

Corresponding author

Correspondence to E. G. Coffman.

Received: 2 May 2003,

J. Sethuraman: Research supported by an NSF CAREER Award DMI-0093981 and an IBM Faculty Partnership Award.

Reprints and permissions