{"id":"arxiv/2609.16046","url":"https://arxiv.org/abs/2609.16046","tags":["math.OC","cs.CC","cs.DM","math.CO"],"score":0,"title":"Asymmetric Weighted Earliness-Tardiness: Scheduling with a Nonrestrictive Common Due Date","domain":"math.OC","source":"arxiv","authors":["Nicholas G. Hall","Hans Kellerer","Miao Song"],"reviews":0,"subject":"math.OC","summary":"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=\\sum_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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-12","reactions":{}}