License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2022.18
URN: urn:nbn:de:0030-drops-173748
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17374/
Hermelin, Danny ;
Itzhaki, Yuval ;
Molter, Hendrik ;
Shabtay, Dvir
Hardness of Interval Scheduling on Unrelated Machines
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].
BibTeX - Entry
@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/opus/volltexte/2022/17374},
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}
}
|
Keywords: |
|
Just-in-time scheduling, Parallel machines, Eligible machine sets, W[1]-hardness, NP-hardness |
|
Collection: |
|
17th International Symposium on Parameterized and Exact Computation (IPEC 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
14.12.2022 |
