Parameterized complexity of machine scheduling: 15 open problems

Matthias Mnich; René van Bevern

doi:10.1016/j.cor.2018.07.020

Parameterized complexity of machine scheduling: 15 open problems

Matthias Mnich, René van Bevern

Результат исследования: Научные публикации в периодических изданиях › обзорная статья

14 Цитирования (Scopus)

Аннотация

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.

Язык оригинала	английский
Страницы (с-по)	254-261
Число страниц	8
Журнал	Computers and Operations Research
Том	100
DOI	https://doi.org/10.1016/j.cor.2018.07.020
Состояние	Опубликовано - 1 дек 2018

Доступ к документу

10.1016/j.cor.2018.07.020

Link to publication in Scopus

Fingerprint Подробные сведения о темах исследования «Parameterized complexity of machine scheduling: 15 open problems». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать

Mnich, M., & van Bevern, R. (2018). Parameterized complexity of machine scheduling: 15 open problems. Computers and Operations Research, 100, 254-261. https://doi.org/10.1016/j.cor.2018.07.020

@article{4d51c6591caf496f8915c391cb6707bf,

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

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",

author = "Matthias Mnich and {van Bevern}, Ren{\'e}",

year = "2018",

month = dec,

day = "1",

doi = "10.1016/j.cor.2018.07.020",

language = "English",

volume = "100",

pages = "254--261",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier",

}

TY - JOUR

T1 - Parameterized complexity of machine scheduling

T2 - 15 open problems

AU - Mnich, Matthias

AU - van Bevern, René

PY - 2018/12/1

Y1 - 2018/12/1

N2 - 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.

AB - 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.

KW - Makespan

KW - Number of tardy jobs

KW - Parallel machines

KW - Shop scheduling

KW - Throughput

KW - Total completion time

KW - Total tardiness

KW - MULTIVARIATE ALGORITHMICS

KW - WEIGHTED NUMBER

KW - TASKS

KW - MAKESPAN MINIMIZATION

KW - OPEN SHOPS

KW - LATE JOBS

KW - MEAN FLOW TIME

KW - FORBIDDEN START

UR - http://www.scopus.com/inward/record.url?scp=85051547881&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2018.07.020

DO - 10.1016/j.cor.2018.07.020

M3 - Review article

AN - SCOPUS:85051547881

VL - 100

SP - 254

EP - 261

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

ER -