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

DOI10.1007/S10479-011-1055-4MaRDI QIDQ1761818zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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

schedulingtotal tardinesspolynomial algorithmmaximization problemssingle machine problems

Mathematics Subject Classification ID

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

Recommendations

• A faster fully polynomial approximation scheme for the single-machine total tardiness problem
• Publication:4944729
• A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date
• Single machine total tardiness maximization problems: complexity and algorithms
• A Fully Polynomial Approximation Scheme for Scheduling a Single Machine to Minimize Total Weighted Late Work
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• A hybrid algorithm for the single-machine total tardiness problem
• Maximizing total tardiness on a single machine in O(n^2) time via a reduction to half-product minimization
• The single-machine total tardiness scheduling problem: review and extensions
• On polynomial solvability of the high multiplicity total weighted tardiness problem

Cites work

• scientific article; zbMATH DE number 3550186 (Why is no real title available?)
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems
• A branch and bound algorithm to minimize total weighted tardiness on a single processor
• A controlled search simulated annealing method for the single machine weighted tardiness problem
• A decomposition algorithm for the single machine total tardiness problem
• A graphical realization of the dynamic programming method for solving NP-hard combinatorial problems
• A special case of the single-machine total tardiness problem is NP-hard
• 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
• 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
• Minimizing Total Tardiness on One Machine is NP-Hard
• Reducibility among single machine weighted completion time scheduling problems
• Solution of the single machine total tardiness problem
• The Pareto-optimal set of the NP-hard problem of minimization of the maximum lateness for a single machine

Cited in

(7)

• 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
• Algorithms for some maximization scheduling problems 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

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)