Principles of Sequencing and Scheduling, 2nd Edition

5Earliness and Tardiness Costs

5.1 Introduction

In earlier chapters, we examined the basic single‐machine model with regular measures of performance, which are nondecreasing in job completion times. Most of the literature on scheduling theory, and therefore much of our understanding of scheduling problems, relates to such regular measures as total flowtime, number of tardy jobs, and total tardiness. The total tardiness criterion, in particular, has been a standard way of measuring conformance to due dates, although it ignores the consequences of jobs completing early and penalizes only those jobs that finish late. However, this emphasis began to change with the growing interest in just‐in‐time (JIT) production, which espouses the notion that earliness – as well as tardiness – should be discouraged. In a JIT scheduling environment, a job that completes early must be held in inventory until its due date, whereas a job that completes after its due date may disrupt a customer’s operations. Therefore, an ideal schedule is one in which all jobs finish exactly on their assigned due dates. Of course, JIT encompasses a much broader set of principles than those relating to due dates, but scheduling models with both earliness and tardiness (E/T) costs address a fundamental scheduling dimension of the JIT approach.

In this chapter, we examine the implications of the E/T criterion in the basic single‐machine model. The goal of finishing all jobs exactly on their due dates can be translated ...