PaperlayerView exact revision on arXiv

Source-linked AI summary

Strong NP-Hardness and Approximation Algorithm for Weighted Tardiness with Release Dates and Identical Processing Times

Zhi-Long Chen, Nicholas G. Hall

arXiv:2609.28751v1cs.CCcs.DMmath.CO

TL;DR

The complexity question for single-machine weighted tardiness with release dates and a common processing time had been documented in prior work. The paper combines a normalization-based MAX-CUT hardness proof with a phase-grid assignment algorithm. It establishes strong NP-completeness even when every job can meet its due date if processed immediately upon release, and gives the algorithm a tight 3/2-1/(2N) approximation ratio.

  • Problem

    The complexity question for single-machine total weighted tardiness with release dates and identical processing times had been documented in prior work.

    Source: §1 · p. 3, §7 · p. 35

  • Method

    The paper uses normalization to derive a MAX-CUT cost identity and develops a deterministic phase-grid algorithm solving at most N minimum-cost assignment problems.

    Source: §7 · p. 35

  • Results

    The scheduling problem is strongly NP-complete even when every job can meet its due date if processed immediately upon release, and the specified algorithm has a tight 3/2-1/(2N) approximation ratio.

    Source: §1 · p. 3, §7 · p. 35

  • Takeaways & Limitations

    The paper resolves the documented complexity question while providing a complementary phase-grid guarantee for the scheduling problem.

    Source: §7 · p. 35

    The hardness construction uses Δe as construction parameters rather than zero, negative, or arbitrary real coefficients, and the algorithm lacks a multiplicative guarantee for ordinary total weighted tardiness.

    Source: §5 · p. 28, §7 · p. 36

Abstract

from arXiv · show

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 $\Phi=F+p\sum_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\sum_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.

1 Introduction

The paper resolves an open complexity question for weighted tardiness with release dates and identical processing times, proving strong NP-completeness. It also presents a phase-grid assignment algorithm with a guarantee for a shifted objective.

1 Introduction

  • The problem's complexity had remained open in the literature, despite polynomial-time algorithms for related equal-processing-time due-date objectives.The cited related problems include unweighted total tardiness and weighted number of tardy jobs.Source: §1 · p. 3
  • The decision problem is strongly NP-complete even when each job can meet its due date if processed immediately at release, with polynomially bounded numerical parameters.This settles the published open question for the problem.Source: §1 · p. 3
  • A constructive normalization converts every sufficiently inexpensive schedule into a binary choice per vertex, enabling an exact pairwise cost identity that encodes MAX-CUT.The reduction represents vertices with blocks of equal-length jobs and uses additional jobs to enforce block timing.Source: §1 · pp. 3–4
  • The deterministic phase-grid algorithm tests at most N release-date residues, rounds releases to each grid, and solves a minimum-cost assignment for each.It retains the best schedule across the assignments.Source: §1 · p. 4
  • For the original objective, the analysis provides an additive guarantee, not a constant multiplicative approximation.The shift preserves schedule ordering and minimizers, but the guarantee is stated for the shifted objective.Source: §1 · p. 4

2 Related literature

Related work identifies tractable equal-processing-time scheduling variants, while the complexity of weighted tardiness with release dates remained open. The paper resolves that question and positions a phase-grid assignment algorithm alongside existing exact and grid-based methods.

2 Related literature

  • The paper surveys complexity results surrounding equal-processing-time weighted tardiness in Table 1.The supplied caption identifies the table’s scope, not its individual results.Source: §2 · p. 4, Table 1 · p. 5

2.1 Complexity results

  • Strongly polynomial algorithms exist for nearby equal-length objectives, but weighted tardiness with release dates had remained open.The paper proves strong NP-hardness even when d_j ≥ r_j + p.Source: §2.1 · pp. 5–6

2.2 Exact, heuristic, and grid-based algorithms

  • Earlier exact algorithms for equal-processing-time weighted tardiness use exponential enumeration, whereas the proposed approach tests at most N release phases.It solves an assignment problem for each residue phase and compares the phase optima.Source: §2.2 · p. 7

2.3 Shifted-objective performance guarantees

  • A schedule-independent shift can change the approximation ratio, so the guarantee must be stated for the translated objective.The paper distinguishes this guarantee from an ordinary multiplicative approximation for unshifted tardiness.Source: §2.3 · p. 8

2.4 Position of our result

  • Strong NP-hardness is proved for one machine with equal job lengths, arbitrary release dates, and weighted tardiness.The result settles a question left open since 2010, even under d_j ≥ r_j + p.Source: §2.1 · p. 6, §2.4 · p. 8
  • The construction adds normalization for bounded-cost witnesses and independently encodes positive edge coefficients.The paper also identifies phase-averaging analysis as a new contribution.Source: §2.4 · p. 8

3 Reduction from unweighted MAX-CUT

The reduction from unweighted MAX-CUT encodes vertex-side choices as equal-processing-time job schedules, with parameter bounds enforcing vertex blocks and tail tardiness savings tied to cut edges; left-shifting supports integral schedules. It establishes a reference schedule of cost K and a lower threshold K* for evaluating cut-dependent schedules.

