Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one

DOI10.1007/s10479-011-1055-4zbMath1251.90143WikidataQ57633858 ScholiaQ57633858MaRDI QIDQ1761818

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

Publication date: 15 November 2012

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

Full work available at URL: https://doi.org/10.1007/s10479-011-1055-4

zbMATH Keywords

scheduling; polynomial algorithm; total tardiness; maximization problems; single machine problems

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90B35: Deterministic scheduling theory in operations research

Related Items

Maximizing total tardiness on a single machine in \(O(n^2)\) time via a reduction to half-product minimization, Single machine total tardiness maximization problems: complexity and algorithms, A new effective dynamic program for an investment optimization problem, Graphical method to solve combinatorial optimization problems, Minimizing total weighted tardiness for scheduling equal-length jobs on a single machine, Mirror scheduling problems with early work and late work criteria

Cites Work

• Unnamed Item
• Maximization problems in single machine scheduling
• A branch and bound algorithm to minimize total weighted tardiness on a single processor
• Algorithms for some maximization scheduling problems on a single machine
• Algorithms for special cases of the single machine total tardiness problem and an application to the even-odd partition problem
• A controlled search simulated annealing method for the single machine weighted tardiness problem
• Reducibility among single machine weighted completion time scheduling problems
• A graphical realization of the dynamic programming method for solving NP-hard combinatorial problems
• Flexible solutions in disjunctive scheduling: general formulation and study of the flow-shop case
• Solution of the single machine total tardiness problem
• A decomposition algorithm for the single machine total tardiness problem
• A special case of the single-machine total tardiness problem is NP-hard
• The Pareto-optimal set of the NP-hard problem of minimization of the maximum lateness for a single machine
• Minimizing Total Tardiness on One Machine is NP-Hard
• Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of computational complexity
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems