RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskretn. Anal. Issled. Oper., 2012, Volume 19, Number 1, Pages 59–73 (Mi da677)  

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

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.

Full text: PDF file (354 kB)
References: PDF file   HTML file

Bibliographic databases:
UDC: 519.8
Received: 05.04.2011
Revised: 14.07.2011

Citation: 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
\Bibitem{Kon12}
\by P.~A.~Kononova
\paper Lower and upper bounds for the optimal makespan in the multimedia problem
\jour Diskretn. Anal. Issled. Oper.
\yr 2012
\vol 19
\issue 1
\pages 59--73
\mathnet{http://mi.mathnet.ru/da677}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2961452}


Linking options:
  • http://mi.mathnet.ru/eng/da677
  • http://mi.mathnet.ru/eng/da/v19/i1/p59

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. 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  mathnet  crossref  mathscinet
  • Дискретный анализ и исследование операций
    Number of views:
    This page:239
    Full text:51
    References:22
    First page:3

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020