Институт вычислительной математики и математической геофизики СОРАН

Пятая азиатская международная школа-семинар "Проблемы оптимизации сложных систем"

Кыргызская Республика, г.Бишкек, база "Эдельвейс" Иссык-Кульского Государственного Университета, 12 - 22 августа.
ВАЖНАЯ ИНФОРМАЦИЯ

Тезисы докладов

АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ ДЖОНСОНА С БУФЕРОМ

Кононова П.А.

Институт математики им. С.Л. Соболева СО РАН (Новосибирск)

Рассматривается следующая задача, возникающая в мультимедиа. Задан набор файлов, составляющих презентацию. Каждый из них должен быть сначала записан в буфер компьютера, а затем выполнен. После выполнения файл удаляется и освобождает занятое место. Задано время записи файла, его размер и время выполнения. Размер буфера ограничен. Необходимо составить порядок записи файлов и порядок их выполнения, при котором время окончания всей презентации будет минимальным.

Сформулированная задача является обобщением классической задачи Джонсона на двух машинах. Она NP--трудна в сильном смысле, так как задача упаковки в контейнеры является ее частным случаем. Для ешения задачи разработан итерационный метод локального поиска с чередующимися окрестностями. В качестве окрестностей используются окрестность Shift --- ставим работу на новое место, Swap -- меняем две работы местами, окрестность Лина-Кернигана --- находим удачную последовательность сдвигов и парных замен работ.

Предложенный метод локального поиска с чередующимися окрестностями показал хорошие результаты. При большом буфере получаются простые примеры, легко решаемые пакетом CPLEX. При малом буфере, в который помещаются 2--3 работы, примеры оказываются сложными и требуют от пакета несколько дней расчетов. Для таких примеров метод локального поиска позволяет быстро найти точное решение или решение с малой относительной погрешностью (до 8 \% относительно линейной релаксации). В численных экспериментах на случайно порожденных данных решение, найденное локальным поиском за 10 секунд расчетов, всегда оказывалось лучше решения, найденного пакетом за 30 минут.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]

© 2009, Институт Вычислительной Математики и Математической Геофизики СО РАН, Новосибирск
© 1996-2009, Сибирское отделение Российской академии наук, Новосибирск
Дата последней модификации: 06-Jul-2012 (11:52:52)