Dynamic programming and decomposition approaches for the single machine total tardiness problem
type: Item
instance of: scholarly article
title: Dynamic programming and decomposition approaches for the single machine total tardiness problem
zbMATH Open document ID: 0627.90055
DOI: 10.1016/S0377-2217(87)80008-5
published in: European Journal of Operational Research
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C39
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 4020834
zbMATH Keywords: sequencing
zbMATH Keywords: single machine
zbMATH Keywords: total tardiness
zbMATH Keywords: precedence constrained
zbMATH Keywords: decomposition
zbMATH Keywords: Computational results
author: Chris N. Potts
author: Luk N. Van Wassenhove
MaRDI profile type: Publication
cites work: One-Machine Sequencing to Minimize Certain Functions of Job Tardiness
cites work: A dual algorithm for the one-machine scheduling problem
cites work: On Dynamic Programming Methods for Assembly Line Balancing
cites work: Q4124332
cites work: Q3206647
cites work: A fully polynomial approximation scheme for the total tardiness problem
cites work: The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling
cites work: A decomposition algorithm for the single machine total tardiness problem
cites work: Minimizing Total Costs in One-Machine Scheduling
cites work: Dynamic Programming Solution of Sequencing Problems with Precedence Constraints
Recommended article: Decomposition of the single machine total tardiness problem
Recommended article: A new decomposition approach for the single machine total tardiness scheduling problem
Recommended article: Single machine total tardiness maximization problems: complexity and algorithms
Recommended article: Some remarks on the decomposition properties of the single machine total tardiness problem
Recommended article: Minimizing total tardiness in a stochastic single machine scheduling problem using approximate dynamic programming
Recommended article: On the single machine total tardiness problem
Recommended article: The single-machine total tardiness scheduling problem: review and extensions
Recommended article: A hybrid algorithm for the single-machine total tardiness problem
Recommended article: New insights on the single machine total tardiness problem
Recommended article: Solution of the single machine total tardiness problem
description: scientific article; zbMATH DE number 4020834