Solving Group Interval Scheduling Efficiently

摘要

The Group Interval Scheduling problem models the scenario where there is set [γ] = {1, …, γ} 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 ? [γ] of k (k ∈ N) jobs which can be scheduled in non-overlapping time intervals. This work describes a deterministic algorithm for the problem that runs in time O((5.18)~kn~d), where n = | U_(i∈[γ])G_i | and d ∈ N is a constant. For k ≥ d log n, this is significantly faster than the best previously-known deterministic algorithm, which runs in time O((12.8)~kγn). We obtain our speedup using efficient constructions of representative families, which can be used to solve the problem by a dynamic programming approach.