Кочетов Ю. А., Кочетова Н. А. Задача балансировки нагрузки на серверы

ЗАДАЧА БАЛАНСИРОВКИ НАГРУЗКИ НА СЕРВЕРЫ

Статья посвящена новой задаче балансировки нагрузки на серверы, возникающей при оптимизации облачного хостинга веб-приложений и пользовательского контента. Получена математическая модель в терминах частично-целочисленного линейного программирования. Показана NP-трудность задачи. Разработан приближенный алгоритм ее решения с апостериорной оценкой уклонения от оптимума. Проведены вычислительные эксперименты с числом серверов до 20.

Ключевые слова: балансировка загрузки, NP-трудные задачи, целочисленное программирование, приближенные алгоритмы.

Yu. A. Kochetov, N. A. Kochetova
THE SERVERS LOAD BALANCING PROBLEM

The paper is devoted to a new load balancing problem originated from the cloud computing and optimal hosting for the web applications and user’s contents. We present a mixed integer linear programming formulation and show that it is NP-hard problem. We design an approximation algorithm with a posterior bound for the deviation from the optimum. Computational results are conducted with number of servers up to 20.

Keywords: Load balancing, NP-hard problems, integer programming, approximation algorithms.

Вестник НГУ. Серия: Информационные технологии. 2013. Т. 11, вып. 4. С. 71–76.
http://www.nsu.ru/xmlui/handle/nsu/1293