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

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

Задачи составления расписаний школьных занятий представляют известный класс задач комбинаторной оптимизации. Его исследованию посвящены де-сятки статей, что обусловлено не только широкими приложениями, но и принципиальной трудностью получения точного решения за полиномиальное время. В данной работе исследуется вопрос о построении приближенных решений задачи в случае достаточного числа аудиторий. Несмотря на сделанные упрощения, задача остается NP-трудной, а поиск допустимого решения является NP-полной проблемой.

Для поиска приближенного решения данной задачи предложен алгоритм локального поиска, в основу которого положены идеи пороговых мето-дов. В качестве окрестности рассматривается множество всех расписаний, отличающихся от данного в двух уроках одного преподавателя. Так как задача построения допустимого решения является NP-полной, то вводится понятие полудопустимого решения и поиск ведется в области всех полудопустимых решений. Поведение разработанного алгоритма зависит от выбора начальной точки. Этому вопросу в работе уделяется особое внимание. Начальное полудопустимое решение строится с помощью жадного алгоритма, который использует полиномиально разрешимую задачу о назначениях.

Разработанный алгоритм запрограммирован на языке ПАСКАЛЬ. Проведены численные эксперименты, целью которых было исследовать качество получаемых стартовых точек и их влияние на результат работы порогового алгоритма. Результаты экспериментов свидетельствуют о продуктивности предложенного подхода.

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

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

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

© 2005, Институт Вычислительной Математики и Математической Геофизики СО РАН, Новосибирск
© 2005, Сибирское отделение Российской академии наук, Новосибирск
Администратор страницы: sojconf@sscc.ru