This article is cited in 1 paper

Lower and upper bounds for the optimal makespan in the multimedia problem

P. A. Kononova

S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia

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, flowshop, local search.

UDC: 519.8

Received: 05.04.2011
Revised: 14.07.2011

Bibliographic databases:

•