Введение в эволюционное моделирование. Каширина И.Л. - 36 стр.

                                   36

                         ПРИЛОЖЕНИЕ
 Математическая модель и генетический алгоритм для реше-
      ния задачи составления школьного расписания
      Как известно, задача составления школьного расписания является пло-
хоформализуемой и труднорешаемой. Школьное расписание является до-
вольно сложной системой, все элементы которой взаимосвязаны между со-
бой напрямую или косвенно. Помимо большого количества условий, кото-
рые приходится строго выполнять, необходимо оптимизировать множество
параметров, влияющих на качество расписания. Поскольку интересы участ-
ников учебного процесса многообразны, задача составления расписания по
сути еще и многокритериальная. Размерность задачи, не позволяющая наде-
яться на отыскание ее точного решения, и сложность объекта, для которого
строится математическая модель, обусловливают необходимость серьезного
математического исследования задачи с целью увеличения функциональных
возможностей алгоритмов составления расписаний.
      Рассмотрим одну из возможных постановок задачи составления
школьного расписания и метод ее решения, основанный на использовании
генетического алгоритма. Представленный алгоритм, хотя и является при-
ближенным, позволяет выполнить все обязательные условия, учитывая при
этом многокритериальность поставленной задачи.
                            Постановка задачи
   Формально задачу составления учебного расписания можно поставить
следующим образом.
   Заданы множество преподавателей P, множество учебных групп K, мно-
жество учебных дисциплин (предметов) U, учебный план, фиксирующий ко-
личество часов каждого предмета в каждом классе, множество кабинетов
(аудиторий) A. Требуется найти расписание, обеспечивающее проведение
всех занятий без накладок относительно аудиторий, без пустых уроков
(“окон”) для учащихся и удовлетворяющее обязательным требованиям пре-
подавателей. Кроме этих необходимых условий, на расписание накладыва-
ются дополнительные требования такие, как, например, выполнение норм
СанПин, касающихся правил распределения нагрузки в течение учебной не-
дели и расстановки уроков в течение учебного дня.
Элементом расписания является учебная дисциплина (предмет), которой
ставится в соответствие учебная группа и преподаватель, а так же указыва-
ется, требуется ли для ее проведения специальная аудитория (например,
компьютерный класс или химическая лаборатория) или нет. Причем счита-
ется, что если для какого-то класса предусмотрено 4 урока математики, то
это 4 разные элемента расписания. Все предметы перенумеровываются и за-