Asymmetric Weighted Earliness-Tardiness: Scheduling with a Nonrestrictive Common Due Date
Abstract
Single-machine asymmetric weighted earliness--tardiness (AWET) scheduling asks how to sequence jobs around a common synchronization date when early and late completion incur unrelated job-dependent penalties. At the boundary nonrestrictive date d=∑jpj, a compact V-shaped schedule reduces the continuous-time problem to a quadratic choice of a nonempty early set. We establish four complementary results for this model. First, the positive-integer problem is strongly NP-complete by a unary-polynomial reduction from Restricted Exact Cover by 3-Sets. Second, unrestricted AWET admits a polynomial-time (3+2√2+ε)-approximation based on an anchored semidefinite relaxation and deterministic marginal thresholding. Third, when the earliness and tardiness ratio orders are strict reversals, the problem is weakly NP-complete but has an exact two-resource pseudopolynomial dynamic program. Fourth, for fixed total refinements whose ratio permutation is separable, an exact separating-tree recurrence and coordinated geometric trimming yield an FPTAS. The proofs use different manifestations of the same canonical objective: scale-separated prefix penalties, positive-semidefinite minimum-kernel covariance, a dominant completed load square, and a bounded four-coordinate decomposition interface. Together, the results show that the decisive issue is not merely whether the two ratio orders agree, but whether their interaction can be controlled by a global certificate or compressed into a bounded constructive interface.
Related
- Strong NP-Hardness and Approximation Algorithm for Weighted Tardiness with Release Dates and Identical Processing Times
- Online Packet Scheduling with Deadlines and Learning
- Optimal Uniform-like Scheduling of Maintenance
- Dropout Universality: Scaling Laws and Optimal Scheduling at the Edge-of-Chaos
- DynaSPLIT: Strong tail-optimal scheduling for the M/G/n with heavy-tailed job sizes
BibTeX
@misc{hall2026asymmetric,
title = {{Asymmetric Weighted Earliness-Tardiness: Scheduling with a Nonrestrictive Common Due Date}},
author = {Nicholas G. Hall and Hans Kellerer and Miao Song},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.16046},
eprint = {2609.16046},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.16046},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Asymmetric Weighted Earliness-Tardiness: Scheduling with a Nonrestrictive Common Due Date
AU - Nicholas G. Hall
AU - Hans Kellerer
AU - Miao Song
PY - 2026
DA - 2026/09/12
PB - arXiv
DO - 10.48550/arxiv.2609.16046
UR - https://arxiv.org/abs/2609.16046
AB - Single-machine asymmetric weighted earliness--tardiness (AWET) scheduling asks how to sequence jobs around a common synchronization date when early and late completion incur unrelated job-dependent penalties. At the boundary nonrestrictive date d=∑_jp_j, a compact V-shaped schedule reduces the continuous-time problem to a quadratic choice of a nonempty early set. We establish four complementary results for this model. First, the positive-integer problem is strongly NP-complete by a unary-polynomial reduction from Restricted Exact Cover by 3-Sets. Second, unrestricted AWET admits a polynomial-time (3+2√2+ε)-approximation based on an anchored semidefinite relaxation and deterministic marginal thresholding. Third, when the earliness and tardiness ratio orders are strict reversals, the problem is weakly NP-complete but has an exact two-resource pseudopolynomial dynamic program. Fourth, for fixed total refinements whose ratio permutation is separable, an exact separating-tree recurrence and coordinated geometric trimming yield an FPTAS. The proofs use different manifestations of the same canonical objective: scale-separated prefix penalties, positive-semidefinite minimum-kernel covariance, a dominant completed load square, and a bounded four-coordinate decomposition interface. Together, the results show that the decisive issue is not merely whether the two ratio orders agree, but whether their interaction can be controlled by a global certificate or compressed into a bounded constructive interface.
ER -