Solving Group Interval Scheduling Efficiently

Abstract

The problem models the scenario where there is set of jobs to be processed on a single machine, and each job i can only be scheduled for processing in exactly one time interval from a group $G_i$ of allowed intervals. The objective is to determine if there is a set of $S \subseteq [\gamma ]$ of $k\ (k \in \mathbb {N})$ jobs which can be scheduled in non-overlapping time intervals.

This work describes a deterministic algorithm for the problem that runs in time ${\text {O}}({(5.18)}^k n^d)$, where $n = |\bigcup _{i \in [\gamma ]} G_i|$ and $d \in \mathbb {N}$ is a constant. For $k \ge d \log {n}$, this is significantly faster than the best previously-known deterministic algorithm, which runs in time ${\text {O}}({(12.8)}^k \gamma n)$. We obtain our speedup using efficient constructions of representative families, which can be used to solve the problem by a dynamic programming approach.