Том 19, номер 5, 2012 г., Стр. 63-82

УДК 519.8
Кононова П. А., Кочетов Ю. А. 
Локальный поиск с чередующимися окрестностями для задачи Джонсона с пассивным буфером

Аннотация:
Рассматривается задача теории расписаний потокового типа для двух машин с пассивной загрузкой буфера на второй машине. Для вычисления нижних оценок оптимума предложены четыре формулировки задачи в терминах целочисленного линейного программирования. Для нахождения верхних оценок разработаны три варианта метода локального поиска с чередующимися окрестностями. Наряду с известными полиномиальными окрестностями используется новая окрестность экспоненциальной мощности. Для проведения численных экспериментов построен новый класс тестовых примеров с известным значением оптимума. Результаты численных экспериментов на этом и других классах показали высокую эффективность разработанного подхода.
Ил. 1, табл. 4, библиогр. 13.

Ключевые слова: теория расписаний, локальный поиск, экспоненциальная окрестность.

Кононова Полина Александровна ^1,2
Кочетов Юрий Андреевич ^1,2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: polinusik@gorodok.net, jkochet@math.nsc.ru

Статья поступила 12 марта 2012 г.
Исправленный вариант — 14 августа 2012 г.

Литература

[1] Кононова П. А. Нижние и верхние оценки длины оптимального расписания презентаций медиа-объектов // Дискрет. анализ и исслед. операций. — 2012. — Т. 19, № 1. — С. 59–73.

[2] Кочетов Ю. A., Младенович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискрет. анализ и исслед. операций. Сер. 2. — 2003. — Т. 10, № 1. — С. 11—43.

[3] Brimberg J., Hansen P., Mladenovi$\acute{c}$ 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. — 2011. — Vol. 6622. — P. 38–47.

[5] Falkenauer E. A hybrid grouping genetic algorithm for bin packing // J. Heuristics. — 1996. — Vol. 2, N 1.— P. 5–30.

[6] Ierapetritou M. G., Floudas C. A. Effective continuous-time formulation for shortterm scheduling: I. Multipurpose batch process // Ind. Eng. Chem. Res. — 1998. — Vol. 37. — P. 4341–4359.

[7] Johnson S. M. Optimal two- and three-stage production scheduling with setup time included // Naval Res. Logist. — 1954. — Vol. 1. — P. 61–68.

[8] Kochetov Yu., Alekseeva E., Levanova T., Loresh M. Large neighborhood local search for the $p$-median problem // Yugosl. J. Oper. Res. — 2005. — Vol. 15, N 1. — P. 53–63.

[9] Kоchetov Yu., Kononova P., Paschenko M. Formulation space search approach for the teacher/class timetabling problem // Yugosl. J. Oper. Res. — 2008. — Vol. 18, N 1. — P. 1–11.

[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). Moscow: Trapeznikov Institute of Control Sciences, 2009. — P. 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. — 2012. — Vol. 15, N 4. —P. 487–497.

[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. — 2009. — Vol. 36, N 4. — P. 1158–1175.

[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). — Praha: Institute for Theoretical Computer Science (ITI) Charles University, 2011. — P. 177–179.