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

1 December 1983

journal article
research article
Published by Taylor & Francis in IIE Transactions

Vol. 15 (4) , 363-366
https://doi.org/10.1080/05695558308974660

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.

Keywords

This publication has 7 references indexed in Scilit:

Combinatorial Problems: Reductibility and Approximation
Operations Research, 1978
Dynamic Programming Solution of Sequencing Problems with Precedence Constraints
Operations Research, 1978
Finding an Optimal Sequence by Dynamic Programming: An Extension to Precedence-Related Tasks
Operations Research, 1978
A dual algorithm for the one-machine scheduling problem
Mathematical Programming, 1976
A hybrid algorithm for the one machine sequencing problem to minimize total tardiness
Naval Research Logistics Quarterly, 1971
One-Machine Sequencing to Minimize Certain Functions of Job Tardiness
Operations Research, 1969
On Scheduling Problems with Deferral Costs
Management Science, 1964