Доклад. Бакалаврская работа на тему "Разработка математической модели и ПО для задач составления расписания"
    Уважаемые члены комиссии, вам представляется доклад бакалаврской работы на тему "Разработка математической модели и ПО для задач составления расписания".
    Технологию разработки расписания следует воспринимать не только как трудоемкий технический процесс, объект механизации и автоматизации с использованием ЭВМ, но и как акцию оптимального управления. Таким образом, это - проблема разработки оптимальных расписаний занятий в вузах с очевидным экономическим эффектом. Поскольку интересы участников учебного процесса многообразны, задача составления расписания - многокритериальная.
    Многокритериальность этой задачи и сложность объекта, для которого сроится математическая модель, обуславливает необходимость серьезного математического исследования объекта для увеличения функциональных возможностей алгоритмов составления расписаний без значительного усложнения модели и, как следствие, увеличения объемов используемой памяти и времени решения задачи. В ходе работы на начальном этапе были проанализированы и протестированы существующие на сегодняшний момент программные продукты. Тестирование осуществлялось на основе данных о ЧГУ за 1999/2000 учебный год. Из проанализированных программ только 3 оказались в состоянии составить расписание, удовлетворяющие почти всем требованиям, причем окончательных результатов работы одной программы дождаться так и не удалось, а 2 остальные работали около 3-4 часов.
    Поэтому была поставлена задача: создание такой математической модели расписания в вузе, которая позволяла бы эффективно (в заданные сроки и с заданной степенью оптимальности) решать задачу автоматического составления расписания и обладала бы гибкостью (незначительных изменений в случае изменений входной информации) для адаптации системы в рамках конкретной практической задачи. Для некоторого упрощения задачи на начальном этапе проектирования были сделаны некоторые допущения: - расписание составляется из расчета не более двух пар в день (что вполне подходит для случая вечерней формы обучения); - все пары проводятся в одном корпусе; - задача ставится в терминах линейного программирования; - дальнейшая декомпозиция модели не производится; - все коэффициенты модели и искомые переменные целочисленны; В ходе работы была построена математическая модель расписания в вузе для случая вечерней формы обучения без переходов между корпусами, выбраны методы решения поставленной задачи и разработана модель хранения исходных данных задачи.
    Математическая формализация задачи составления расписания выполнялась исходя из принципов (см. плакат 1.): 1. Вводились целочисленные константы, соответствующие группам, проводимым занятиям, преподавателям, аудиторной нагрузке преподавателей и аудиторному фонду, причем часть из них может принимать только булевы значения. 2. Вводились булевы переменные, соответствующие паре, на которой проводится то или иное занятие. Для сохранения линейной целочисленности полученной модели потребовалось вводить по 12 переменных на каждое проводимое занятие. 3. На основе введенных констант и априорной информации о задаче составлялись ограничения на значения булевых переменных. 4. ............