Interval scheduling with economies of scale. (February 2023)

• Record Type: Journal Article
• Authors: Muir, Christopher; Toriello, Alejandro
• Is Part Of: Computers & operations research. Volume 150(2023)
• Publication Date: 2023-02
• Subjects: Interval scheduling -- Integer programming -- Column generation -- Linear programming -- Dynamic programming -- Heuristics; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.106056
• Languages: English
• ISSNs: 0305-0548

Abstract

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.