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

Библиографическая ссылка: Кочетов Ю.А. , Ратушный А.В.
Верхние и нижние оценки оптимума для задачи динамической упаковки в контейнеры
Труды Института математики и механики УрО РАН (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

Даты:

Поступила в редакцию:	30 мая 2023 г.
Принята к публикации:	2 окт. 2023 г.
Опубликована в печати:	5 мар. 2024 г.
Опубликована online:	5 мар. 2024 г.

Идентификаторы БД:

Web of science:	WOS:001403291100009
Scopus:	2-s2.0-85191818321
РИНЦ:	61885723
OpenAlex:	W4392429480

Цитирование в БД: Пока нет цитирований

Альметрики: