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, @math , requires the use of up to @math units of the resource, with a profit of @math 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 @math -approximation algorithm, for any fixed @math , 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 @math algorithm for uniform profit instances of n jobs. The algorithm is easy to implement and is thus practical.
We introduce two scheduling problems, the flexible bandwidth allocation problem ( ( FBAP )) and the flexible storage allocation problem ( ( FSAP )). In both problems, we have an available resource, and a set of requests, each consists of a minimum and a maximum resource requirement, for the duration of its execution, as well as a profit accrued per allocated unit of the resource. In ( FBAP ), the goal is to assign the available resource to a feasible subset of requests, such that the total profit is maximized, while in ( FSAP ) we also require that each satisfied request is given a contiguous portion of the resource. Our problems generalize the classic bandwidth allocation problem (BAP) and storage allocation problem (SAP) and are therefore ( NP-hard ). Our main results are a 3-approximation algorithm for ( FBAP ) and a ((3+ ) )-approximation algorithm for ( FSAP ), for any fixed ( >0 ). These algorithms make nonstandard use of the local ratio technique. Furthermore, we present a ((2+ ) )-approximation algorithm for ( SAP ), for any fixed ( >0 ), thus improving the best known ratio of ( 2e-1 e-1 + ). Our study is motivated also by critical resource allocation problems arising in all-optical networks.