A faster fully polynomial approximation scheme for the single-machine total tardiness problem

DOI10.1016/j.ejor.2007.12.031zbMath1157.90419OpenAlexW1976596296MaRDI QIDQ958114

Christos P. Koulamas

Publication date: 2 December 2008

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2007.12.031

zbMATH Keywords

total tardinesssingle-machine sequencingfully polynomial approximation

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (4)

Distributionally robust single machine scheduling with the total tardiness criterion ⋮ A strongly polynomial FPTAS for the symmetric quadratic knapsack problem ⋮ The single-machine total tardiness scheduling problem: review and extensions ⋮ Approximation algorithms and an FPTAS for the single machine problem with biased tardiness penalty

Cites Work

• Unnamed Item
• Some remarks on the decomposition properties of the single machine total tardiness problem
• A decomposition algorithm for the single machine total tardiness problem
• A fully polynomial approximation scheme for the total tardiness problem
• Improving the complexities of approximation algorithms for optimization problems
• On decomposition of the total tardiness problem
• Minimizing Total Tardiness on One Machine is NP-Hard
• Lower bounds on the approximation ratios of leading heuristics for the single-machine total tardiness problem

This page was built for publication: A faster fully polynomial approximation scheme for the single-machine total tardiness problem