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

1 April 1983

journal article
Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research

Vol. 31 (2) , 381-386
https://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(n²) algorithm for this problem, generalizing previous results of E. L. Lawler.

Keywords

SCHEDULE
SINGLE MACHINE
PREEMPTIVE
SUPPOSE
LAWLER
PREVIOUS
MINIMIZES THE MAXIMUM