2026-07-22T10:25:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17374 2024-03-06T10:59:35Z ddc:004 open_access

Hardness of Interval Scheduling on Unrelated Machines Hermelin, Danny Itzhaki, Yuval Molter, Hendrik Shabtay, Dvir Just-in-time scheduling Parallel machines Eligible machine sets W[1]-hardness NP-hardness 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Danny Hermelin and Yuval Itzhaki and Hendrik Molter and Dvir Shabtay 2022 Is Part Of LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2022.18 urn:nbn:de:0030-drops-173748 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.18 eng https://creativecommons.org/licenses/by/4.0/legalcode