|
Дискретный анализ и исследование операций, 2012, том 19, выпуск 1, страницы 59–73
(Mi da677)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Нижние и верхние оценки длины оптимального расписания презентаций медиа-объектов
П. А. Кононова Институт математики им. С. Л. Соболева СО РАН, Новосибирск, Россия
Аннотация:
Рассматривается задача теории расписаний потокового типа для двух машин с буфером на второй машине. Вводится понятие ограниченной задачи, и показана эквивалентность исходной и ограниченной задач. Исследуются нижние оценки оптимума. Установлено, что переход к ограниченной задаче приводит к улучшению нижних оценок. Для нахождения верхних оценок разработан итерационный метод локального поиска с чередующимися окрестностями. Используются четыре вида окрестностей, в том числе новая окрестность типа Кернигана–Лина. Численные эксперименты показали высокую эффективность предложенного подхода. Для сложных примеров метод локального поиска позволяет быстро найти точное решение или решение с малой относительной погрешностью. Табл. 1, ил. 3, библиогр. 10.
Ключевые слова:
теория расписаний, задача потокового типа, локальный поиск.
Статья поступила: 05.04.2011 Переработанный вариант: 14.07.2011
Образец цитирования:
П. А. Кононова, “Нижние и верхние оценки длины оптимального расписания презентаций медиа-объектов”, Дискретн. анализ и исслед. опер., 19:1 (2012), 59–73
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da677 https://www.mathnet.ru/rus/da/v19/i1/p59
|
Статистика просмотров: |
Страница аннотации: | 311 | PDF полного текста: | 86 | Список литературы: | 36 | Первая страница: | 3 |
|