arXiv preprint ·
Scheduling with Mandatory Breaks: NP-Hardness and an Additive-One Approximation
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Certificate-Governed CRT Sparse FFT: Verified Global-Label Candidate Construction under Explicit Decoding Models
Degree Balance as a Fine-Grained Complexity Boundary for Quantum SAT
Online Stochastic Allocation with Increasing Returns
On Extensions of the Unanimous Vote Problem
Local Search for Fair Max-Min Diversification
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.