Xl Туполевские чтения : всероссийская (с международным участием) молодежная научная конференция. Казань, 8-10 октября 2003 г., тезисы докладов. Т. 3

Эвристики, применяемые при составлении расписания С.В. Короткова Научный руководитель: А.С. Клевин, ассистент Казанский государственный технический университет им. А.Н.Туполева Поиск оптимального или близкого к оптимальному алгоритма авто­ матизированного составления расписания осуществляется с помощью од­ ного из 4 подходов: математического программирования, комбинаторного, эвристического, статистического (вероятностного); При применении методов математического программирования для решения задач теории расписания неизбежна экспоненциальность време­ ни решения задачи. Широко используются методы ветвей и границ или метод неявного перебора. Эти приемы состоят в построении «частичны:< решений». При составлении расписания второго образования были выде­ лены следующие ограничения: каждая учебная фуппа в один момент вре­ мени может посещать не более одного предмета; преподаватель в один момент времени может проводить занятия не более, чем у одной группы; преподаватель в один момент времени может читать не более, чем одну дисциплину; каждой дисциплине должна быть подобрана соответствую­ щая аудитория; каждой учебной группе в зависимости от количества сту­ дентов должна быть подобрана соответствующая аудитория; каждая учеб­ ная группа в один день может посещать не более двух предметов; Комбинаторный подход сводится к целенаправленной перестановке пар работ в некоторой исходной последовательности, пока не будет полу­ чено оптимальное (близкое к оптимальному) решение. Различают задачи класса Р и NP-полные задачи. NP-полнота задачи определяет построение приближенных или эвристических алгоритмов решения. Идеального решения не существует, поэтому чаще всего использу­ ются условно приближенные методы, которые делятся на эвристические и вероятностные. Эвристические алгоритмы основаны на снижении требова­ ний. Он заключается в поиске приближенного к оптимальному решения. Широко применяется метод локального поиска. При этом заранее выбран­ ное множество перестановок используется для улучшения начального ре­ шения, в противном случае достигается локальный оптимум. Еще одно на­ правление - формирование правил или функций предпочтений (приорите­ тов). Пример расстановки приоритетов при составлении расписания: Группа Дисинплина Аудитория Преподаватель Время варьируется 71