An Algorithm for the Single-Machine Sequencing Problem to Minimize Total Tardiness

Abstract

This paper considers the basic single-machine sequencing problem to minimize total tardiness of all jobs. Using Emmons' well-known theoretical results, certain precedence relations among the jobs are established and used to describe an implicit enumeration scheme which requires only O(n² ) computer storage. Computational experience indicates that the proposed algorithm is more suitable for microcomputers with limited storage capacity than Schrage and Baker's dynamic programming algorithm.