Single machine total tardiness maximization problems: complexity and algorithms

DOI10.1007/S10479-012-1288-XMaRDI QIDQ367638zbMATHOpenAlexWikidataFDO

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)

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