Локальный поиск с чередующимися окрестностями для задачи Джонсона с пассивным буфером

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