A special case of the single-machine total tardiness problem is NP-hard

DOI10.1134/S1064230706030117zbMath1260.93116OpenAlexW2621839118MaRDI QIDQ1946412

Alexander A. Lazarev, Evgeny R. Gafarov

Publication date: 12 April 2013

Published in: Journal of Computer and Systems Sciences International (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s1064230706030117

Mathematics Subject Classification ID

Control/observation systems involving computers (process control, etc.) (93C83)

Related Items (8)

Algorithms for some maximization scheduling problems on a single machine ⋮ A hybrid algorithm for the single-machine total tardiness problem ⋮ Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one ⋮ Single machine scheduling problems with financial resource constraints: some complexity results and properties ⋮ Algorithms for special cases of the single machine total tardiness problem and an application to the even-odd partition problem ⋮ Metric approach for finding approximate solutions of scheduling problems ⋮ A note on a single machine scheduling problem with generalized total tardiness objective function ⋮ The single-machine total tardiness scheduling problem: review and extensions

Cites Work

• Unnamed Item
• Unnamed Item
• Solution of the single machine total tardiness problem
• A decomposition algorithm for the single machine total tardiness problem
• 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
• Algorithmic paradoxes of the single-machine total tardiness problem

This page was built for publication: A special case of the single-machine total tardiness problem is NP-hard