Volume 19, No 1, 2012, P. 59-73
P. A. Kononova
Lower and upper bounds for the optimal makespan in the multimedia problem
We consider a buffer-constrained flow shop problem. We introduce the notion of the restricted problem and show that the original and restricted problems are equivalent. We study two lower bounds for a global optimum. It is shown that the use of the restricted problem can improve the lower bounds. We develop a variable neighborhood search algorithm to obtain the upper bound with some well-known neighborhoods and a new large Kernighan–Lin neighborhood. Computational results show that the proposed method finds optimal solutions or near optimal solutions for difficult examples.
Tab. 1, ill. 3, bibliogr. 10.
Keywords: scheduling, flow shop, local search.
Kononova Polina Aleksandrovna 1
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia