Interval Scheduling with Machine Eligibility
Date:
Poster presented at the Israel Data Science and Statistics Association (ISDSA) Annual Conference, held on June 10, 2026, at Eretz Israel Museum, Tel Aviv.
Authors
Danny Hermelin, Yuval Itzhaki, Hendrik Molter, and Dvir Shabtay.
Abstract
We provide new parameterized complexity results for Interval Scheduling with Machine Eligibility. In this problem, a set of jobs is given to be processed non-preemptively on a set of machines. Each job has a processing time, a deadline, a weight, and a set of eligible machines that can process it. The goal is to find a maximum-weight subset of jobs that can each be processed on one of its eligible machines such that it completes exactly at its deadline.
We focus on two parameters: the number of machines (m) and the largest processing time (p). Our main contribution is showing W[1]-hardness when parameterized by (m). This answers Open Problem 8 from Mnich and van Bevern’s list of 15 open problems in the parameterized complexity of scheduling problems.