DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2022.18

Hardness of Interval Scheduling on Unrelated Machines

Authors: Danny Hermelin, Yuval Itzhaki, Hendrik Molter, and Dvir Shabtay

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

Abstract

We provide new (parameterized) computational hardness results for Interval Scheduling on Unrelated Machines. It is a classical scheduling problem motivated from just-in-time or lean manufacturing, where the goal is to complete jobs exactly at their deadline. We are given n jobs and m machines. Each job has a deadline, a weight, and a processing time that may be different on each machine. The goal is find a schedule that maximizes the total weight of jobs completed exactly at their deadline. Note that this uniquely defines a processing time interval for each job on each machine. Interval Scheduling on Unrelated Machines is closely related to coloring interval graphs and has been thoroughly studied for several decades. However, as pointed out by Mnich and van Bevern [Computers & Operations Research, 2018], the parameterized complexity for the number m of machines as a parameter remained open. We resolve this by showing that Interval Scheduling on Unrelated Machines is W[1]-hard when parameterized by the number m of machines. To this end, we prove W[1]-hardness with respect to m of the special case where we have parallel machines with eligible machine sets for jobs. This answers Open Problem 8 of Mnich and van Bevern’s list of 15 open problems in the parameterized complexity of scheduling [Computers & Operations Research, 2018]. Furthermore, we resolve the computational complexity status of the unweighted version of Interval Scheduling on Unrelated Machines by proving that it is NP-complete. This answers an open question by Sung and Vlach [Journal of Scheduling, 2005].

Cite as

Danny Hermelin, Yuval Itzhaki, Hendrik Molter, and Dvir Shabtay. Hardness of Interval Scheduling on Unrelated Machines. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hermelin_et_al:LIPIcs.IPEC.2022.18,
  author =	{Hermelin, Danny and Itzhaki, Yuval and Molter, Hendrik and Shabtay, Dvir},
  title =	{{Hardness of Interval Scheduling on Unrelated Machines}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.18},
  URN =		{urn:nbn:de:0030-drops-173748},
  doi =		{10.4230/LIPIcs.IPEC.2022.18},
  annote =	{Keywords: Just-in-time scheduling, Parallel machines, Eligible machine sets, W\lbrack1\rbrack-hardness, NP-hardness}
}

Document

DOI: 10.4230/LIPIcs.SAND.2022.19

Temporal Unit Interval Independent Sets

Authors: Danny Hermelin, Yuval Itzhaki, Hendrik Molter, and Rolf Niedermeier

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract

Temporal graphs have been recently introduced to model changes to a given network that occur throughout a fixed period of time. We introduce and investigate the Temporal Δ Independent Set problem, a temporal variant of the well known Independent Set problem. This problem is e.g. motivated in the context of finding conflict-free schedules for maximum subsets of tasks, that have certain (changing) constraints on each day they need to be performed. We are specifically interested in the case where each task needs to be performed in a certain time-interval on each day and two tasks are in conflict on a day if their time-intervals overlap on that day. This leads us to considering Temporal Δ Independent Set on the restricted class of temporal unit interval graphs, i.e., temporal graphs where each layer is unit interval. We present several hardness results for this problem, as well as two algorithms: The first is a constant-factor approximation algorithm for instances where τ, the total number of time steps (layers) of the temporal graph, and Δ, a parameter that allows us to model some tolerance in the conflicts, are constants. For the second result we use the notion of order preservation for temporal unit interval graphs that, informally, requires the intervals of every layer to obey a common ordering. We provide an FPT algorithm parameterized by the size of minimum vertex deletion set to order preservation.

Cite as

Danny Hermelin, Yuval Itzhaki, Hendrik Molter, and Rolf Niedermeier. Temporal Unit Interval Independent Sets. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hermelin_et_al:LIPIcs.SAND.2022.19,
  author =	{Hermelin, Danny and Itzhaki, Yuval and Molter, Hendrik and Niedermeier, Rolf},
  title =	{{Temporal Unit Interval Independent Sets}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.19},
  URN =		{urn:nbn:de:0030-drops-159617},
  doi =		{10.4230/LIPIcs.SAND.2022.19},
  annote =	{Keywords: Temporal Graphs, Vertex Orderings, Order Preservation, Interval Graphs, Algorithms and Complexity}
}

Search Results

Documents authored by Itzhaki, Yuval

Hardness of Interval Scheduling on Unrelated Machines

Abstract

Cite as

Temporal Unit Interval Independent Sets

Abstract

Cite as

Thanks for your feedback!

Could not send message