Нижние и верхние оценки длины оптимального расписания презентаций медиа-объектов

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