Volume 19, No 5, 2012, P. 21-34
UDC 519.8
Yu. Yu. Velikanova
Running time of local search algorithms for a scheduling problem on the parallel machines
Abstract:
We study behavior of local search algorithms with quadratic neighborhoods for the NP-hard scheduling problem P||Cmax. We obtain new upper and lower bounds for the running time of the local search algorithms with the given pivoting rule.
Bibliogr. 11.
Keywords: local search algorithm, neighborhood, running time of the algorithm, upper and lower bounds.
Velikanova Yuliya Yurievna 1
1. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: julia.velikanova@gmail.com
|