Недавно здесь проскакивала тема расписания занятий, и мне захотелось рассказать о своем опыте построения алгоритма составления расписания для ВУЗа, а точнее, больше об эвристике, которую применил.
В недалеком 2002 году, заканчивая ВУЗ (Ярославский филиал МЭСИ), специальность «Прикладная информатика в экономике», стояла задача выбора дипломной работы. Предложенный список тем удручил, в основном скучные разработки БД. В принципе мог бы какой-нибудь из моих имеющихся наработок взять за основу, как предлагал зав. кафедры, но кровь бурлила, хотелось сделать что-нибудь интересное и новое для себя. Предложил руководителю тему составления расписания, тем более что работал в ИТ-службе ВУЗа, и в моем ведении была система КИС УЗ (Комплексная информационная система управления учебным заведением), продукт ярославской компании. КИС УЗ была хороша, но составлять расписание сама не могла. Также, этим я преследовал цель сделать что-то полезное, но вышло так, что не было попыток внедрения в жизнь, может хоть публикация на хабре даст кому-нибудь пользу.
Итак, надо было научить компьютер составлять недельное расписание занятий, причем как можно лучше. Осознавая масштабы пространства поиска, не ставил цель нахождения самого лучшего варианта. Для начала надо определить, что собой представляют занятия, и что такое хорошо, а что такое плохо. Была выбрана следующая модель, у которой такие входные данные:
— число дней в неделе
— количество занятий в день
— список преподавателей
— список групп, подгрупп и потоков
— количество аудиторий по определенному типу
— набор групп заданий (занятий):
- занятие
- преподаватель
- поток или группа
- тип аудитории
- количество занятий в данной группе занятий
- время, если постановщик желает «жестко» установить данное занятие в определенное время
Процесс должен расставить занятия на временной сетке – расписание. В оценке расписания участвуют 4 параметра — количество «окон» в расписании у группы и преподавателей, равномерное распределение занятий по дням у группы и преподавателей. Значимость этих параметров задает постановщик. Сначала хотел применить метод анализа иерархий в целевой функции, но пришлось бы ввести попарное сравнение этих параметров, поэтому обошелся линейной функцией.
Что касается аудиторий, то я пошел на упрощение, убрал его из расписания, сделав ограничением, при поиске количество свободных аудиторий на конкретное время учитывалась. После генерации расписания во времени – расставлялись аудитории. В общем, вот такую простую модель я и очертил. Поэкспериментировал немножко с генетическим алгоритмом, на основе библиотеки в течение дня набросал программку, однако результат не понравился, и я, недолго думая, переключился на другие алгоритмы. Думаю, нехороший результат получился из-за моего неосновательного подхода, скорее всего, неудачно закодировал модель в терминах ГА. Начал думать о методе ветвей и границ. Пространство поиска представляет собой дерево, где уровень означает занятие, а ветвь – элемент сетки времени. Расписание считается путь от корня дерева до одной из висячих вершин. В пути, в процессе ветвления, проверяется возможность и целесообразность обхода по разным признакам: занятость преподавателя, группы, оценка. Обход дерева, естественно, вглубь. На каждом уровне находятся свободные ячейки сетки для текущего задания. Если постановщик «жестко» закрепил данное задание на определенное время, то строится одна ветвь, соответствующая определенному времени. Далее, проходя по ветви, находится оценка верхней границы (плюс к этому ведется контроль на наличие свободных аудиторий данного типа), и если оценка верхней границы выше оценки найденного лучшего на текущий момент расписания (и если есть свободная аудитория данного типа), то проходим по ветви, иначе переходим на следующую ветвь. В методе ветвей и границ ключевым и важным моментом является алгоритм нахождения оценки верхней границы. Не мудрствуя лукаво, оценивал текущее неполное расписание, и сравнивал с текущим лучшим найденным расписанием. Так как, погружаясь далее, оценка неполного расписания будет становиться хуже, то если она уже хуже оценки лучшего расписания, то ветвь бракуется. И так, запрограммировав все это дело, подготовив данные (брал из системы на основе реальных данных) запустил вечером и ушел домой. Утром, придя на работу, загрузил в КИС УЗ полученное лучшее из миллиарда найденных расписаний, однако без слез нельзя было на это смотреть. Я был разочарован, удручен и не знал, что дальше делать. Вечером пошли с друзьями попить пивка, и вот стою на остановке под хмелем и жду последний трамвай, а в голове одни деревья, ветви, границы, оценки… и тут до меня доходит, что надо каким то образом на каждом уровне, при определении ветвей, их сортировать, сделать так, чтобы сначала шли те варианты, которые вероятнее других были бы в составе лучшего расписания. Но каким образом это сделать? Мысль пришла, когда уже докуривал вторую сигарету. Надо, предварительно, строить для каждого субъекта расписания свои идеальные расписания, и для каждой ветви вычислять степень попадания в эти расписания, и сортировать по ней. Утром на работу шел быстрее обычного, по дороге рисуя в голове технические детали, к обеду эвристика была встроена, результат выглядел в КИС УЗ вполне достойно, и оставшиеся полрабочего дня я улыбался.
PS. Позднее, когда услышал о PageRank, подумал, что есть в нем нечто схожее с этой эвристикой.
Автор: optimizer
