Kanthi Sarpatwar, Baruch Schieber, et al.
Operations Research Letters
Motivated by the cloud computing paradigm, and by key optimization problems in all-optical networks, we study two variants of the classic job interval scheduling problem, where a reusable resource is allocated to competing job intervals in a flexible manner. Each job, Ji, requires the use of up to rmax(i) units of the resource, with a profit of pi≥ 1 accrued for each allocated unit. The goal is to feasibly schedule a subset of the jobs so as to maximize the total profit. The resource can be allocated either in contiguous or non-contiguous blocks. These problems can be viewed as flexible variants of the well known storage allocation and bandwidth allocation problems. We show that the contiguous version is strongly NP-hard, already for instances where all jobs have the same profit and the same maximum resource requirement. For such instances, we derive the best possible positive result, namely, a polynomial time approximation scheme. We further show that the contiguous variant admits a (54+ε)-approximation algorithm, for any fixed ε> 0 , on instances whose job intervals form a proper interval graph. At the heart of the algorithm lies a non-standard parameterization of the approximation ratio itself, which is of independent interest. For the non-contiguous case, we uncover an interesting relation to the paging problem that leads to a simple O(nlog n) algorithm for uniform profit instances of n jobs. The algorithm is easy to implement and is thus practical.
Kanthi Sarpatwar, Baruch Schieber, et al.
Operations Research Letters
Nikhil Bansal, Amit Chakrabarti, et al.
STOC 2006
Viswanath Nagarajan, Baruch Schieber, et al.
Mathematics of Operations Research
Alan J. Hoffman, Baruch Schieber
Discrete Applied Mathematics