EN|RU

Том 19, номер 5, 2012 г., Стр. 21-34

УДК 519.8
Великанова Ю. Ю. 
Оценки времени работы алгоритмов локального спуска для задачи построения расписаний на параллельных машинах

Аннотация:
Изучаются свойства алгоритмов локального спуска с окрестностями квадратичной мощности для NP-трудной задачи теории расписаний P||Cmax. Получены новые верхние и нижние оценки на время работы алгоритмов локального спуска с заданным направлением выбора соседнего решения.
Библиогр. 11.

Ключевые слова: алгоритм локального спуска, окрестность, время работы алгоритма, верхняя и нижняя границы.

Великанова Юлия Юрьевна 1
1. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: julia.velikanova@gmail.com

Статья поступила 13 августа 2009 г.
Исправленный вариант — 14 марта 2012 г.

 © Институт математики им. С. Л. Соболева, 2015