Разработка математической модели и ПО для задач составления расписания (работа 1)
Доклад.
Бакалаврская работа на тему “Разработка математической модели и ПО для задач составления расписания”
Уважаемые члены комиссии, вам представляется доклад бакалаврской работы на тему “Разработка математической модели и ПО для задач составления расписания”.
Технологию разработки расписания следует воспринимать не только как трудоемкий технический процесс, объект механизации и автоматизации с использованием ЭВМ, но и как акцию оптимального управления. Таким образом, это - проблема разработки оптимальных расписаний занятий в вузах с очевидным экономическим эффектом. Поскольку интересы участников учебного процесса многообразны, задача составления расписания - многокритериальная.
Многокритериальность этой задачи и сложность объекта, для которого сроится математическая модель, обуславливает необходимость серьезного математического исследования объекта для увеличения функциональных возможностей алгоритмов составления расписаний без значительного усложнения модели и, как следствие, увеличения объемов используемой памяти и времени решения задачи.
В ходе работы на начальном этапе были проанализированы и протестированы существующие на сегодняшний момент программные продукты. Тестирование осуществлялось на основе данных о ЧГУ за 1999/2000 учебный год. Из проанализированных программ только 3 оказались в состоянии составить расписание, удовлетворяющие почти всем требованиям, причем окончательных результатов работы одной программы дождаться так и не удалось, а 2 остальные работали около 3-4 часов.
Поэтому была поставлена задача: создание такой математической модели расписания в вузе, которая позволяла бы эффективно (в заданные сроки и с заданной степенью оптимальности) решать задачу автоматического составления расписания и обладала бы гибкостью (незначительных изменений в случае изменений входной информации) для адаптации системы в рамках конкретной практической задачи. Для некоторого упрощения задачи на начальном этапе проектирования были сделаны некоторые допущения:
расписание составляется из расчета не более двух пар в день (что вполне подходит для случая вечерней формы обучения);
все пары проводятся в одном корпусе;
задача ставится в терминах линейного программирования;
дальнейшая декомпозиция модели не производится;
все коэффициенты модели и искомые переменные целочисленны;
В ходе работы была построена математическая модель расписания в вузе для случая вечерней формы обучения без переходов между корпусами, выбраны методы решения поставленной задачи и разработана модель хранения исходных данных задачи.
Математическая формализация задачи составления расписания выполнялась исходя из принципов (см. плакат 1.):
Вводились целочисленные константы, соответствующие группам, проводимым занятиям, преподавателям, аудиторной нагрузке преподавателей и аудиторному фонду, причем часть из них может принимать только булевы значения.
Вводились булевы переменные, соответствующие паре, на которой проводится то или иное занятие. Для сохранения линейной целочисленности полученной модели потребовалось вводить по 12 переменных на каждое проводимое занятие.
На основе введенных констант и априорной информации о задаче составлялись ограничения на значения булевых переменных.
Целевая функция составлялась таким образом, чтобы максимизировать взвешенное число свободных от аудиторной работы дней для всех преподавателей, что при условии фиксированной длины рабочей недели эквивалентно максимальному совокупному уплотнению аудиторной нагрузки. Все переменные, входящие в целевую функцию, первой степени, и все коэффициенты при переменных постоянны.
Поставленная таким образом задача максимизации линейной целевой функции при заданной системе ограничений является задачей линейного целочисленного булева программирования, поскольку все коэффициенты ограничений целочисленны в силу дискретности исходных данных задачи; кроме этого искомые переменные математической модели могут принимать только два значения. На данный момент времени существует несколько возможных методов решения такого рода задач.
В [3] – [8] описаны методы упорядоченной индексации и модифицированных пометок, основанные на лагранжевой декомпозиции исходной модели на ряд однострочных задач, решаемых соответственно методами упорядочивающей индексации или модифицированных пометок. К сожалению количество операций каждого из методов не допускает полиномиальной оценки; кроме того, размерность таблицы наборов (промежуточных значений) методов резко возрастает при увеличении размерности решаемой задачи, что недопустимо в нашем случае. Возможно, изменение алгоритма декомпозиции под конкретную математическую модель позволит уменьшить размерность таблиц, но пока такого алгоритма не существует.
В связи с этим в качестве методов решения были выбраны описанные в [2] модификации симплекс-метода для случая задачи целочисленного линейного программирования. В общем случае количество операций симплекс-метода не допускает полиномиальной оценки (был даже показан класс задач, для которых количество операций составляет O(en)), но для случая нашей задачи среднее число операций допускает полиномиальную оценку: O(n3m1/(n-1)) (n – количество переменных; m – количество ограничений). Алгоритм работы методов представлен на плакате 2.
Алгоритмы математической формализации модели и методы решения были реализованы в виде программных модулей. Скорость работы алгоритмов была протестирована на разнородных наборах исходных данных, в результате чего были определены возможности и области применения алгоритмов.
Ядро системы и интерфейсная часть были написаны на Delphi 6.0. База данных была реализована на СУБД Oracle 8i, запросы к ней осуществляются на языке PL/SQL.
Алгоритмы решения задачи были протестированы на различных выборках исходных данных. Тестирование производилось на ЭВМ с процессором Intel Pentium 350 Мгц, СУБД Oracle 8i был установлен на двухпроцессорном сервере: 2 CPU Intel Pentium II 350 Мгц, ОЗУ 384 Мб; в качестве канала связи использовалась LAN с пропускной способностью до 100 Мбит/с. В качестве тестовых исходных данных были использованы как реальные данные о группах, преподавателях и читаемых предметах вечерней формы обучения ЧГУ на 1999/2000 учебные годы, так и случайно формируемые исходные данные (читаемым предметам случайным образом определяли аудитории для проведения занятий). В среднем производилось от 5 до 10 тестов для каждой тестируемой размерности исходных данных. В результате получили данные, приведенные на плакате 3.
Анализируя полученные данные можно сделать некоторые выводы о функциональных возможностях алгоритмов решения и математической модели, их недостатках и областях применения.
Во-первых, использованная математическая модель содержит в себе “лишние” ограничения, существование которых обусловлено линейной целочисленной моделью, кроме этого каждому читаемому на потоке (поток может состоять и из одной группы) предмету ставится в соответствие 12 (для случая вечерников) переменных, каждая из которых представляет из себя булеву переменную. Во-вторых, резко возрастает время решения задачи при увеличении входных данных. Это происходит из-за резкого увеличения количества переменных и ограничений в модели, в результате чего возрастает размерность массивов и соответственно время решения задачи. В-третьих, формализованная математически задача охватывает только задачу составления расписания для студентов вечерней формы обучения без учета переходов между корпусами. Учет дополнительных требований увеличит количество ограничений задачи, что отрицательно повлияет на скорость работы алгоритмов решения.
Обратим внимание на возрастающую разницу между минимальным и средним значением времени решения задачи по мере увеличения размерности задачи. Эта разница соответствует тому, насколько “удачно” (наиболее близко к оптимальному) было найдено начальное допустимое базисное решение задачи. Поэтому время решения задачи можно значительно уменьшить, “удачно” найдя начальное базисное допустимое решение. Для поиска такого решения лучше всего использовать эвристические и декомпозиционные алгоритмы.
Отметим, что эвристические и декомпозиционные алгоритмы нельзя использовать в “чистом” виде, поскольку в случае эвристического решения его (решения) оптимальность (или достижение глобального максимума) может быть доказана только полным перебором всех возможных вариантов (ясно, что в этом случае время работы алгоритма будет очень большим), поэтому итерации эвристических алгоритмов прекращаются по достижении некоего максимального (нельзя сказать, локального или глобального) значения. Решение такого алгоритма может быть близким к оптимальному, но не оптимальным. В этом случае для достижения глобального максимума можно использовать рассмотренный в работе способ решения, поскольку оптимум может быть достигнут за несколько итераций представленных на плакате 2. методов решения.