Том 19, номер 1, 2012 г., Стр. 59-73

УДК 519.8
Конoнова П. А. 
Нижние и верхние оценки длины оптимального расписания презентаций медиа-объектов

Аннотация:
Рассматривается задача теории расписаний потокового типа для двух машин с буфером на второй машине. Вводится понятие ограниченной задачи, и показана эквивалентность исходной и ограниченной задач. Исследуются нижние оценки оптимума. Установлено, что переход к ограниченной задаче приводит к улучшению нижних оценок. Для нахождения верхних оценок разработан итерационный метод локального поиска с чередующимися окрестностями. Используются четыре вида окрестностей, в том числе новая окрестность типа Кернигана — Лина. Численные эксперименты показали высокую эффективность предложенного подхода. Для сложных примеров метод локального поиска позволяет быстро найти точное решение или решение с малой относительной погрешностью.
Табл. 1, ил. 2, библиогр. 10.

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

Конoнова Полина Александровна ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: kononova@math.nsc.ru

Статья поступила 5 апреля 2011 г.
Исправленный вариант — 14 июля 2011 г.

Литература

[1] Кононова П. А. Алгоритм локального поиска для задачи выбора порядка презентаций медиа-объектов // Тр. ИВМиМГ. Информатика, 9. — Новосибирск: Изд-во ИВМиМГ СО РАН, 2009.— С. 177–182.

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

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

[4] Hansen P., Mladenovich N. Variable neighborhood search for the $p$-median problem // Locat. Sci. — 1997. — Vol. 5. — P. 207–226.

[5] 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.

[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). — P. 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. Статья принята к печати. DOI: 10.1007/s10951-011-0235-z. 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.— 2009.— Vol. 36, N 4. — P. 1158–1175.

[9] Papadimitriou C. H., Kanellakis P. C. Flowshop scheduling with limited temporary storage // J. ACM. — 1980. — Vol. 27, N 3. — P. 533–549.

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