EN|RU

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

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

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

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

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

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

 © Институт математики им. С. Л. Соболева, 2015