Optimal Single-Machine Scheduling with Earliness and Tardiness Penalties

Abstract

We consider a single-machine job shop scheduling problem in which penalties occur for jobs that either commence before their target start times or are completed after their due dates. The objective is to minimize the maximum penalty, subject to restrictive assumptions on the target start times, the due dates, and the penalty functions. We present an algorithm for solving this problem, along with a method for generating alternative optima. The algorithm is generalized to cover the case in which the machine is available for only a limited time span.