Geodesic
Variable neighborhood search for two machine flowshop problem with a~passive prefetch
Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 5, pp. 63-82.

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

We consider the two machine flowshop scheduling problem with passive loading of the buffer on the second machine. To compute lower bounds for the global optimum, we present four integer linear programming formulations of the problem. Three local search methods with variable neighborhoods are developed for obtaining upper bounds. A new large neighborhood is designed. Our methods use this neighborhood along with some other well-known neighborhoods. For computational experiments, we present a new class of test instances with known global optima. Computational results indicate the high efficiency of the proposed approach for the new class of instances as well as for other classes of instances. Ill. 1, tab. 4, bibliogr. 13.
Keywords: scheduling theory, local search, exponential neighborhoods. 
@article{DA_2012_19_5_a4,
     author = {P. A. Kononova and Yu. A. Kochetov},
     title = {Variable neighborhood search for two machine flowshop problem with a~passive prefetch},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {63--82},
     publisher = {mathdoc},
     volume = {19},
     number = {5},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2012_19_5_a4/}
}
TY  - JOUR
AU  - P. A. Kononova
AU  - Yu. A. Kochetov
TI  - Variable neighborhood search for two machine flowshop problem with a~passive prefetch
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2012
SP  - 63
EP  - 82
VL  - 19
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2012_19_5_a4/
LA  - ru
ID  - DA_2012_19_5_a4
ER  - 
%0 Journal Article
%A P. A. Kononova
%A Yu. A. Kochetov
%T Variable neighborhood search for two machine flowshop problem with a~passive prefetch
%J Diskretnyj analiz i issledovanie operacij
%D 2012
%P 63-82
%V 19
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2012_19_5_a4/
%G ru
%F DA_2012_19_5_a4
P. A. Kononova; Yu. A. Kochetov. Variable neighborhood search for two machine flowshop problem with a~passive prefetch. Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 5, pp. 63-82. http://geodesic.mathdoc.fr/item/DA_2012_19_5_a4/

[1] Kononova P. A., “Nizhnie i verkhnie otsenki dliny optimalnogo raspisaniya prezentatsii media-ob'ektov”, Diskret. analiz i issled. operatsii, 19:1 (2012), 59–73 | MR

[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] Brimberg J., Hansen P., Mladenović N., Convergence of variable neighborhood search, Les Cahiers du GERAD G–2000–73, Montreal, Canada, 2000

[4] Croce F. D., Grosso A., Salassa F., “A matheuristic approach for the total completion time two-machines permutation flow shop problem”, Lect. Notes Comput. Sci., 6622, 2011, 38–47 | DOI

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

[6] Ierapetritou M. G., Floudas C. A., “Effective continuous-time formulation for shortterm scheduling: I. Multipurpose batch process”, Ind. Eng. Chem. Res., 37 (1998), 4341–4359 | DOI

[7] Johnson S. M., “Optimal two- and three-stage production scheduling with setup time included”, Naval Res. Logist., 1 (1954), 61–68 | DOI

[8] Kochetov Yu., Alekseeva E., Levanova T., Loresh M., “Large neighborhood local search for the $p$-median problem”, Yugosl. J. Oper. Res., 15:1 (2005), 53–63 | DOI | MR

[9] 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

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

[11] 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., 15:4 (2012), 487–497 | DOI | MR

[12] 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

[13] Sevastianov S., Lin B. M. T., “Efficient enumeration of optimal and approximate solutions of the two-machine flow-shop problem”, Preprint of 10th Workshop on Models and Algorithms for Planning and Scheduling Problems (Nymburk, Czech Republic, July 19–24, 2007), Institute for Theoretical Computer Science (ITI) Charles University, Praha, 2011, 177–179