CS Paper Radar

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

Zhi-Long Chen, Nicholas G. Hall

cs.CC cs.DMmath.CO ·submitted 2026-09-23 19:50 UTC · v1
theory

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.

Comment
38 pages, 2 figures, 5 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Asymmetric Weighted Earliness-Tardiness: Scheduling with a Nonrestrictive Common Due Date

cs.CC math.OCcs.DMmath.CO ·2026-09-12 ·Nicholas G. Hall, Hans Kellerer, Miao Song
similarity 0.73
Abstract · 268 pages, 12 figures, 29 tables

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 polynomial-time $(3+2\sqrt2+\varepsilon)$-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.

0.21

Scheduling with Mandatory Breaks: NP-Hardness and an Additive-One Approximation

cs.DS ·2026-09-28 ·Shreyas Ghildiyal, Muralidhara V N
similarity 0.70
Abstract

In classical fixed-interval scheduling, each job of a given set must be processed during a prescribed time interval. The goal is to assign each job to exactly one machine such that no two jobs assigned to the same machine overlap in their interiors, and the number of machines used is minimized. Without further constraints this is interval graph coloring and is solvable in polynomial time through greedy approaches. We study a variant in which every used machine must remain idle during a contiguous \emph{break} of prescribed length $x$ somewhere in the scheduling horizon. We show that this additional constraint makes the problem hard, except when $x\le1$. First, for every fixed $x\ge2$, deciding whether $k$ machines suffice for the assignment of a given set of jobs is NP-complete, even when all coordinates are bounded linearly in the number of jobs, so machine minimization is strongly NP-hard. Second, for $x=1$, we give a polynomial-time algorithm that solves the problem exactly. Finally, we give a deterministic polynomial-time algorithm that, on every feasible instance, outputs a schedule using at most $\OPT+1$ machines, where $\OPT$ is the true minimum. Unless $\mathrm{P}=\mathrm{NP}$, no polynomial-time algorithm guarantees $\OPT$ machines for any fixed $x\ge2$, so the additive guarantee of one is best possible.

0.07

An EPTAS for Vector Scheduling with Time Intervals

cs.DS cs.CC ·2026-09-27 ·Junho Hwang
theory similarity 0.68
Abstract · 18 pages, 4 figures. v2: extended to several resources and unrelated machines, with a new title and simplified proofs

We study vector scheduling in which each job is active during a fixed time interval. A job uses several resources and stays on one machine for its entire interval; its resource requirements may depend on the machine. The objective is to minimize the largest resource load over all machines and times. For $r$ machines and $d$ resources, we give a deterministic $(1+\varepsilon)$-approximation in $f(r,d,1/\varepsilon)N^{O(1)}$ time, where $N$ is the binary input length. This gives an efficient polynomial-time approximation scheme for fixed $r$ and $d$, extending approximation schemes for scalar temporary tasks assignment. The algorithm merges jobs into blocks whose time intervals are fixed before any machine is chosen, and assigns the blocks by dynamic programming over a balanced recursive split of the time line. We also prove strong NP-hardness and an exponential lower bound in $1/\varepsilon$ under the Exponential Time Hypothesis, already for two identical machines and one resource.

0.13

Scheduling to Maximize Weighted Throughput with an Active-Time Budget

cs.DS ·2026-08-29 ·Susanne Albers, G. Wessel van der Heijden
publishedtheory similarity 0.67
Abstract · 16 pages, 5 figures, To appear at WAOA 2026

We study the active-time scheduling problem with weighted throughput maximization. In this setting, a set of $n$ jobs $J$ arrive at integer release times, each with an integer processing time and integer deadline. Jobs may be preempted at integer time slot boundaries. A schedule assigns jobs to time slots, with at most $m$ jobs assigned to the same time slot. A slot is called \emph{active} if at least one job is scheduled in it. Instead of scheduling all jobs to minimize the number of active time slots, we consider the more general variant of \emph{weighted throughput} with an active-time budget $K$, where each job $j\in J$ has a weight $w_j$. The objective is to maximize the total weight of \emph{completed} jobs using at most $K$ active time slots. This means that partially scheduled jobs do not count towards the objective. The classical active-time minimization problem is recovered by asking whether all jobs can be completed within a given active-time budget. We give hardness, approximation, and exact algorithmic results. For general intervals with unbounded parallelism, we prove NP-hardness, rule out an FPTAS unless $\mathrm{P}=\mathrm{NP}$, and give a pseudo-polynomial time $Ω(1/\log K)$-approximation. For proper intervals, we prove a canonical structural lemma and obtain an exact $(nK)^{O(m)}$-time algorithm. For laminar intervals, we give an exact $f(K,m)\cdot n^{O(1)}$-time algorithm.

0.25

Approximation algorithms for identical parallel machine scheduling with assignment costs

cs.DS ·2026-10-24 ·Wei Li
similarity 0.65
Abstract

