Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one
DOI10.1007/S10479-011-1055-4zbMATH Open1251.90143DBLPjournals/anor/GafarovLW12OpenAlexW2067283563WikidataQ57633858 ScholiaQ57633858MaRDI QIDQ1761818FDOQ1761818
Evgeny R. Gafarov, Alexander A. Lazarev, Frank Werner
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
Deterministic scheduling theory in operations research (90B35) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Title not available (Why is that?)
- 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
- Maximization problems in single machine scheduling
- Minimizing Total Tardiness on One Machine is NP-Hard
- Algorithms for some maximization scheduling problems on a single machine
- A decomposition algorithm for the single machine total tardiness problem
- Solution of the single machine total tardiness problem
- Flexible solutions in disjunctive scheduling: general formulation and study of the flow-shop case
- A graphical realization of the dynamic programming method for solving NP-hard combinatorial problems
- A branch and bound algorithm to minimize total weighted tardiness on a single processor
- A special case of the single-machine total tardiness problem is NP-hard
- 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
- The Pareto-optimal set of the NP-hard problem of minimization of the maximum lateness for a single machine
Cited In (6)
- 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
- Minimizing total weighted tardiness for scheduling equal-length jobs on a single machine
- Mirror scheduling problems with early work and late work criteria
- A new effective dynamic program for an investment optimization problem
- Graphical method to solve combinatorial optimization problems
Recommendations
- 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 fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date 👍 👎
- A polynomial-time approximation scheme for maximizing the minimum machine completion time 👍 👎
- The single-machine total tardiness scheduling problem: review and extensions 👍 👎
- A hybrid algorithm for the single-machine total tardiness problem 👍 👎
- A faster fully polynomial approximation scheme for the single-machine total tardiness problem 👍 👎
- On polynomial solvability of the high multiplicity total weighted tardiness problem 👍 👎
- A Fully Polynomial Approximation Scheme for Scheduling a Single Machine to Minimize Total Weighted Late Work 👍 👎
- Title not available (Why is that?) 👍 👎
This page was built for publication: Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1761818)
