Preemptive Scheduling of a Single Machine to Minimize Maximum Cost Subject to Release Dates and Precedence Constraints
Published Online:1 Apr 1983https://doi.org/10.1287/opre.31.2.381
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(n2) algorithm for this problem, generalizing previous results of E. L. Lawler.
