Реферат: The main directions of development in cloud computing systems are aimed at increasing the efficiency of using server resources and the reliability of virtual machines (VMs), as well as reducing operating costs. A common goal in such systems is to minimize the number of servers required to maintain a given set of VMs, satisfying server capacity constraints. This goal practically leads to the well-known temporal bin packing problem. This study explores a generalization of this problem by introducing a concept of fault domains, where specific sets of VMs must operate in independent domain zones. For this NP-hard problem, we developed a heuristic for calculating the upper bound, based on the First Fit algorithm. Using the structural prop erties of the new constraints, we propose several efficient VM sequencing algorithms for the First Fit algorithm. Preliminary computational exper iments on a publicly available dataset showed that the proposed heuristic method is capable of efficiently solving both small and large scale prob lems in a short time.

Библиографическая ссылка: Davydov I. , Akentyev V.
Greedy algorithms for the temporal bin packing problem with failure domain
XXIII International Conference Mathematical Optimization Theory and Operations Research 30 Jun - 6 Jul 2024