3 Reduction from unweighted MAX-CUT

  • Left-shifting any feasible schedule to its earliest schedule preserves feasibility, gives integer start times, and cannot increase cost, even from noninteger starts.Thus the minimum over finitely many earliest job permutations attains the optimum.Source: §3 · p. 9
  • Each normalized vertex block chooses one of two incidence jobs, and the postponed jobs’ tail tardiness decreases exactly when an edge’s endpoints choose different sides.The parameter inequalities force the intended block structure for schedules below the reference bound; Section 4 transforms these schedules to canonical form.Source: §3 · p. 9

3.1 Source instance and job data

  • The construction starts from MAX-CUT on an unweighted simple graph and creates 2n² equal-processing-time jobs, including a pair for each incidence plus charge and guard jobs.It uses an auxiliary complete graph, although MAX-CUT counts only original edges and all auxiliary edges participate in the scheduling construction.Source: §3.1 · pp. 9, 10, 13

3.2 Bounds needed for the schedule argument

  • The parameter bounds include (2P + 1) > K and UL > V (2M + 1)P + Fsum, ensuring the intended blocks for schedules below the reference bound.The inequalities are stated in Lemma 1 and used in the schedule argument.Source: §3 · p. 9, §3.2 · p. 13
  • Every A/B-job has due date at least its release time plus P, with equality for charge and guard jobs.The passage states this bound for the constructed instance; the reference schedule’s charge and guard jobs meet their due dates.Source: §3.2 · p. 15
  • The reference schedule supplies a feasible-cost baseline from which later cut-dependent savings are measured, rather than claiming optimality.Its role is to show the constructed instance has a feasible schedule costing at most K and that the schedules considered in the normalization argument are nonempty.Source: §3.2 · p. 15
  • The reference schedule interleaves A-jobs, charge jobs, and guards, with one unit of idle time before each guard; guards finish by H, and B-jobs form the tail after H.All A-jobs, charge jobs, and guard jobs are on time.Source: §3.2 · p. 15
  • The complete reference schedule proves OPT ≤ K, while K* = K − (P/2)Γκ is the decision threshold, not the reference schedule’s cost or necessarily the optimum.Schedules may meet or improve on K* by choosing different modes at different vertices.Source: §3.2 · p. 16

4 Schedule normalization

Section 4 shows that bounded-cost feasible schedules can be normalized in polynomial time, without increasing cost, into canonical schedules that select one early job per pair, use a consistent A- or B-mode at each vertex, and order the tail by weight.

4 Schedule normalization

  • Every feasible schedule costing at most K, including one with noninteger start times, can be transformed in polynomial time into a canonical schedule without increasing cost.This lets the decision problem be analyzed using canonical schedules.Source: §4 · p. 16
  • Every feasible schedule costing at most K can be transformed in polynomial time into an integral schedule with exactly one early member of each pair (Ag, Bg), at no greater cost.The exchange procedure corrects defective pair counts while preserving feasibility and terminates after at most M exchanges.Source: §4 · pp. 19, 21
  • With one early member per pair, each vertex can be normalized to an A-mode or B-mode, with charge cost zero in A-mode and Fi in B-mode.In either mode, the guard job starts at its release date.Source: §4 · p. 21
  • In A-mode the charge is on time and one idle unit precedes the guard; in B-mode the block’s early jobs shift one unit and the charge costs Fi, while the guard timing is unchanged.The local offset is zero throughout A-mode and one throughout B-mode; repeated B selections do not add further delay.Source: Figure 2 · p. 22, §4 · p. 23
  • Any vertex with both A-jobs and B-jobs early can be converted to a single mode with a strict cost reduction, without changing charge contributions or affecting other windows or guards.The exchange replaces each early A-job with its paired B-job and swaps the pair in the tail; their common due date and positive tail tardiness yield the saving.Source: §4 · p. 23
  • Every feasible schedule of cost at most K, including one with noninteger starts, admits a polynomial-time canonical schedule of no greater cost.Normalization first makes exactly one member of each pair early, then sets vertex modes and charge and guard placements, and finally compacts and sorts the tail.Source: §4 · p. 24
  • Nonincreasing weight order minimizes the compacted tail’s cost, the equal-processing-time specialization of Smith’s rule.Swapping adjacent jobs a and b when wa < wb reduces the weighted completion component by P(wa − wb); ties leave it unchanged.Source: §4 · p. 24

5 Cost identity and strong NP-completeness

This section develops a positive-integer-coefficient cost identity and a polynomially encoded MAX-CUT reduction to establish strong NP-completeness, even when every job can meet its due date if processed at release. It also characterizes the scheduling optimum by the cuts it favors.

