Resource allocation problems often arise in real-life scenarios, production systems and computing services. While these problems have been extensively studied, most of the previous works propose algorithms that apply rigid resource allocation schemes. These schemes may either use the same allocation rule, or even the very same allocation of resources for the lifetime of a job.
However, in modern applications, such as video delivery over wireless networks, deadline-aware scheduling in cloud systems, and in broadcasting networks, either jobs resource requirements inherently change over time, or service level agreements allow to apply such changes, under some restrictions. Thus, it is natural to seek flexible resource allocation schemes, using a certain optimization goal (e.g., system throughput, resource utilization, or quality-of-service). This is the focus of the present research.
We consider variants of fundamental scheduling and packing problems, where the allocation of resources to jobs, or packed items, can change over time. This includes a variant of the classical Knapsack problem, where packed items are resizable, a generalization of resource constrained real-time scheduling, where jobs have dwindling resource requirements, and the problem of real-time scheduling with bounded number of preemptions.
Our study shows that most of the known results for the classic problems do not extend to the flexible variants. This is due to the geometric nature and the large number of configurations inherent in flexible resource allocation. Yet, all of our problems admit constant factor approximations, often by practical algorithms.
We bridge the gap between theory and practice through extensive experimental studies of our problems, showing that some of our approximation algorithms are in fact close to the optimal on realistic inputs.