Research output

Parameterized complexity of machine scheduling: 15 open problems

Research output: Contribution to journalArticleAcademicpeer-review

Associated researcher

Associated organisations

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.

    Research areas

  • Parallel machines, Shop scheduling, Makespan, Total completion time, Total tardiness, Throughput, Number of tardy jobs, TIME APPROXIMATION SCHEME, MEAN FLOW TIME, OPEN-SHOPS, LATE JOBS, MAKESPAN MINIMIZATION, WEIGHTED NUMBER, FORBIDDEN START, MULTIVARIATE ALGORITHMICS, PARALLEL MACHINES, COMPLETION TIMES, TASKS, OPEN SHOPS
View graph of relations

Details

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