License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2020.18
URN: urn:nbn:de:0030-drops-133620
Go to the corresponding LIPIcs Volume Portal

Koutecký, Martin ; Zink, Johannes

Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines

LIPIcs-ISAAC-2020-18.pdf (0.7 MB)


The task of scheduling jobs to machines while minimizing the total makespan, the sum of weighted completion times, or a norm of the load vector, are among the oldest and most fundamental tasks in combinatorial optimization. Since all of these problems are in general NP-hard, much attention has been given to the regime where there is only a small number k of job types, but possibly the number of jobs n is large; this is the few job types, high-multiplicity regime. Despite many positive results, the hardness boundary of this regime was not understood until now.
We show that makespan minimization on uniformly related machines (Q|HM|C_max) is NP-hard already with 6 job types, and that the related Cutting Stock problem is NP-hard already with 8 item types. For the more general unrelated machines model (R|HM|C_max), we show that if either the largest job size p_max, or the number of jobs n are polynomially bounded in the instance size |I|, there are algorithms with complexity |I|^poly(k). Our main result is that this is unlikely to be improved, because Q||C_max is W[1]-hard parameterized by k already when n, p_max, and the numbers describing the speeds are polynomial in |I|; the same holds for R|HM|C_max (without speeds) when the job sizes matrix has rank 2. Our positive and negative results also extend to the objectives 𝓁₂-norm minimization of the load vector and, partially, sum of weighted completion times ∑ w_j C_j.
Along the way, we answer affirmatively the question whether makespan minimization on identical machines (P||C_max) is fixed-parameter tractable parameterized by k, extending our understanding of this fundamental problem. Together with our hardness results for Q||C_max this implies that the complexity of P|HM|C_max is the only remaining open case.

BibTeX - Entry

  author =	{Martin Kouteck{\'y} and Johannes Zink},
  title =	{{Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Yixin Cao and Siu-Wing Cheng and Minming Li},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-133620},
  doi =		{10.4230/LIPIcs.ISAAC.2020.18},
  annote =	{Keywords: Scheduling, cutting stock, hardness, parameterized complexity}

Keywords: Scheduling, cutting stock, hardness, parameterized complexity
Collection: 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Issue Date: 2020
Date of publication: 04.12.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI