Двухстадийный алгоритм для динамической задачи упаковки в контейнеры с группами размещения

Рассматривается новая задача динамической упаковки в контейнеры, актуальная для облачных вычислений. Для каждого предмета (виртуальной машины) известны время создания, удаления и требуемые ресурсы. Контейнеры (серверы) имеют NUMA-архитектуру и определённые правила при размещении машин. Серверы собраны в стойки, а некоторые машины образуют группы. Каждая группа разделена на партиции. Машины из разных партиций нельзя размещать на одной стойке для обеспечения отказоустойчивости системы. Требуется упаковать все машины в минимальное число стоек на заданном горизонте планирования. Для решения задачи разработан двухстадийный алгоритм: построение начального решения, в котором нарушается часть ограничений, и итеративное улучшение с помощью локального поиска, направленное на устранение нарушений. Применяя предложенный подход на открытых тестовых примерах, удалось достичь среднего отклонения от нижней границы в $3,8\%$. Табл. 3, ил. 4, библиогр. 27.