Optimizing job completion time with fairness in large-scale data centers

• Published in: Future generation computer systems 2021-01, Vol.114, p.563-573
• Main Authors: Wu, Zhaoxi, Fu, Liqun
• Format: Article
• Language: English
• Subjects: Data center; Job completion time; Lexicographical maximization
• ISSN: 0167-739X; 1872-7115
• DOI: 10.1016/j.future.2020.08.013

In this paper, we aim to design new algorithms to schedule jobs efficiently and fairly. In particular, we consider that different jobs in a shared cluster have different degrees of sensitivity to their completion times, and parallel frameworks should provide differential treatment to jobs with different degrees of sensitivity. The above problem called CORA (Completion-time Optimal Resource Allocation) can be formulated as a lexicographical maximization problem. But it is challenging to solve in practice due to its inherent multi-objective, integer, large-scale, and non-convex nature. To address these challenges, we propose efficient algorithms under different problem scales. In particular, when the problem is of small-to-median scale, we propose a method called SILM (Single Iteration Lexicographical Maximization) so that the optimal schedule can be found efficiently. When the problem is of large-scale, we propose a method called MILM (Multiple Iterations Lexicographical Maximization), which can be further accelerated by the UCDM (Uniform Coordinate Descent Method), to find the optimal schedule iteratively. Last but not least, we also propose a heuristic algorithm, called Multiple Resource Water Filling (MRWF) that can reach close-to-optimal solution with fast run-time. The simulation using CVXPY (Python version of CVX) shows that, compared with the state-of-art method called Linearized-CORA, our SILM method can reduce run time by at most 87.7%. Furthermore, the performance gap of the heuristic method is within 15% compared with the optimal solutions. •When the problem is of small-to-median scale, we propose the SILM method to solve it efficiently.•As the problem scale further increases, we propose MILM method to find the optimal solutions. We further apply the UCDM to accelerate the MILM method.•We propose a heuristic algorithm, called Multiple Resource Water Filling (MRWF) that can reach close-to-optimal solution with fast run-time.