С.Л. Соболева СО РАН, Новосибирск) ГЕНЕТИЧЕСКИЙ ЛОКАЛЬНЫЙ ПОИСК И СЛОЖНОСТЬ АППРОКСИМАЦИИ ЗАДАЧИ БАЛАНСИРОВКИ НАГРУЗКИ НА СЕРВЕРЫ1 Рассматривается известная NP-трудная задача балансировки нагрузки на серверы. <...> Исследуется вычислительная сложность получения приближенных решений с гарантированной оценкой точности. <...> Для решения задачи разработан приближенный метод, основанный на идеях генетического локального поиска. <...> Эта активность позволяет определить нагрузку на каждый сервер в каждый момент времени по каждому параметру. <...> Если нагрузка по каждому параметру не превосходит заданного порога, то сервер находится в рабочем режиме. <...> В противном случае сервер работает с перегрузкой. <...> Предполагается, что для каждого диска известны накладные расходы по каждому параметру при его изъятии с сервера и подключении к любому другому серверу. <...> Начальное распределение дисков по серверам считается известным. <...> Задача состоит в том, чтобы перераспределить диски по серверам и достичь минимальной суммарной перегрузки на всем плановом периоде при ограничениях на накладные 1 Работа выполнена при финансовой поддержке Минобрнауки Республики Казахстан, грант 0115PK00546. <...> Задача балансировки нагрузки на серверы может быть сформулирована в терминах частично-целочисленного линейного программирования [1]. <...> Целочисленные переменные заменяются непрерывными, и оптимальное решение соответствующей задачи линейного программирования используется для получения приближенного решения и оценки его погрешности. <...> Линейное программирование позволяет зафиксировать часть дисков на серверах, сократить размерность задачи и решить оставшуюся подзадачу точно методом ветвей и границ, используя пакет CPLEX. <...> Такой подход позволяет быстро находить оптимальное решение на примерах с нулевой перегрузкой и дает хорошие результаты при большой перегрузке серверов. <...> При малой перегрузке линейное программирование фактически не дает целочисленных <...>