REVIEW
Scheduling with Mandatory Breaks: NP-Hardness and an Additive-One Approximation
Data Structures and Algorithms · Submitted 28 Sep 2026 · 23 references
Pith's verdict: Settles the exact complexity threshold for mandatory-break fixed-interval scheduling (x=1 easy, x>=2 hard) and gives a provably best-possible OPT+1 algorithm; the proofs check out and it deserves a referee.
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
A mandatory idle break of length 2 or more makes fixed-interval scheduling strongly NP-hard, yet a feasible schedule using at most OPT + 1 machines is always computable in polynomial time.
The reading
What carries the argument
The argument runs on three objects. For hardness, a variable gadget with three variable jobs and three literal jobs whose safe pairings are exactly the nonempty sets of occurrences of a single sign, forcing a consistent truth assignment; the construction has 9p jobs with all coordinates at most 10.5p, giving strong NP-hardness. For x = 1, handoff sets, a union of directed paths over touching jobs, showing that a budget of K machines forces exactly max(0, δ(t) − K) handoffs at each point t, with a flow network deciding which jobs hand off without ever covering the horizon. For the additive-one guarantee, the width formula W(z) = max_{(P,Q) admissible} (Z_z(P) + d(Q) − Z_z(Q)) for the partial order of a legal early/late labeling, combined with a linear program over O(n) labeling variables and O(n²) constraints whose constraint matrix is totally unimodular because the elementary intervals of a job are consecutive; rounding a vertex perturbs every elementary-interval depth by less than one, incurring at most one extra machine.
Extended reading notes
Core claim
The paper's central claims are three. First (Theorem 1), for every fixed break length x ≥ 2, deciding whether k machines suffice is NP-complete even when all coordinates are bounded linearly in the number of jobs, so machine minimization is strongly NP-hard; the reduction maps a restricted satisfiability form — each variable appears exactly three times, twice with one sign and once with the other — to 9p jobs arranged in variable, literal, and clause gadgets whose machines realize a truth assignment exactly when the safe pairings force a consistent sign. Second (Theorem 2), for x = 1 the problem is exactly solvable in O(n² log n) time: a machine has an idle gap of length one exactly when its jobs do not tile the horizon, so the only decisions are which touching jobs hand off on one machine, and a flow network with a binary search over the machine budget decides feasibility. Third (Theorem 3), for every x there is a deterministic polynomial-time algorithm returning at most OPT + 1 machines: jobs are labeled early or late, the minimum chain cover under that labeling is the machine count, an LP over the labels is solved and rounded through total unimodularity, perturbing every elementary-interval depth by less than one, which costs at most one extra machine. Corollary 1 states that this is best possible: unless P = NP no polynomial algorithm guarantees OPT machines for any fixed x ≥ 2.
Load-bearing premise
The additive-one guarantee rests on the width formula of Lemma 9, which claims that for every legal early/late labeling, the true width of the partial order equals the maximum over a single admissible pair of elementary intervals of Z_z(P) + d(Q) − Z_z(Q); if an antichain existed that no single admissible pair pinned, the LP relaxation would not control the real width and the OPT + 1 bound could fail.
Editorial extensions
If this is right
- The complexity of the problem is fully settled: exact polynomial algorithms for x ≤ 1, strong NP-hardness for every fixed x ≥ 2, with an exact boundary at x = 2.
- Unless P = NP, no polynomial-time algorithm can guarantee OPT machines for any break length x ≥ 2, so the additive-one guarantee of Theorem 3 cannot be improved.
- The additive-one algorithm works for every break length x, including the hard regime, and reduces the entire difficulty to choosing early/late labels: given the right labels, an optimal schedule is recovered in polynomial time via Dilworth's chain cover.
- The x = 1 case coincides with the working-time constrained fixed job schedule problem at the largest constraining per-machine limit (y − 1), which the paper shows is polynomial even though that problem is NP-hard for general limits.
Reading between the lines
- The total-unimodularity rounding that drives the OPT + 1 guarantee likely transfers to other per-machine constraints whose 0/1 labels enter constraints only through depth sums, such as spread-time bounds or workload caps; testing the same LP-and-rounding scheme on those problems would show whether additive-one guarantees are a general phenomenon rather than specific to breaks.
- The additive gap of one machine is probably realized on some natural instance family; the paper leaves open the search for such a family, and finding one would clarify when the extra machine is actually incurred.
- The threshold at x = 2 suggests the hardness is driven by the break no longer fitting into arbitrary integral gaps; analogous gap-requirement variants of other interval problems may exhibit the same dichotomy at their own integrality boundaries.
- The O(n²)-constraint linear program might be avoidable: a purely combinatorial algorithm achieving the same tolerance guarantee, which the paper leaves open, could expose whether the linear program is the essential bottleneck.
Original 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.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | In classical fixed-interval scheduling, each job of a given set must be processed during a prescribed time interval. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s1 | 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. | background 1.00 | 0.08 | 0.03 | asserted 1.00 |
| s2 | Without further constraints this is interval graph coloring and is solvable in polynomial time through greedy approaches. | background 1.00 | 0.06 | 0.02 | asserted 1.00 |
| s3 | 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. | contribution 0.84 | 0.26 | 0.05 | asserted 0.93 |
| s4 | We show that this additional constraint makes the problem hard, except when $x\le1$. | result 0.97 | 0.91 | 0.37 | asserted 1.00 |
| s5 | 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. | result 0.98 | 0.93 | 0.29 | asserted 1.00 |
| s6 | Second, for $x=1$, we give a polynomial-time algorithm that solves the problem exactly. | result 0.57 | 0.96 | 0.13 | asserted 1.00 |
| s7 | 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. | contribution 0.68 | 0.96 | 0.33 | asserted 1.00 |
| s8 | 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. | interpretation 0.80 | 0.60 | 0.33 | asserted 0.93 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
Figures
Figures reproduced from arXiv:2609.34254 by the authors.
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.