Interval Scheduling with Eligible Machines
Date:
Poster presentation at Pioneering Israeli Science, Science Abroad, New York, 2026.
Authors
Danny Hermelin, Yuval Itzhaki, Hendrik Molter, and Dvir Shabtay.
Abstract
We provide new parameterized complexity results for Interval Scheduling with Eligible Machines. 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 of Mnich and van Bevern’s list of 15 open problems in parameterized complexity of scheduling problems (Computers & Operations Research, 2018).