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

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10421992" target="_blank" >RIV/00216208:11320/20:10421992 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.4230/LIPIcs.ISAAC.2020.18" target="_blank" >https://doi.org/10.4230/LIPIcs.ISAAC.2020.18</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.ISAAC.2020.18" target="_blank" >10.4230/LIPIcs.ISAAC.2020.18</a>

Result language

angličtina

Original language name

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

Original language description

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 ????1-norm minimization of the load vector and, partially, sum of weighted completion times N-ARY SUMMATION 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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GX19-27871X" target="_blank" >GX19-27871X: Efficient approximation algorithms and circuit complexity</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2020

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Leibniz International Proceedings in Informatics, LIPIcs

ISBN

978-3-95977-173-3

ISSN

1868-8969

e-ISSN

—

Number of pages

17

Pages from-to

1-17

Publisher name

Schloss Dagstuhl--Leibniz-Zentrum für Informatik

Place of publication

Dagstuhl

Event location

Hong Kong

Event date

Dec 14, 2020

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—