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
Citation
Georgia Institute of Technology School of Industrial and Systems Engineering, April 2022