Interval Scheduling with Machine Eligibility
Date:
Talk at the Operations Research Society of Israel (ORSIS) Annual Meeting, held on May 12-13, 2026, at the Technion, Haifa.
Authors
Danny Hermelin, Yuval Itzhaki, Hendrik Molter, and Dvir Shabtay.
Abstract
We provide new parameterized complexity results for Interval Scheduling on 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).