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.IPEC.2020.25
URN: urn:nbn:de:0030-drops-133287
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13328/
Go to the corresponding LIPIcs Volume Portal

Nederlof, Jesper ; Swennenhuis, Céline M. F.

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

pdf-format:
LIPIcs-IPEC-2020-25.pdf (0.7 MB)

Abstract

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^k k(|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.

BibTeX - Entry

@InProceedings{nederlof_et_al:LIPIcs:2020:13328,
  author =	{Jesper Nederlof and C{\'e}line M. F. Swennenhuis},
  title =	{{On the Fine-Grained Parameterized Complexity of Partial Scheduling to Minimize the Makespan}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Yixin Cao and Marcin Pilipczuk},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13328},
  URN =		{urn:nbn:de:0030-drops-133287},
  doi =		{10.4230/LIPIcs.IPEC.2020.25},
  annote =	{Keywords: Fixed-Parameter Tractability, Scheduling, Precedence Constraints}
}

Keywords: Fixed-Parameter Tractability, Scheduling, Precedence Constraints
Collection: 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Issue Date: 2020
Date of publication: 04.12.2020

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