Running time of local search algorithms for a scheduling problem on the parallel machines

Yu. Yu. Velikanova

Novosibirsk State University, Novosibirsk, Russia

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.

UDC: 519.8

Received: 13.08.2009
Revised: 14.03.2012

Bibliographic databases:

•