Abstract: Рассматривается новая задача динамической упаковки в контейнеры, возникающая в облачных вычислениях. Имеется конечное множество виртуальных машин. Для каждой машины задано временное окно для обслуживания и два размера: число ядер и объем оперативной памяти. Все машины делятся на два типа: большие и малые. Каждый сервер состоит их двух одинаковых узлов. Малые машины помещаются полностью на один из них. Большие машины делятся пополам и помещаются на оба узла. Требуется разместить все машины в минимальное число серверов. Для решения задачи разработана эвристика, основанная на методе генерации столбцов. Для получения нижних оценок оптимума выбираются моменты времени с большой суммарной нагрузкой и для них решается статическая задача. Для построения верхних оценок решение статической задачи расширяется на все моменты времени известным алгоритмом “Первый подходящий” (First Fit). Приводятся теоретические утверждения о точности оценок в худшем случае. Вычислительные эксперименты для реальных тестовых примеров указывают на небольшой разрыв между границами, не более 0.9% для недельного интервала, 50000 машин и среднем времени расчетов 26 с на персональном компьютере. В работе удалось улучшить некоторые известные результаты на открытых примерах.

Cite: Кочетов Ю.А. , Ратушный А.В.
Верхние и нижние оценки оптимума для задачи динамической упаковки в контейнеры
Труды Института математики и механики УрО РАН (Trudy Instituta Matematiki i Mekhaniki UrO RAN). 2024. Т.30. №1. С.109-127. DOI: 10.21538/0134-4889-2024-30-1-109-127 WOS Scopus РИНЦ OpenAlex

Dates:

Submitted:	May 30, 2023
Accepted:	Oct 2, 2023
Published print:	Mar 5, 2024
Published online:	Mar 5, 2024

Identifiers:

Web of science:	WOS:001403291100009
Scopus:	2-s2.0-85191818321
Elibrary:	61885723
OpenAlex:	W4392429480

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

Altmetrics: