Joint seminar with the Algorithms Research Group (ARG).

Title: Ideal Preemptive Schedules on Two Processors

An ideal schedule minimizes both maximum completion time and total completion time. It is known that the Coffman-Graham algorithm [Acta Informatica 1, 200a-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 completion time has been open. In conclusion, we discuss the fractionality conjecture (that m-machine preemptive problems of minimizing regular criteria have solutions of fractionality 1/m) and the NP-preemption hypothesis (that the decision versions of preemptive problems of minimizing regular criteria are in NP), which remain unverified.
Joint work with E.G. Coffman, Jr. and J. Sethuraman.