A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack

DOI10.1007/s10951-016-0478-9zbMath1376.90028arXiv1508.01657OpenAlexW3102245374MaRDI QIDQ2400435

René van Bevern, Ondřej Suchý, Rolf Niedermeier

Publication date: 1 September 2017

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1508.01657

zbMATH Keywords

NP-hard problemfixed-parameter tractabilitymachine minimizationrelease times and deadlinessequencing within intervalsshiftable intervals

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

New algorithms for minimizing the weighted number of tardy jobs on a single machine, A general scheme for solving a large set of scheduling problems with rejection in FPT time, Efficient algorithms for scheduling parallel jobs with interval constraints in clouds, On topological models of zero entropy loosely Bernoulli systems, Equitable scheduling on a single machine, A multivariate complexity analysis of the material consumption scheduling problem, On the parameterized tractability of single machine scheduling with rejection, Completing Partial Schedules for Open Shop with Unit Processing Times and Routing, Parameterized complexity of machine scheduling: 15 open problems, Single-machine scheduling with release times, deadlines, setup times, and rejection, Parameterized complexity of a coupled-task scheduling problem, Throughput scheduling with equal additive laxity, Single courier single restaurant meal delivery (without routing), On the parameterized tractability of the just-in-time flow-shop scheduling problem, Throughput scheduling with equal additive laxity, Scheduling meets \(n\)-fold integer programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Towards optimal and expressive kernelization for \(d\)-hitting set
• Interval scheduling and colorful independent sets
• Scheduling and fixed-parameter tractability
• An introduction to multi-parameter complexity analysis of discrete problems
• On the parametric complexity of schedules to minimize tardy tasks.
• \(W[2\)-hardness of precedence constrained \(K\)-processor scheduling]
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Bin packing with fixed number of bins revisited
• Approximability and parameterized complexity of multicover by \(c\)-intervals
• A complete 4-parametric complexity classification of short shop scheduling problems
• Shiftable intervals
• Parametrized complexity theory.
• Reflections on Multivariate Algorithmics and Problem Parameterization
• Strip Graphs: Recognition and Scheduling
• Interval scheduling: A survey
• An ℴ(log m)-Competitive Algorithm for Online Machine Minimization
• Scheduling Two Competing Agents When One Agent Has Significantly Fewer Jobs
• Parameterized Algorithms