TY - JOUR

T1 - Flexible Resource Allocation to Interval Jobs

AU - Katz, Dmitriy

AU - Schieber, Baruch

AU - Shachnai, Hadas

N1 - Funding Information:
This work was partly carried out during visits to DIMACS supported by the National Science Foundation under Grants Number CCF-1144502 and CCF-1445755. Work partially supported also by the Technion V.P.R. Fund, and by the Smoler Research Fund.
Publisher Copyright:
© 2019, Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2019/8/1

Y1 - 2019/8/1

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Bandwidth allocation

KW - Cloud computing

KW - Elastic all-optical networks

KW - Flexible storage allocation

KW - Paging problem

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=85065505039&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85065505039&partnerID=8YFLogxK

U2 - 10.1007/s00453-019-00582-9

DO - 10.1007/s00453-019-00582-9

M3 - Article

AN - SCOPUS:85065505039

SN - 0178-4617

VL - 81

SP - 3217

EP - 3244

JO - Algorithmica

JF - Algorithmica

IS - 8

ER -