About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
IPDPS 2016
Conference paper
Reusable Resource Scheduling via Colored Interval Covering
Abstract
Motivated by scheduling scenarios in large shared computing systems, we study the problem of reusable resource scheduling. In this problem, there are many resources, each specified by a capacity, duration, per-use cost, and an availability window comprising of a release time and a deadline. A resources can be reused multiple times within its availability window with each use being limited by the duration associated with the resource and incurring cost equal to per-use cost. Different uses of a resource have to be non-overlapping. Given a demand profile, the goal is tocover it by scheduling the resources within their availability windows while minimizing their total cost. Reusable resource scheduling is a generalization of the well known interval covering problem. We present approximation algorithms and hardness results for the reusable resource scheduling problem. While the interval cover problem is NP-hard, it can be solved optimally for the special case where all the resources have unit capacities. In contrast, we show that the reusable resource scheduling is NP-hard and APX-hard, even for the case where the resources have unit capacities and unit costs. The approximation algorithms are derived by considering the notion of colored interval coloring, which could be of independent interest.