Parameterized complexity of machine scheduling: 15 open problems

Matthias Mnich, René van Bevern

Research output: Contribution to journalReview articlepeer-review

21 Citations (Scopus)

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. (C) 2018 Elsevier Ltd. All rights reserved.

Original languageEnglish
Pages (from-to)254-261
Number of pages8
JournalComputers and Operations Research
Volume100
DOIs
Publication statusPublished - 1 Dec 2018

Keywords

  • Makespan
  • Number of tardy jobs
  • Parallel machines
  • Shop scheduling
  • Throughput
  • Total completion time
  • Total tardiness
  • MULTIVARIATE ALGORITHMICS
  • WEIGHTED NUMBER
  • TASKS
  • MAKESPAN MINIMIZATION
  • OPEN SHOPS
  • LATE JOBS
  • MEAN FLOW TIME
  • FORBIDDEN START

OECD FOS+WOS

  • 1.02.EV COMPUTER SCIENCE, INTERDISCIPLINARY APPLICATIONS
  • 2.11.IJ ENGINEERING, INDUSTRIAL
  • 5.02.PE OPERATIONS RESEARCH & MANAGEMENT SCIENCE

Fingerprint Dive into the research topics of 'Parameterized complexity of machine scheduling: 15 open problems'. Together they form a unique fingerprint.

Cite this