Variable neighborhood search for two machine flowshop problem with a passive prefetch

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.