Geodesic
Lower and upper bounds for the optimal makespan in the multimedia problem
Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 1, pp. 59-73.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2012_19_1_a4,
     author = {P. A. Kononova},
     title = {Lower and upper bounds for the optimal makespan in the multimedia problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {59--73},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2012_19_1_a4/}
}
TY  - JOUR
AU  - P. A. Kononova
TI  - Lower and upper bounds for the optimal makespan in the multimedia problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2012
SP  - 59
EP  - 73
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2012_19_1_a4/
LA  - ru
ID  - DA_2012_19_1_a4
ER  - 
%0 Journal Article
%A P. A. Kononova
%T Lower and upper bounds for the optimal makespan in the multimedia problem
%J Diskretnyj analiz i issledovanie operacij
%D 2012
%P 59-73
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2012_19_1_a4/
%G ru
%F DA_2012_19_1_a4
P. A. Kononova. Lower and upper bounds for the optimal makespan in the multimedia problem. Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 1, pp. 59-73. http://geodesic.mathdoc.fr/item/DA_2012_19_1_a4/

[1] Kononova P. A., “Algoritm lokalnogo poiska dlya zadachi vybora poryadka prezentatsii media-ob'ektov”, Tr. IVMiMG. Informatika, 9, Izd-vo IVMiMG SO RAN, Novosibirsk, 2009, 177–182

[2] Kochetov Yu. A., Mladenovich N., Khansen P., “Lokalnyi poisk s chereduyuschimisya okrestnostyami”, Diskret. analiz i issled. operatsii. Ser. 2, 10:1 (2003), 11–43 | MR | Zbl

[3] Falkenauer E., “A hybrid grouping genetic algorithm for bin packing”, J. Heuristics, 2:1 (1996), 5–30 | DOI | MR

[4] Hansen P., Mladenovich N., “Variable neighborhood search for the $p$-median problem”, Locat. Sci., 5 (1997), 207–226 | DOI | MR | Zbl

[5] Kochetov Yu., Kononova P., Paschenko M., “Formulation space search approach for the teacher/class timetabling problem”, Yugosl. J. Oper. Res., 18:1 (2008), 1–11 | DOI | MR | Zbl

[6] Kononov A., Kononova P., Hong J.-S., “Two-stage multimedia scheduling problem with an active prefetch model”, Preprints 13th IFAC Symp. Inf. Control Problems in Manufacturing (Moscow, Russia, June 3–5, 2009), 1997–2002

[7] Kononov A., Hong J.-S., Kononova P., Lin F.-C., “Quantity-based buffer-constrained two machine flowshop problem: active and passive prefetch models for multimedia applications”, J. Sched. (to appear) http://www.springerlink.com/content/82762q4066w16th8/

[8] Lin F.-C., Hong J.-S., Lin B. M. T., “A two-machine flow shop problem with processing time-dependent buffer constraints – An application in multimedia problem”, Comput. Oper. Res., 36:4 (2009), 1158–1175 | DOI | Zbl

[9] Papadimitriou C. H., Kanellakis P. C., “Flowshop scheduling with limited temporary storage”, J. ACM, 27:3 (1980), 533–549 | DOI | MR | Zbl

[10] CPLEX http://www-142.ibm.com/software/products/ru/ru/ilogcple/