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

Cite: Ратушный А.В. , Кочетов Ю.А.
Двухстадийный алгоритм для динамической задачи упаковки в контейнеры с группами размещения
Дискретный анализ и исследование операций. 2025. Т.32. №1. С.99–118. DOI: 10.33048/daio.2025.32.813

Dates:

Submitted:	Sep 11, 2024
Accepted:	Sep 22, 2024
Published print:	Mar 20, 2025
Published online:	Mar 20, 2025

Identifiers: No identifiers

Citing: Пока нет цитирований

Altmetrics: