Strong NP-Hardness and Approximation Algorithm for Weighted Tardiness with Release Dates and Identical Processing Times
Abstract
We study nonpreemptive scheduling on a single machine with release dates, due dates, positive job weights, and a common processing time. The objective is to minimize total weighted tardiness. Although closely related equal-processing-time problems admit polynomial-time algorithms, the complexity of this problem has remained open in the literature since 2010. We prove that its decision version is strongly NP-complete, even when every job can meet its due date if processed immediately upon release. The reduction is from unweighted MAX-CUT and uses a quadratic number of jobs with polynomially bounded numerical data. Its main ingredient is a constructive normalization theorem that converts every sufficiently inexpensive feasible schedule into a binary choice for each graph vertex; after normalization, total weighted tardiness equals a constant minus a scaled cut value. We also give a deterministic polynomial-time phase-grid assignment algorithm for the shifted objective Φ=F+p∑jwj, where F is total weighted tardiness. The algorithm enumerates at most N release-date residues modulo p, solves one minimum-cost assignment problem for each residue, and returns the best phase-grid schedule. It runs in O(N5) arithmetic operations and achieves the tight ratio $3/2-1/(2N)$ for this algorithm. Because the added term p∑jwj is independent of how the jobs are scheduled, the shifted and original objectives have exactly the same optimal schedules. However, the approximation guarantee applies to the shifted objective; for the original objective, the analysis provides an additive bound. Thus, the paper both resolves the long-standing complexity question and provides a complementary worst-case guarantee for the phase-grid assignment algorithm.
Related
- NP-hardness of additive approximation for generalized Turán problems
- A tight 1/3-approximation algorithm and fully polynomial-time approximation schemes for the Colored Knapsack Problem
- Approximation algorithm for mixed volumes of a constant number of convex bodies
- A Fast Algorithm for Quaternion Tensor Singular Value Decomposition under the QT-Product with Applications to Color Video Processing
- The best approximation tuple: an extension of the Cheney-Goldstein algorithm and results to the multiple sets case
BibTeX
@misc{chen2026strong,
title = {{Strong NP-Hardness and Approximation Algorithm for Weighted Tardiness with Release Dates and Identical Processing Times}},
author = {Zhi-Long Chen and Nicholas G. Hall},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.28751},
eprint = {2609.28751},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.28751},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Strong NP-Hardness and Approximation Algorithm for Weighted Tardiness with Release Dates and Identical Processing Times
AU - Zhi-Long Chen
AU - Nicholas G. Hall
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.28751
UR - https://arxiv.org/abs/2609.28751
AB - We study nonpreemptive scheduling on a single machine with release dates, due dates, positive job weights, and a common processing time. The objective is to minimize total weighted tardiness. Although closely related equal-processing-time problems admit polynomial-time algorithms, the complexity of this problem has remained open in the literature since 2010. We prove that its decision version is strongly NP-complete, even when every job can meet its due date if processed immediately upon release. The reduction is from unweighted MAX-CUT and uses a quadratic number of jobs with polynomially bounded numerical data. Its main ingredient is a constructive normalization theorem that converts every sufficiently inexpensive feasible schedule into a binary choice for each graph vertex; after normalization, total weighted tardiness equals a constant minus a scaled cut value. We also give a deterministic polynomial-time phase-grid assignment algorithm for the shifted objective Φ=F+p∑_jw_j, where F is total weighted tardiness. The algorithm enumerates at most N release-date residues modulo p, solves one minimum-cost assignment problem for each residue, and returns the best phase-grid schedule. It runs in O(N^5) arithmetic operations and achieves the tight ratio $3/2-1/(2N)$ for this algorithm. Because the added term p∑_jw_j is independent of how the jobs are scheduled, the shifted and original objectives have exactly the same optimal schedules. However, the approximation guarantee applies to the shifted objective; for the original objective, the analysis provides an additive bound. Thus, the paper both resolves the long-standing complexity question and provides a complementary worst-case guarantee for the phase-grid assignment algorithm.
ER -