Том 21, номер 6, 2014 г., Стр. 21-34

УДК 519.87
Давыдов И. А., Кононова П. А., Кочетов Ю. А.
Локальный поиск с окрестностью экспоненциальной мощности для задачи балансировки нагрузки на серверы

Аннотация:
Для решения задачи балансировки нагрузки на серверы предложен метод локального поиска с оригинальной окрестностью экспоненциальной мощности. Исследуются варианты локального поиска с рандомизированными версиями такой окрестности. Приводятся результаты численных экспериментов, свидетельствующие о высокой эффективности предложенного подхода.
Ил. 1, табл. 4, библиогр. 15.

Ключевые слова: локальный поиск, задача о назначениях, балансировка нагрузки.

Давыдов Иван Александрович ^1,2
Кононова Полина Александровна ^1,2
Кочетов Юрий Андреевич ^1,2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: vann.davydov@gmail.com, polik83@ngs.ru, jkochet@math.nsc.ru

Статья поступила 11 апреля 2014 г.
Исправленный вариант — 22 мая 2014 г.

Литература

[1] Береснев В. Л., Гончаров Е. Н., Мельников А. А. Локальный поиск по обобщённой окрестности для задачи оптимизации псевдобулевых функций // Дискрет. анализ и исслед. операций. - 2011. - Т. 18, №4. - С. 3–16.
Beresnev V. L., Goncharov E. N., Melnikov A. A. Local search over generalized neighborhood for an optimization problem of pseudo-Boolean functions // J. Appl. Industr. Math. - 2012. - Vol. 6, N1. - P. 22–30.

[2] Давыдов И. А., Кочетов Ю. А., Младенович Н., Уросевич Д.
Быстрые метаэвристики для дискретной задачи о (r|p)-центроиде // Автоматика и телемеханика. - 2014. - T. 75, №4. - С. 106–119.
Davydov I., KochetovYu., Mladenovic N., Urosevich D. Fast metaheuristics for the discrete (r|p)-centroid problem // Autom. Remote Control. - 2014. - Vol. 75, N4. - P. 677-687.

[3] Кононова П. А., Кочетов Ю. А. Локальный поиск с чередующимися окрестностями для задачи Джонсона с пассивным буфером // Дискрет. анализ и исслед. операций. - 2012. - Т. 19, №5. - С. 63–82.
Kononova P. A., Kochetov Yu. A. The variable neighborhood search for the two machine flow shop problem with a passive prefetch // J. Appl. Industr. Math. - 2013. - Vol. 7, N1. - P. 54–67.

[4] Кочетов Ю. А., Кочетова Н. А. Задача балансировки нагрузки на серверы // Вестн. Новосиб. гос. ун-та. Сер. Информ. технологии. - 2013. - Т. 11, вып. 4. - С. 71–76.

[5] Мельников А. А. Рандомизированный локальный поиск для дискретной задачи конкурентного размещения предприятий // Автоматика и телемеханика. - 2014. - T. 75, №4. - С. 134-152.
Melnikov A. Randomized local search for the discrete competitive facility location problem // Autom. Remote Control. - 2014. - Vol. 75, N4. - P. 700–714.

[6] Ahuja R. K., Ergun O., Orlin J. B., Punnen A. P. A survey of very largescale neighborhood search techniques // Discrete Appl. Math. - 2002. - Vol. 123, N1–3. - P. 75–102.

[7] Davydov I. A., Kochetov Yu. A., Carrizosa E. A local search heuristic for the (r|p)-centroid problem in the plane // Comput. Oper. Res. - 2014. - Vol. 52, Part B. - P. 334-340.

[8] Gutin G. Exponential neighborhood local search for the traveling salesman problem // Comput. Oper. Res. - 1999. - Vol. 26. - P. 313–320.

[9] Gutin G., Yeo A. Small diameter neighborhood graphs for the traveling salesman problem: four moves from tour to tour // Comput. Oper. Res. - 1999. - Vol. 26. - P. 321–327.

[10] Hansen P., Mladenovich N. Variable neighborhood search // Eur. J. Oper. Res. - 2001. - Vol. 13. - P. 449–467.

[11] Kochetov Yu., Alekseeva E., Levanova T., Loresh M. Large neighborhood local search for the p-median problem // Yugoslav. J. Oper. Res. - 2005. - Vol. 15, N1. - P. 53–63.

[12] Kоchetov Yu., Kononova P., Paschenko M. Formulation space search approach for the teacher/class timetabling problem // Yugoslav. J. Oper. Res. - 2008. - Vol. 18, N1. - P. 1–11.

[13] Marti R. Multi-start methods // Handbook of metaheuristics. - Dordrecht: Kluwer Acad. Publ., 2003. - P. 355–368.

[14] Talbi E.-G. Metaheuristics: from design to implementation. - Berlin: Wiley, 2009. -624 p.

[15] Yannakakis M. Computational complexity // Local search in combinatorial optimization. - Chichester: Wiley, 1997. - P. 19–55.