Precedence-constrained scheduling problems parameterized by partial order width

René van Bevern, Robert Bredereck, Laurent Bulteau, Christian Komusiewicz, Nimrod Talmon, Gerhard J. Woeginger

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

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

Аннотация

Negatively answering a question posed by Mnich and Wiese (Math. Program. 154(1–2):533–562), we show that P2|prec, pj∈{1, 2}|Cmax, the problem of finding a non-preemptive minimummakespan schedule for precedence-constrained jobs of lengths 1 and 2 on two parallel identical machines, is W[2]-hard parameterized by the width of the partial order giving the precedence constraints. To this end, we show that Shuffle Product, the problem of deciding whether a given word can be obtained by interleaving the letters of k other given words, is W[2]-hard parameterized by k, thus additionally answering a question posed by Rizzi and Vialette (CSR 2013). Finally, refining a geometric algorithm due to Servakh (Diskretn. Anal. Issled. Oper. 7(1):75–82), we show that the more general Resource-Constrained Project Scheduling problem is fixed-parameter tractable parameterized by the partial order width combined with the maximum allowed difference between the earliest possible and factual starting time of a job.

Язык оригиналаанглийский
Название основной публикацииDiscrete Optimization and Operations Research - 9th International Conference, DOOR 2016, Proceedings
РедакторыMichael Khachay, Panos Pardalos, Yury Kochetov, Vladimir Beresnev, Evgeni Nurminski
ИздательSpringer-Verlag GmbH and Co. KG
Страницы105-120
Число страниц16
ISBN (печатное издание)9783319449135
DOI
СостояниеОпубликовано - 1 янв 2016
Событие9th International Conference on Discrete Optimization and Operations Research, DOOR 2016 - Vladivostok, Российская Федерация
Продолжительность: 19 сен 201623 сен 2016

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том9869 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция9th International Conference on Discrete Optimization and Operations Research, DOOR 2016
СтранаРоссийская Федерация
ГородVladivostok
Период19.09.201623.09.2016

ГРНТИ

  • 27 МАТЕМАТИКА

Fingerprint Подробные сведения о темах исследования «Precedence-constrained scheduling problems parameterized by partial order width». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    van Bevern, R., Bredereck, R., Bulteau, L., Komusiewicz, C., Talmon, N., & Woeginger, G. J. (2016). Precedence-constrained scheduling problems parameterized by partial order width. В M. Khachay, P. Pardalos, Y. Kochetov, V. Beresnev, & E. Nurminski (Ред.), Discrete Optimization and Operations Research - 9th International Conference, DOOR 2016, Proceedings (стр. 105-120). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 9869 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-319-44914-2_9