We study non-preemptive scheduling on identical parallel machines in which assigning job $j$ to machine $M_i$ incurs the cost $c_{ij}=a_iw_j+b_j$. The processing times $p_j$ and the cost weights $w_j$ are independent, and the number of machines is part of the input. For every fixed $\varepsilon\in(0,1]$ and every deadline $T$ for which a schedule with makespan at most $T$ exists, we give a polynomial-time algorithm that computes a schedule with makespan at most $(1+\varepsilon)T$ whose total assignment cost does not exceed the minimum under the deadline $T$. Using this algorithm as a subroutine, we obtain a polynomial-time approximation scheme for minimizing the makespan under a total cost budget whose schedules always satisfy the budget; this answers an open question for costs $c_{ij}=l_ic_j$ with $c_j$ independent of $p_j$. For the lexicographic problem, in which the total assignment cost is minimized among all schedules of minimum makespan, we obtain in polynomial time a schedule with makespan at most $1+\varepsilon$ times the minimum and total assignment cost at most that of a lexicographically optimal schedule; this improves the makespan guarantees of earlier algorithms for additive and multiplicative costs. For costs $c_{ij}=s_i+a_iw_j$, where $s_i$ is charged for each job processed on $M_i$, the same guarantees are obtained in quasi-polynomial time.

0.24

The Complexity of Value Optimization in Sporadic Task Systems

cs.CC cs.DS ·2026-10-26 ·Christopher Harbourne, Nathan Fisher, Kecheng Yang, Pontus Ekberg, Sanjoy Baruah +1 more
theory similarity 0.64
Abstract · 31 pages, 5 figures, 2 tables

Value-based Task Selection (VTS) asks whether a real-time system can select tasks whose total value reaches a required target while preserving every deadline. We study its threshold decision form for finite collections of independent sporadic tasks scheduled preemptively on one processor. We prove that this problem is $Σ_2^P$-complete for both constrained and arbitrary deadlines, even when all numerical parameters are encoded in unary. The existential choice is the selected task set, while the universal condition requires every processor-demand window to remain feasible. Our hardness reduction already uses constrained-deadline tasks. It represents universal assignments by Chinese Remainder Theorem timestamps and uses polynomial-weight local selector locks to enforce a valid existential assignment. The reduction produces polynomially many tasks, and every generated execution time, deadline, period, task value, and target is polynomially bounded in the source-instance size.

0.25

Serial-batch scheduling to minimise the total weighted late work

cs.DS ·2026-09-16 ·Yao-Wen Sang, Naiming Xie, Jian Chen, Malgorzata Sterna, Jacek Blazewicz
similarity 0.64
Abstract

We study the problem of scheduling jobs on a serial-batch machine with the aim of minimising the total weighted late work. In a serial-batch setting, jobs within a batch are processed sequentially, and none are removed from the machine until the last job in the batch completes its processing. The processing time of a batch is the sum of the processing times of the jobs within it, and the completion time for each job in the batch is equal to the makespan of the jobs in the batch. When a new batch begins, a constant setup time is required for the machine. We show that minimising the total weighted late work in this environment is $NP$-hard even if all jobs have a common due date and unit weight. For the general problem, we present a pseudo-polynomial time dynamic programming algorithm. Additionally, we explore two special cases, i.e., one with a common due date and another with an agreeable condition among due dates, processing times and weights. For both special cases, we develop specialised pseudo-polynomial time dynamic programming algorithms. The proposed approaches are equipped with specialised acceleration techniques to enhance their computational performance. The extended experiments demonstrate that the dynamic programming algorithms outperform Gurobi in time efficiency.

0.13

Faster Exponential Algorithms for Multi-Machine Scheduling Problems

cs.DS ·2026-08-12 ·Anubhav Dhar, Anita Dürr, Ahmed Ghazy, Jakob Greilhuber, Karol Węgrzycki
published similarity 0.64
Abstract

Minimizing the weighted completion times ($P \mid \mid Σw_j C_j$) and weighted number of tardy jobs ($P \mid \mid Σw_j U_j$) on multiple identical machines are two classical NP-hard scheduling problems. As shown by Lenté et al. (2014), both problems can be solved in time ${O}^{\star}(3^n)$. In this paper, we improve these bounds to ${O}(2.755^n)$ and ${O}^{\star}(2^n)$, respectively. Our algorithm for $P \mid \mid Σw_j C_j$ exploits the meet-in-the-middle paradigm and an efficient data structure answering linear programming queries. Additionally, when the number of machines is at most $6$, we show that the running time for $P \mid \mid Σw_j C_j$ can further be improved. Both scheduling problems are generalizations of the classical Bin Packing problem, which can be solved in ${O}^{\star}(2^n)$ time. Improving this running time is an important open question. We show that, when assuming the Asymptotic Rank Conjecture (ARC), Bin Packing can be solved in time ${O}((2-\varepsilon)^n)$ for some $\varepsilon >0$. Our algorithm makes use of two main ingredients: the recent ${O}((2-\varepsilon)^n)$-time algorithm of Nederlof et al. [SICOMP'23] for Bin Packing when the number of bins is a fixed constant, and the ${O}((2-\varepsilon)^n)$-time algorithm of Björklund et al. [SODA'25] for special instances of the $3$-way Partitioning problem when assuming ARC.

0.50