Scheduling Resources for Throughput Maximization

Abstract

We consider the problem of scheduling a set of resources over time. Each resource is specified by a set of time intervals (and the associated amount of resource available), and we can choose to schedule it in one of these intervals. The goal is to maximize the number of demands satisfied, where each demand is an interval with a starting and ending time, and a certain resource requirement. This problem arises naturally in many scenarios, e.g., the resource could be an energy source, and we would like to suitably combine different energy sources to satisfy as many demands as possible. We give a constant factor randomized approximation algorithm for this problem, under suitable assumptions (the so called no-bottleneck assumptions). We show that without these assumptions, the problem is as hard as the independent set problem. Our proof requires a novel configuration LP relaxation for this problem. The LP relaxation exploits the pattern of demand sharing that can occur across different resources.