This article is cited in 1 scientific paper (total 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
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.
scheduling, flowshop, local search.
PDF file (354 kB)
P. A. Kononova, “Lower and upper bounds for the optimal makespan in the multimedia problem”, Diskretn. Anal. Issled. Oper., 19:1 (2012), 59–73
Citation in format AMSBIB
\paper Lower and upper bounds for the optimal makespan in the multimedia problem
\jour Diskretn. Anal. Issled. Oper.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
P. A. Kononova, Yu. A. Kochetov, “Variable neighborhood search for two machine flowshop problem with a passive prefetch”, J. Appl. Industr. Math., 7:1 (2013), 54–67
|Number of views:|