The Power of Preemptions in Scheduling on Shareable Resources

Many combinatorial optimization problems arise in the context of resource allocation.In this paper, we study the problem of allocating shareable resources of different types to jobs, where each job consists of multiple tasks, and each task has a demand of a given duration to a single resource type.All resources are available over a common time interval.Several copies from each resource may be allocated.In a valid solution, at any given time, each job may be processed by at most one resource, and each resource may process at most one job.The objective is to complete all jobs while minimizing the total cost of the allocated resources.We focus on the power of preemptions in this model, analyzing how much the total cost can be reduced when jobs are allowed to be preempted -that is, when the processing of tasks can be split into multiple intervals.We present both theoretical and experimental results, distinguishing between environments where jobs may be preempted but all intervals of a task must be processed on the same resource copy (weak preemptions), and environments where jobs may split the processing of a task among different resource copies (strong preemptions).Without preemptions, the problem is clearly NPhard, as it generalizes the classical Bin Packing problem.We provide an optimal polynomial-time algorithm for the strongpreemption model, as well as a polynomial-time algorithm for the non-preemption model under a restricted class of task durations.Our empirical evaluation investigates the performance of several greedy heuristics, showing that even simple methods can achieve near-optimal results.