Volume 19, No 5, 2012, P. 63-82

UDC 519.8
P. A. Kononova, Yu. A. Kochetov 
Variable neighborhood search for two machine flowshop problem with a passive prefetch

Abstract:
We consider the two machine flowshop scheduling problem with passive loading of the buffer on the second machine. To compute lower bounds for the global optimum, we present four integer linear programming formulations of the problem. Three local search methods with variable neighborhoods are developed for obtaining upper bounds. A new large neighborhood is designed. Our methods use this neighborhood along with some other well-known neighborhoods. For computational experiments, we present a new class of test instances with known global optima. Computational results indicate the high efficiency of the proposed approach for the new class of instances as well as for other classes of instances. 
Ill. 1, tab. 4, bibliogr. 13.

Keywords: scheduling theory, local search, exponential neighborhoods.

Kononova Polina Alexandrovna ^1,2
Kochetov Yury Andreevich ^1,2
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: polinusik@gorodok.net, jkochet@math.nsc.ru