TY - CONF

T1 - On the Fine-Grained Parameterized Complexity of Partial Scheduling to Minimize the Makespan.

AU - Nederlof, Jesper

AU - Swennenhuis, Céline M. F.

N1 - DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

PY - 2020

Y1 - 2020

N2 - We study a natural variant of scheduling that we call partial scheduling: In this variant an instance of a scheduling problem along with an integer k is given and one seeks an optimal schedule where not all, but only k jobs, have to be processed. Specifically, we aim to determine the fine-grained parameterized complexity of partial scheduling problems parameterized by k for all variants of scheduling problems that minimize the makespan and involve unit/arbitrary processing times, identical/unrelated parallel machines, release/due dates, and precedence constraints. That is, we investigate whether algorithms with runtimes of the type f (k) n^ 풪 (1) or n^ 풪 (f (k)) exist for a function f that is as small as possible. Our contribution is two-fold: First, we categorize each variant to be either in 햯, NP-complete and fixed-parameter tractable by k, or 햶 [1]-hard parameterized by k. Second, for many interesting cases we further investigate the run time on a finer scale and obtain run times that are (almost) optimal assuming the Exponential Time Hypothesis. As one of our main technical contributions, we give an 풪 (8^ kk (| V|+| E|)) time algorithm to solve instances of partial scheduling problems minimizing the makespan with unit length jobs, precedence constraints and release dates, where G=(V, E) is the graph with precedence constraints.

AB - We study a natural variant of scheduling that we call partial scheduling: In this variant an instance of a scheduling problem along with an integer k is given and one seeks an optimal schedule where not all, but only k jobs, have to be processed. Specifically, we aim to determine the fine-grained parameterized complexity of partial scheduling problems parameterized by k for all variants of scheduling problems that minimize the makespan and involve unit/arbitrary processing times, identical/unrelated parallel machines, release/due dates, and precedence constraints. That is, we investigate whether algorithms with runtimes of the type f (k) n^ 풪 (1) or n^ 풪 (f (k)) exist for a function f that is as small as possible. Our contribution is two-fold: First, we categorize each variant to be either in 햯, NP-complete and fixed-parameter tractable by k, or 햶 [1]-hard parameterized by k. Second, for many interesting cases we further investigate the run time on a finer scale and obtain run times that are (almost) optimal assuming the Exponential Time Hypothesis. As one of our main technical contributions, we give an 풪 (8^ kk (| V|+| E|)) time algorithm to solve instances of partial scheduling problems minimizing the makespan with unit length jobs, precedence constraints and release dates, where G=(V, E) is the graph with precedence constraints.

U2 - 10.4230/LIPICS.IPEC.2020.25

DO - 10.4230/LIPICS.IPEC.2020.25

M3 - Paper

SP - 25:1-25:17

ER -