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.