Верхние и нижние оценки оптимума для задачи динамической упаковки в контейнеры

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