Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one
From MaRDI portal
Publication:1761818
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
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
