Single machine total tardiness maximization problems: complexity and algorithms

DOI10.1007/S10479-012-1288-XMaRDI QIDQ367638zbMATH OpenOpenAlexWikidataFDO

Authors Evgeny R. Gafarov, Frank Werner, Alexander A. Lazarev

Publication date 16 September 2013

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10479-012-1288-x

zbMATH Keywords

dynamic programmingcomplexityschedulingsingle machine maximization problems

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Algorithms for some maximization scheduling problems on a single machine
• A branch and bound algorithm to minimize total weighted tardiness on a single processor
• Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one
• Maximization problems in single machine scheduling
• On the single machine total tardiness problem

Cites work

• scientific article; zbMATH DE number 3550182 (Why is no real title available?)
• scientific article; zbMATH DE number 3550186 (Why is no real title available?)
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems
• Algorithms for some maximization scheduling problems on a single machine
• Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of computational complexity
• Flexible solutions in disjunctive scheduling: general formulation and study of the flow-shop case
• Maximization problems in single machine scheduling
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one

Cited in

(19)

• Maximizing total tardiness on a single machine in O(n^2) time via a reduction to half-product minimization
• A note on reverse scheduling with maximum lateness objective
• Research on permutation flow shop scheduling problems with general position-dependent learning effects
• Maximization problems in single machine scheduling
• Finding the Pareto-optima for the total and maximum tardiness single machine problem
• Single-machine primary-secondary scheduling with total tardiness being the primary criterion
• The single-machine absolute-deviation early-tardy problem with random completion times
• A note on the single-machine scheduling problem with minimum weighted completion time and maximum allowable tardiness
• New insights on the single machine total tardiness problem
• Two scheduling problems of minimizing the maximum weighted completion time
• Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one
• On the complexity of the single machine scheduling problem minimizing total weighted delay penalty
• On the single machine total tardiness problem
• Insights into two solution procedures for the single machine tardiness problem
• Decomposition of the single machine total tardiness problem
• Minimizing total weighted tardiness for scheduling equal-length jobs on a single machine
• Algorithms for some maximization scheduling problems on a single machine
• An exact exponential branch-and-merge algorithm for the single machine total tardiness problem
• Dynamic programming and decomposition approaches for the single machine total tardiness problem

This page was built for publication: Single machine total tardiness maximization problems: complexity and algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q367638)