Parameterized complexity of machine scheduling: 15 open problems

Publikationstyp
Review Article
Date Issued
2018-12
Sprache
English
Author(s)
Mnich, Matthias  orcid-logo
van Bevern, RenĂ©  
TORE-URI
http://hdl.handle.net/11420/4605
Journal
Computers & operations research  
Start Page
254
End Page
261
Citation
Computers (2018)
Publisher DOI
10.1016/j.cor.2018.07.020
ArXiv ID
1709.01670v3
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.
Subjects
Makespan
Number of tardy jobs
Parallel machines
Shop scheduling
Throughput
Total completion time
Total tardiness
Mathematics - Optimization and Control
Mathematics - Optimization and Control
Computer Science - Computational Complexity
Computer Science - Data Structures and Algorithms
90B35
F.2.2; G.2.1