Geodesic
Running time of local search algorithms for a~scheduling problem on the parallel machines
Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 5, pp. 21-34.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2012_19_5_a1,
     author = {Yu. Yu. Velikanova},
     title = {Running time of local search algorithms for a~scheduling problem on the parallel machines},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {21--34},
     publisher = {mathdoc},
     volume = {19},
     number = {5},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2012_19_5_a1/}
}
TY  - JOUR
AU  - Yu. Yu. Velikanova
TI  - Running time of local search algorithms for a~scheduling problem on the parallel machines
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2012
SP  - 21
EP  - 34
VL  - 19
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2012_19_5_a1/
LA  - ru
ID  - DA_2012_19_5_a1
ER  - 
%0 Journal Article
%A Yu. Yu. Velikanova
%T Running time of local search algorithms for a~scheduling problem on the parallel machines
%J Diskretnyj analiz i issledovanie operacij
%D 2012
%P 21-34
%V 19
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2012_19_5_a1/
%G ru
%F DA_2012_19_5_a1
Yu. Yu. Velikanova. Running time of local search algorithms for a~scheduling problem on the parallel machines. Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 5, pp. 21-34. http://geodesic.mathdoc.fr/item/DA_2012_19_5_a1/

[1] Brucker P., Hurink J., Werner F., “Improving local search heuristics for some scheduling problems. I”, Discrete Appl. Math., 65:1–3 (1996), 97–122 | DOI | MR | Zbl

[2] Brucker P., Hurink J., Werner F., “Improving local search heuristics for some scheduling problems. II”, Discrete Appl. Math., 72:1–2 (1997), 47–69 | DOI | MR | Zbl

[3] Brueggemann T., Efficiency of local search, Thes. $\dots$ doct. phylosophy, Univ. Twente, Enschede, 2006, 167 pp. | MR

[4] Glover F., “Tabu search. I”, ORSA J. Comput., 1:3 (1989), 190–206 | DOI | Zbl

[5] Glover F., “Tabu search. II”, ORSA J. Comput., 2:1 (1990), 4–32 | DOI | Zbl

[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., 5 (1979), 287–326 | DOI | MR | Zbl

[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., 31 (2003), 137–141 | DOI | MR | Zbl

[8] Ibaraki T., Nonobe K., Yagiura M., Metaheuristics: progress as real problem solvers, Springer-Verl., Berlin, 2005, 414 pp. | MR

[9] Kernighan B. W., Lin S., “An efficient heuristic procedure for partitioning graphs”, Bell Syst. Tech. J., 49 (1970), 291–307 | Zbl

[10] Van Laarhoven P. J. M., Aarts E. H. L., Simulated annealing: theory and applications, Reidel, Kluwer Acad. Publ., Dordrecht, 1987, 204 pp. | MR

[11] Yannakakis M., “Computational complexity”, Local search in combinatorial optimization, Wiley, Chichester, 1997, 19–55 | MR | Zbl