5 Cost identity and strong NP-completeness

  • For strictly positive integer edge coefficients, the normalized schedule cost is a constant minus a scaled weighted-cut value.The coefficient identity makes unequal endpoint modes the source of the cut saving.Source: §5 · pp. 27–28
  • The cost-identity proposition requires strictly positive integer edge coefficients and does not as stated cover zero, negative, or arbitrary real coefficients.Each coefficient determines an interval width and the endpoint job-weight differences and charge-weight portions.Source: §5 · p. 28
  • The reduction assigns coefficient Γ + 1 to original graph edges and 1 to auxiliary edges, bounding auxiliary crossing pairs by Γ − 1.The constructed scheduling instance admits a schedule of cost at most K* if and only if the MAX-CUT instance has a cut of size at least κ.Source: §5 · p. 28
  • The decision problem is strongly NP-complete even when every job satisfies d_j ≥ r_j + p, with all numerical data and the threshold polynomially bounded in the number of jobs.The reduction’s threshold is integral, and the construction also satisfies d_j ≥ r_j + p for every job.Source: §5 · pp. 28–29

Cost identity and strong NP-completeness

  • With N=2n^2 jobs and total unary encoding length O(N^15), the reduction proves strong NP-hardness.The source graph has no isolated vertices, so the output length is polynomial in the graph input length.Source: §5 · p. 30
  • The reduction parameters are computable in O(n^2) arithmetic operations using polynomial-bit operands, without enumerating interval endpoints as jobs.Prefix sums are used for (3), and direct sums for (5) and (7).Source: §5 · p. 30
  • A job permutation is a polynomial-size certificate whose earliest schedule can be checked in polynomial time, establishing membership in NP.The earliest schedule meets the threshold whenever any feasible schedule with that permutation does, including schedules with noninteger start times.Source: §5 · p. 30
  • The scheduling optimum first maximizes the number of original graph edges cut, then maximizes s(x)(n − s(x)) among maximum cuts.Losing one cut edge reduces the first term by Γ, more than the second term can increase, which is bounded by Γ − 1.Source: §5 · p. 31

6 A phase-grid assignment algorithm and its shifted-objective guarantee

The section gives a phase-grid assignment algorithm and analyzes its guarantee for the shifted objective. Its ratio bound is tight for this algorithm, while the guarantee applies to the shifted—not the original—objective.

6.1 Shifted objective

  • The shift pW leaves the objective’s optimal schedules unchanged, but the approximation guarantee is for Φ rather than the unshifted objective F.Source: §6.1 · p. 31

6.2 The phase-grid assignment algorithm

  • The algorithm tests distinct release-date phases, builds candidate grid slots, assigns jobs to slots by minimum-cost matching, and returns the least-cost schedule.The matching must cover every job, but slots may remain unused.Source: §6.2 · pp. 31–32
  • For a fixed phase, the matching returns an optimal schedule among schedules whose starts lie on that phase’s grid.Source: §6.2 · p. 32
  • The algorithm uses O(N^5) arithmetic operations, with generated times and costs of polynomial binary length.It avoids enumerating every integer time, every residue modulo p, or the full time horizon.Source: §6.2 · p. 32

6.3 Worst-case analysis

  • For each tested phase, upward-rounding all optimal starts preserves feasibility and delays each job by less than p, increasing its cost by at most w_jδ_j.Weight-dependent averaging over tested phases sharpens the uniform additive bound used in the analysis.Source: §6.3 · p. 33

6.4 Tightness and the role of the shift

  • For every integer N ≥ 1, an integer-data instance attains ratio 3/2 − 1/(2N) for the phase-grid assignment algorithm using shift (33).Source: §6.4 · p. 34

7 Conclusion

The paper establishes strong NP-hardness for equal-processing-time weighted tardiness with release dates and presents a phase-grid algorithm with a tight guarantee for a shifted objective. Its conclusion distinguishes that guarantee from what is established for the original objective and identifies open directions.

7 Conclusion

  • The problem remains strongly NP-hard with equal processing times, settling a complexity question documented since 2010.The result holds even when each job can meet its due date if processed immediately upon release.Source: §7 · p. 35
  • The phase-grid algorithm solves at most N assignment problems in O(N^5) arithmetic operations and achieves a tight ratio of 3/2 − 1/(2N) for the shifted objective.The bound is tight for this specified algorithm.Source: §7 · p. 35
  • The hardness proof normalizes sufficiently inexpensive schedules into binary vertex choices, then uses a pairwise cost identity to connect the construction to MAX-CUT.The job counts and numerical values remain polynomially bounded.Source: §7 · pp. 35–36
  • Weight-dependent averaging over release phases yields a sharper additive error from which the shifted-objective ratio follows.Source: §7 · p. 36
  • The shifted-objective guarantee does not establish a constant multiplicative guarantee for ordinary weighted tardiness.Source: §7 · p. 36
  • Restricted release dates, weights, or release phases, and stronger algorithms for the shifted objective, remain directions for future work.The conclusion also notes the established polynomial cases as useful directions for algorithm design.Source: §7 · p. 36

Data and code availability

The manuscript relies on self-contained proofs rather than external empirical data. The package includes the source and compiled PDF, but no supplementary implementation code or recorded computational outputs.

Data and code availability

  • No external empirical data are used, and the proofs of Theorems 1 and 2 are self-contained and do not depend on computational experiments.Source: Data and code availability · p. 36
  • The manuscript package contains the LaTeX source and compiled PDF, but no supplementary implementation code or recorded computational outputs.Source: Data and code availability · p. 36
Loading 2609.28751v1…