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||C_max. 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. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: julia.velikanova@gmail.com