Interval scheduling with economies of scale. (February 2023) - Muir, Christopher; Toriello, Alejandro
Abstract: Motivated by applications in cloud computing, we study interval scheduling problems exhibiting economies of scale. An instance is given by a set of jobs, each with start time, end time, and a function representing the cost of scheduling a subset of jobs on the same machine. Specifically, we focus on the max-weight function and non-negative, non-decreasing concave functions of total schedule weight. The goal is a partition of the jobs that minimizes the total schedule cost, where overlapping jobs cannot be processed on the same machine. We propose a set cover formulation and a column generation algorithm to solve its linear relaxation. For the max-weight function, which is already NP-hard, we give a polynomial-time pricing algorithm; for the more general case of a function of the total weight, we have a pseudo-polynomial algorithm. To obtain integer solutions, we extend the column generation approach using branch-and-price. We computationally evaluate our methods on two different functions, using both random instances and instances derived from cloud computing data; our algorithm significantly outperforms known integer programming formulations (when these are available) and is able to provably optimize instances with hundreds of jobs. Highlights: Set covering formulation for interval scheduling with economies of scale. Efficient pricing algorithms for the max-weight and concave functions. Integral linear programming formulation for the max-weight function on paths. Branch-and-price outperforms standard methods the for max-weight function.