Volume 19, No 1, 2012, P. 59-73

UDC 519.8
P. A. Kononova 
Lower and upper bounds for the optimal makespan in the multimedia problem

Abstract:
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. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: kononova@math.nsc.ru