Dynamic programming and decomposition approaches for the single machine total tardiness problem. (English) Zbl 0627.90055

The problem of sequencing jobs on a single machine to minimize total tardiness is considered. General precedence constrained dynamic programming algorithms and special-purpose decomposition algorithms are presented. Computational results for problems with up to 100 are given.


90B35 Deterministic scheduling theory in operations research
90C39 Dynamic programming
65K05 Numerical mathematical programming methods
Full Text: DOI


[1] Elmaghraby, S. E., The one-machine sequencing problem with delay costs, Journal of Industrial Engineering, 19, 105-108 (1968)
[2] Emmons, H., One-machine sequencing to minimize certain functions of job tardiness, Operations Research, 17, 701-715 (1969) · Zbl 0176.50005
[3] Fisher, M. L., A dual algorithm for the one-machine scheduling problem, Mathematical Programming, 11, 229-251 (1976) · Zbl 0359.90039
[4] Kao, E. P.C.; Queyranne, M., On dynamic programming methods for assembly line balancing, Operations Research, 30, 375-390 (1982) · Zbl 0481.90043
[5] Lawler, E. L., A ‘pseudopolynomial’ algorithm for sequencing jobs to minimize total tardiness, Annals of Discrete Mathematics, 1, 331-342 (1977) · Zbl 0353.68071
[6] Lawler, E. L., Efficient implementation of dynamic programming algorithms for sequencing problems, (Report BW 106 (1979), Mathematisch Centrum: Mathematisch Centrum New York) · Zbl 0416.90036
[7] Lawler, E. L., A fully polynomial approximation scheme for the total tardiness problem, Operations Research Letters, 1, 207-208 (1982) · Zbl 0511.90074
[8] Picard, J. C.; Queyranne, M., The time dependent traveling salesman problem and applications to the tardiness problem in one-machine sequencing, Operations Research, 26, 88-110 (1978) · Zbl 0371.90066
[9] Pots, C. N.; Van Wassenhove, L. N., A decomposition algorithm for the single machine total tardiness problem, Operations Research Letters, 1, 177-181 (1982) · Zbl 0508.90045
[10] Rinnooy Kan, A. H.G.; Lageweg, B. J.; Lenstra, J. K., Minimizing total costs in one-machine scheduling, Operations Research, 23, 908-927 (1975) · Zbl 0324.90039
[11] Schrage, L.; Baker, K. R., Dynamic programming solution of sequencing problems with precedence constraints, Operations Research, 26, 444-449 (1978) · Zbl 0383.90054
[12] Sen, T. T.; Austin, L. N.; Ghandforoush, P., An algorithm for the single-machine sequencing problem to minimize total tardiness, IEE Transactions, 15, 363-366 (1983)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.