Summary
The paper studies a scheduling problem where jobs with equal length and specific release times must be ordered on one machine to minimize how late weighted jobs finish. Although related problems had known efficient solutions, the complexity of this particular problem was unknown for over a decade. The authors prove that deciding the best schedule is strongly NP-complete, meaning it is computationally very hard in the worst case. They also provide an efficient algorithm that produces good approximate schedules and gives formal bounds on how close these schedules are to the best possible. This work settles a long-open question and offers a way to handle the problem in practice.
What this means in practice
- •For manufacturing schedulers: Understand the computational difficulty of scheduling jobs with equal processing times but varying release and due dates to better estimate time and resource needs.
- •For logistics planners: Use the presented approximation algorithm to generate near-optimal job sequences where tasks must start at certain times and weighted lateness should be minimized.
A theory result. No direct application yet.
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\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.