Source-linked AI summary
Scheduling with Mandatory Breaks: NP-Hardness and an Additive-One Approximation
Shreyas Ghildiyal, Muralidhara V N
TL;DR
Fixed-interval scheduling is tractable without breaks, but requiring each used machine to take a contiguous break raises the question of how break length changes complexity. The paper proves an exact threshold and develops exact and approximate algorithms. For x ≥2 the problem is NP-complete, while for x ≤1 it is polynomial-time solvable; a deterministic algorithm achieves the best possible additive-one guarantee.
Problem
The paper asks how requiring every used machine to take a prescribed contiguous break changes the complexity of fixed-interval scheduling.
Source: §1 · p. 1Method
For x = 1, the algorithm reduces handoff choices to maximum flow; the additive-one algorithm uses a fractional linear program and rounds job labels using total unimodularity.
Source: §1.2 · p. 4Results
For every fixed x ≥2 the problem is NP-complete and machine minimization is strongly NP-hard; for x ≤1 it is polynomial-time solvable, and a deterministic algorithm uses at most OPT +1 machines, the best possible guarantee unless P = NP.
Source: §1 · p. 2Takeaways & Limitations
The complexity threshold is exact: breaks of length at most one permit exact polynomial-time optimization, whereas every fixed length of at least two makes the decision problem NP-complete.
Source: §1 · p. 2For extensions such as time-window-restricted breaks or machine-dependent costs, the problem inherits hardness, but the additive-one guarantee is not established; the normal form also fails if machines may rest twice.
Source: §6 · p. 15
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies fixed-interval scheduling with a required contiguous break on every used machine. It establishes the complexity threshold, gives exact and additive-one algorithms, and explains how these results differ from related scheduling models.
1 Introduction
- For every fixed x ≥2, deciding whether k machines suffice is NP-complete, even with linearly bounded coordinates; machine minimization is strongly NP-hard.The threshold is exact: x ≤1 is polynomial-time solvable.Source: §1 · p. 2
- For x ≤1, an algorithm either reports infeasibility or computes an optimal schedule in O(n^2 log n) time.The case x = 1 is polynomial-time solvable because integral data make any idle gap of length one sufficient for a break.Source: §1 · p. 2
- A deterministic polynomial-time algorithm outputs a feasible schedule using at most OPT +1 machines, and for fixed x ≥2 this additive guarantee is best possible unless P = NP.No polynomial-time algorithm guarantees OPT machines for every feasible instance at those break lengths unless P = NP.Source: §1 · p. 2
1.1 Related work
- Unlike related workload and availability models, this problem combines fixed jobs, machine minimization, and a freely positioned contiguous idle interval; for x ≥2, workload alone does not determine feasibility.With integral data, x = 1 coincides with the working-time problem at per-machine limit y −1, a boundary case that is polynomial here.Source: §1.1 · p. 3
1.2 Technical overview
- For x = 1, the algorithm models touching consecutive jobs as handoffs and uses maximum flow, with a binary search over the machine budget.A machine has an idle gap of length one precisely when its jobs do not tile the horizon.Source: §1.2 · p. 4
- The additive-one method labels jobs early or late, solves a fractional linear program, then rounds labels using total unimodularity to incur at most one extra machine.With fixed labels, minimum chain cover reduces through Dilworth’s theorem to bipartite matching; rounding changes each constraint by less than two.Source: §1.2 · p. 4
2 Preliminaries
The preliminaries establish how schedule feasibility can be verified and characterize when any feasible schedule exists. They also define the elementary intervals used to measure overlap depth.
2 Preliminaries
- A schedule is a polynomial-size certificate: sort each machine’s jobs, check for conflicts, and verify that its longest idle interval is at least x.The idle interval includes the gaps before the first job and after the last job.Source: §2 · pp. 4–5
- A feasible schedule exists exactly when every job satisfies rj ≤ y −x or lj ≥x; otherwise that job fits on no machine.When every job satisfies one condition, assigning jobs to private machines gives a feasible schedule.Source: §2 · p. 5
- Elementary intervals are the open intervals between sorted job endpoints, 0, and y; their maximum depth D is the minimum machine count without breaks.There are at most 2n+1 elementary intervals.Source: §2 · p. 5
3 NP-completeness
The paper reduces a restricted satisfiability problem to scheduling with breaks of length two, encoding literal assignments through machine-compatible jobs and safe gaps. The construction proves NP-completeness for every fixed break length x ≥ 2, even with coordinates bounded linearly in the number of jobs.
3 NP-completeness
- The source problem is NP-complete when clauses have two or three literals and each variable occurs three times, twice with one sign and once with the other [11, 22].Variable splitting replaces each occurrence with a fresh copy and links consecutive copies in a cycle of implications.Source: §3 · p. 5
3.1 The reduction
- For x = 2, the reduction creates n = 9p jobs, uses k = 3p machines, and bounds all coordinates by 10.5p.The jobs comprise variable, literal, and clause families; the horizon is y = 6p + 3q.Source: §3.1 · pp. 5–6
3.2 Correctness
- Any schedule on at most k machines uses exactly k machines, each with one variable, literal, and clause job in that order.The construction matches literal jobs to their variables and clause jobs to the clauses of their literals, making each machine represent a literal occurrence.Source: §3.2 · p. 7
- A variable’s safe literal jobs form a nonempty set of occurrences of one sign, and the formula is satisfiable exactly when the instance fits on k machines.A satisfying assignment selects routings that make precisely its true literals safe; conversely, each clause’s filter forces a safe literal, yielding a satisfying assignment.Source: §3.2 · pp. 8–9
- The reduction makes the x = 2 decision problem NP-complete with linearly bounded coordinates, so machine minimization is strongly NP-hard; scaling extends hardness to every fixed x ≥ 2.For fixed x, the scaled coordinates remain bounded linearly in n.Source: §3.1 · p. 6, §3.2 · p. 9
4 A polynomial-time algorithm for break length one
For break length one, the algorithm characterizes feasible schedules through handoffs between touching jobs and a flow network. It tests machine budgets by maximum flow and recovers an optimal schedule in polynomial time.
4 A polynomial-time algorithm for break length one
- A machine has a length-one idle interval exactly when its jobs do not cover the full horizon; touching jobs on one machine are represented by handoffs.Feasibility on K machines is equivalent to a handoff set with no run covering the horizon and δ(t) − h_t ≤ K at every integer t.Source: §4 · pp. 9–10
- For budget K, it suffices to use exactly h_t = max(0, δ(t) − K) handoffs at each integer t, then route the runs through N_K.The network has O(n) nodes and arcs, and a flow of value |S0| exists exactly when such a handoff set avoids a horizon-covering run.Source: §4 · pp. 10–11
- For x = 1, OPT is the smallest budget K ≥ D for which network N_K admits a flow of value |S0|.Binary search over the upward-closed feasible budgets uses O(log n) maximum-flow computations.Source: §4 · pp. 11–12
- Each maximum-flow computation takes O(n^2) time, and the algorithm assembles the optimal schedule in O(n log n) time.Together with binary search, this gives O(n^2 log n) time for the flow tests.Source: §4 · p. 12
5 An additive-one approximation algorithm
The algorithm reduces machine minimization to choosing legal early/late labels and covering the resulting partial order with chains. A linear-programming relaxation and rounding then produce a feasible schedule using at most OPT +1 machines in polynomial time.
5.1 A normal form and a chain cover
- A machine is feasible exactly when its chronologically ordered jobs form an early prefix and late suffix separated by a gap of at least x.Jobs eligible for either side may be labeled early or late; jobs eligible for only one side have a forced label.Source: §5.1 · p. 12
- For any legal labeling, feasible machines correspond to chains of the induced partial order, so the minimum machine count is its width and is computable in polynomial time.A minimum chain cover can be found by a standard reduction to bipartite matching.Source: §5.1 · p. 13
5.2 A formula for the width
- The width is determined by depths at admissible pairs of elementary intervals, which count early jobs covering one interval and late jobs covering the other.Such pairs have points less than x apart; their counted jobs form an antichain.Source: §5.2 · pp. 13–14
5.3 Relaxing and rounding
- The algorithm relaxes binary labels to a linear program, then uses total unimodularity to round to a legal integral labeling while controlling interval depths.Its final bound uses the fact that the relevant integer count is at most OPT +1.Source: §5.3 · pp. 14–15
- The rounding procedure yields a legal labeling whose partial-order width is at most OPT +1, producing a feasible schedule with that many machines in polynomial time.The algorithm uses a minimum chain cover to construct the schedule.Source: §5.1 · p. 13, §5.3 · p. 15
6 Conclusion
The paper concludes that mandatory breaks preserve polynomial-time solvability for x ≤1, while every fixed x ≥2 yields strong NP-hardness; nevertheless, a polynomial-time additive-one guarantee is achievable and best possible unless P = NP. It identifies unresolved algorithmic and scope questions, including whether that guarantee extends to natural variants.
6 Conclusion
- A polynomial-time schedule using at most OPT +1 machines is achievable and best possible unless P = NP, while x ≤1 is polynomial-time solvable and every fixed x ≥2 is strongly NP-hard.The conclusion contrasts the tractable threshold with hardness beyond it and the additive-one guarantee.Source: §6 · p. 15
- Whether a purely combinatorial algorithm can match the additive-one guarantee remains open, as does characterizing instances with an integral width linear program.The conclusion also asks for a natural family where rounding incurs the additive loss.Source: §6 · p. 15
- Time-window breaks and machine-dependent costs inherit hardness, but the additive-one guarantee is not established for them; the normal form also breaks down when machines may rest twice.These are scope boundaries identified for natural extensions.Source: §6 · p. 15