Preemptive Scheduling of a Single Machine to Minimize Maximum Cost Subject to Release Dates and Precedence Constraints

K. R. Baker, E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan

Operations Research · 1983 · Volume 31 · Issue 2

Abstract

Suppose n jobs are to be processed on a single machine, subject to release dates and precedence constraints. The problem is to find a preemptive schedule which minimizes the maximum job completion cost. We present an O ( n 2 ) algorithm for this problem, generalizing previous results of E. L. Lawler.

Keywords

432 computational complexity, 584 single machine scheduling

Enable JavaScript for citation tools and additional paper interactions.