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

DOI10.1007/s10479-011-1055-4zbMath1251.90143OpenAlexW2067283563WikidataQ57633858 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

schedulingpolynomial algorithmtotal tardinessmaximization problemssingle machine problems

Mathematics Subject Classification ID

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

Related Items (6)

Minimizing total weighted tardiness for scheduling equal-length jobs on a single machine ⋮ 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 ⋮ Mirror scheduling problems with early work and late work criteria ⋮ Maximizing total tardiness on a single machine in \(O(n^2)\) time via a reduction to half-product minimization

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

This page was built for publication: Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one