Parameterized complexity of machine scheduling: 15 open problems

Abstract

Machine scheduling problems are a long-time key domain of algorithms and complexity research. A novel approach to machine scheduling problems are fixed-parameter algorithms. To stimulate this thriving research direction, we propose 15 open questions in this area whose resolution we expect to lead to the discovery of new approaches and techniques both in scheduling and parameterized complexity theory.

Version accepted to Computers & Operations Research

References in corpus (4)

• A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
• Inductive $k$-independent graphs and $c$-colorable subgraphs in scheduling: A review
• A parameterized approximation algorithm for the mixed and windy Capacitated Arc Routing Problem: theory and experiments
• On The Parameterized Tractability of the Just-In-Time Flow-Shop Scheduling Problem

Cited by in corpus (7)

• Inductive $k$-independent graphs and $c$-colorable subgraphs in scheduling: A review
• Scheduling a Proportionate Flow Shop of Batching Machines
• Multitype Integer Monoid Optimization and Applications
• On the Complexity of Scheduling Problems With a Fixed Number of Parallel Identical Machines
• Polynomial-Time Data Reduction for Weighted Problems Beyond Additive Goal Functions
• Parameterized Complexity of Partial Scheduling
• Tight running times for minimum ${\ell }_q$-norm load balancing: beyond exponential dependencies on $1/\epsilon$