EN|RU

Том 19, номер 5, 2012 г., Стр. 63-82

УДК 519.8
Кононова П. А., Кочетов Ю. А. 
Локальный поиск с чередующимися окрестностями для задачи Джонсона с пассивным буфером

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

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

Кононова Полина Александровна 1,2
Кочетов Юрий Андреевич 1,2

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

Статья поступила 12 марта 2012 г.
Исправленный вариант — 14 августа 2012 г.

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