Том 19, номер 5, 2012 г., Стр. 21-34
УДК 519.8
Великанова Ю. Ю.
Оценки времени работы алгоритмов локального спуска для задачи построения расписаний на параллельных машинах
Аннотация:
Изучаются свойства алгоритмов локального спуска с окрестностями квадратичной мощности для NP-трудной задачи теории расписаний P||Cmax. Получены новые верхние и нижние оценки на время работы алгоритмов локального спуска с заданным направлением выбора соседнего решения.
Библиогр. 11.
Ключевые слова: алгоритм локального спуска, окрестность, время работы алгоритма, верхняя и нижняя границы.
Великанова Юлия Юрьевна 1
1.
Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: julia.velikanova@gmail.com
Статья поступила 13 августа 2009 г.
Исправленный вариант — 14 марта 2012 г.
Литература
[1] Brucker P., Hurink J., Werner F. Improving local search heuristics for some scheduling problems. I // Discrete Appl. Math. — 1996. — Vol. 65, N 1–3. — P. 97–122.
[2] Brucker P., Hurink J., Werner F. Improving local search heuristics for some scheduling problems. II // Discrete Appl. Math. 1997. Vol. 72, N 1–2. P. 47–69.
[3] Brueggemann T. Efficiency of local search: Thes.. . . doct. phylosophy . — Univ. Twente, Enschede, 2006. — 167 p.
[4] Glover F. Tabu search, part I // ORSA J. Comput. — 1989. — Vol. 1, N 3. — P. 190–206.
[5] Glover F. Tabu search, part II // ORSA J. Comput. — 1990. — Vol. 2, N 1. — P. 4–32.
[6] Graham R. L., Lawler E. L., Lenstra J. K., Rinnoy Kan A. H. G. Optimization and approximation in deterministic sequencing and scheduling // Ann. Discrete Math. — 1979. — Vol. 5. — P. 287–326.
[7] Hurkens C. A. J., Vredeveld T. Local search for multiprocessor scheduling: how many moves does it take to a local optimum?// Oper. Res. Lett. — 2003. — Vol. 31. — P. 137–141.
[8] Ibaraki T., Nonobe K., Yagiura M. Metaheuristics: progress as real problem solvers. — Berlin: Springer-Verl., 2005. — 414 p.
[9] Kernighan B.W., Lin S. An efficient heuristic procedure for partitioning graphs // Bell Syst. Tech. J. — 1970. — Vol. 49. — P. 291–307.
[10] Van Laarhoven P. J. M., Aarts E. H. L. Simulated annealing: theory and applications. — Reidel, Dordrecht: Kluwer Acad. Publ., 1987. — 204 p.
[11] Yannakakis M. Computational complexity. Local search in combinatorial optimization. — Chichester: Wiley, 1997. — P. 19–55.
