МЕТОДЫ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ СОСТАВЛЕНИЯ РАСПИСАНИЯ В УСЛОВИЯХ УЧЕБНОГО ЗАВЕДЕНИЯ

Расписание учебных занятий – это документ, регламентирующий работу студентов, преподавателей, всего учебного заведения, распределяющий содержание учебного плана и рабочих программ по календарным дням учебного года и обеспечивающий их реализацию. Расписание влияет на комфортность обучения студентов, творческую отдачу преподавателей и эффективность использования ресурсов аудиторного фонда и лабораторий. С экономической точки зрения при составлении эффективного расписания можно уменьшить затраты на электроэнергию, водоснабжение и отопление [1].

Задачи теории расписаний имеют не только важное теоретическое значение, как относящееся к классу NP-полных задач, но и получили широкое практическое распространение. Построение оптимального плана распределения занятий может занять многие месяцы, при использовании точных методов решения. Возникает необходимость в методах, характеризующихся сочетанием противоречивых свойств: полиноминальной зависимостью времени счета от размерности задачи и точностью близкой к оптимальной. К такому классу методов относятся различные эвристические методы, не имеющие строгого математического обоснования, но хорошо зарекомендовавших себя в практической сфере [2].

Определим некоторые понятия:

Ограничения – требования, которым обязательно должно соответствовать расписание (отсутствие накладок и др.), влияют на допустимость расписания.

Предпочтения – ограничения, выполнение которых желательно, влияют на эффективность расписания.

Методы составления расписания

1. Методы целочисленного программирования

   Задача целочисленного программирования сводится к выделению переменных, значение которых необходимо найти, составлению математической модели задачи в виде ограничений, которые описывают задачу и накладывают определенные ограничения на искомые переменные, и составление целевой функции [3,4].

   Применение алгоритма:

   1. выделение переменных;
   2. составление математической модели (выделение ограничений для переменных);
   3. составление целевой функции;
   4. нахождение максимума (минимума) целевой функции с помощью математических методов.

   Основные недостатки:

   1. экспоненциальное увеличение временных затрат на поиск лучшего (приемлемого) решения с ростом размерности решаемой задачи;
   2. отсутствие гарантии получения приемлемого решения;
   3. в силу большой размерности математической модели сложно оценить влияние разных факторов процесс решения задачи и его результат;
   4. сложность учета предпочтений.

2. Метод теории графов

   В этом случае строится неориентированный граф, в котором каждая вершина представляет собой запланированное учебным планом занятие. Если между какими-то двумя вершинами возможны конфликты, то они соединяются ребром. Это эквивалентно запрету одновременного проведения занятий. Тогда задача сводится к раскраске графа в заданное количество цветов [4].

   Применение алгоритма:

   1. выделение множества занятий в учебном плане;
   2. представление каждого занятия в виде вершины графа;
   3. соединение вершин графа ребрами в случае невозможности одновременного проведения занятий;
   4. решение задачи раскраски графа в заданное количество цветов.

   Основные недостатки:

   1. малая эффективность при применении точных методов для раскраски графов большой размерности;
   2. отсутствие возможности учета предпочтений.

   Преимущества:

   1. простая в понимании математическая модель;
   2. применение графа вместе с эвристическими методами может давать хорошие результаты.

3. Агентный подход

   Суть применения агентного подхода для решения какой-либо задачи следующая – разбиение задачи на некоторые более мелкие задачи. Для решения каждой из которых выделяется агент. Цель агента – найти такое решение своей задачи, чтобы оно согласовалось с решениями других агентов. Агенты добиваются согласования друг с другом путем обмена информационными сообщениями [5].

   Применение алгоритма:

   1. разбиение глобальной задачи на более мелкие подзадачи;
   2. для каждого вида подзадачи реализуется особый вид агентов;
   3. составление модели пространства, в котором действуют агенты в виде правил и аксиом;
   4. составление онтологии понятий;
   5. замещение всех пользователей расписания агентами, целью каждого найти оптимальное (для себя) расписание.

   Основные недостатки:

   1. отсутствует гарантия получения приемлемого решения задачи построения расписания занятий (на тестах соревнования ITC 2007 мульти-агентная система не нашла ни одного допустимого расписания [5]);
   2. практически невозможным становится оценка влияния значений параметров для внутренней логики каждого из агентов на результат решения задачи.

   Преимущества:

   1. возможность гибкой настройки индивидуальных предпочтений за счет возможности реализации собственной логики для каждого из агентов;
   2. возможность динамического изменения предпочтений.

4. Метод муравьиной колонии

   Основан на способности муравьев находить кратчайшие пути к пище с помощью выделения феромона [6].

   Применение алгоритма:

   1. представить задачу в виде взвешенного графа;
   2. определить значение следа феромона;
   3. определить эвристику поведения муравья при построении решения;
   4. реализовать локальный поиск.

   Основные недостатки:

   1. сходимость алгоритма гарантируется, но время сходимости не определено;
   2. высокая итеративность алгоритма;
   3. результат работы метода сильно зависит от начальных параметров поиска, которые подбираются экспериментально;
   4. теоретический анализ значения начальных параметров затруднен, исследования являются больше экспериментальными.

   Преимущества:

   1. может использоваться в динамических приложениях;
   2. использует память всей колонии, что достигается за счет моделирования выделения феромонов;
   3. сходимость к оптимальному решению гарантируется.

5. Метод имитации отжига

   Алгоритм имитации отжига основывается на имитации физического процесса, который происходит при кристаллизации вещества из жидкого состояния в твердое [7].

   Применение алгоритма:

   1. составить корректное расписание и задать высокое значение температуры T = T₀;
   2. изменить расписание Z = Z';
   3. вычислить целевую функцию для измененного расписания Δ = f(Z') – f(Z);
   4. заменить предыдущее расписание полученным, если оно является лучше предыдущего (Δ ≤ 0), если нет, то вероятность замены p = e^–Δf/T;
   5. понизить температуру;
   6. пока не выполнен критерий остановки переход к пункту 2.

   Основные недостатки:

   1. малоэффективен для составления расписаний в современных системах массового образования в виду большой размерности задачи;
   2. для получение эффективного решения необходимо применять схему Больцмана, или Коши, что приводит к значительным затратам вычислительных мощностей.

6. Генетический алгоритм

   Генетические алгоритмы основаны на использовании механизмов теории естественной эволюции [8, 9].

   Применение алгоритма:

   1. сгенерировать случайным образом популяцию размера P;
   2. вычислить целевую функцию;
   3. выполнить операцию репродукции;
   4. выполнить операцию скрещивания;
   5. выполнить операцию мутации;
   6. выполнить оператор редукции;
   7. проверит критерий останова и, если он не достигнут, перейти к шагу 2, иначе завершить работу.

   Основные недостатки:

   1. качество решения значительным образом зависит от размера и разнообразия начальной популяции;
   2. решения, полученные в результате нескольких экспериментов для одной и той же задачи, могут незначительно различаться;
   3. слабый учет специфики задачи составления расписания учебных занятий при организации ее решения.

   Преимущества:

   1. алгоритм работает с кодами, в которых представлен набор параметров, напрямую зависящих от аргументов целевой функции;
   2. в процессе поиска алгоритм использует несколько точек поискового пространства, а не переходит от точки к точке;
   3. в процессе работы алгоритм может не использовать никакой дополнительной информации о задаче, но, если такая имеется можно ускорить сходимость алгоритма;
   4. генетический алгоритм использует как вероятностные правила для порождения новых точек поиска, так и детерминированные для перехода от одних точек к другим;
   5. для задач высокой размерности скорость работы алгоритма можно «регулировать» размерами популяции.

6. Математическая постановка задачи

Расписание, по сути, представляет собой график проведения занятий, которые проводят преподаватели для конкретных групп в определенной аудитории в обозначенное время. Из этого можно сделать вывод, что расписание можно представить в функции

S (P,G,A,T,D,V),
где G Множество обучающихся групп;
A – Множество аудиторий;
D – Множество дисциплин;
P – Множество преподавателей;
T – Множество учебных пар (временных интервалов проведения занятий);
V – Рабочие учебные планы трехмерная матрица, определяющая для каждого занятия какие преподаватели его проводят, и какие группы на нем присутствуют.

Если упростить задачу и не рассматривать учебные планы и дисциплины, то расписание можно представить в виде декартова произведения

S=G×P×A×T→{0,1},
где G множество обучающихся групп;
A – множество аудиторий;
P – множество преподавателей;
T – множество учебных пар (временных интервалов проведения занятий).

Данное выражение расшифровывается следующим образом: если в определенное время Т преподаватель Р у группы G проводит занятие в аудитории А, то значение выражения равно 1, иначе 0.

Целевая функция Р является суммой штрафов за нарушения предпочтений при составлении расписания.

где NW – количество требований;
W – список штрафных коэффициентов длиной NW, соответствующий требованиям;
N – количество занятий в расписании (количество генов в хромосоме);
Z – список занятий длиной N;
z_i^r– список из булевых длиной NW значений, где каждому значению соответствует требование и штрафной коэффициент из списка W.

В большинстве учебных заведений основными ограничениями к расписанию являются:

1. отсутствие накладок в расписании преподавателя групп и аудиторий;
2. соответствие аудитории требованиям для проведения занятия;
3. ограничение количества занятий в неделю для преподавателя и группы.

Предлагается следующий вид кодирования хромосомы

Занятие - это сущность, которая определяет проведение одного занятия, определяя, преподавателей и группы, участвующие в нем, а также необходимые требования, которым должна удовлетворять аудитория, или перечень аудиторий.

Составляется список занятий Z в котором хранятся эти сущности, при этом, в данный список помещается столько экземпляров занятия, сколько должно быть проведено пар в течение 2х недель.

Тогда особь будет состоять из двух хромосом [10], представлена на рис 1.

1. номер аудитории из допустимого множества аудиторий для занятия;
2. время проведения занятия.

Рис 1 – Структура хромосомы

Позиция каждого гена в хромосоме однозначно соответствует занятию.

В рамках данной работы были проанализированы основные алгоритмы составления расписаний и выявлено, что все они не лишены недостатков. Полученные расписания в результате их работы обладают низкой эффективностью и далеки от оптимальных. Для устранения некоторых из недостатков предложено использовать модифицированный генетический алгоритм, который позволит получать субоптимальные решения с учетом особенностей учебных заведений различного профиля.

Список использованной литературы

1. Будиловский Дмитрий Михайлович Оптимизация решения задач теории расписаний на основе эволюционно-генетической модели распределения заданий // Системный анализ, управление и обработка информации (по отраслям) // Ростов-на-Дону 2007.
2. Секирин А. И. Программный комплекс для моделирования, анализа и оптимизации работы автоматизированных технологических комплексов механообработки // Научные труды Донецкого национального технического университета. Серия: "Вычислительная техника и автоматизация". Выпуск 90 - Донецк: ДонНТУ, 2005.
3. А. М. Дворянкин, В. С. Чалышев Обзор методов составления расписания вузов // Известия волгоградского государственного технического университета // Выпуск № 11 / том 9 / 2011.
4. Низамова Гузель Фанисовна Математическое и программное обеспечение составления расписания учебных занятий на основе агрегативных генетических алгоритмов: дис. канд. техн. наук: 05.13.11 Уфа, 2006 132 с.
5. Деканова, М. В. Конкретизация постановочных принципов проблемы многокритериальной оптимизации расписания занятий в университете // Вестник Полоцкого государственного университета. Серия C, Фундаментальные науки: научно-теоретический журнал. - 2014. - № 4. - C. 56-66.
6. Субботин С.А., Олейник Ан.А., Олейник Ал.А. Фрагмент рабочих материалов монографии Интеллектуальные Субботин С.А., Олейник Ан.А., Олейник Ал.А. интеллектуальные мультиагентные методы часть 3.
7. А. Б. Сидорин, Л. В. Ликучева, А. М. Дворянкин Методы автоматизации составления расписания занятий часть 2. Эвристические методы оптимизации // Известия волгоградского государственного технического университета // Выпуск № 7 / том 12 / 2009.
8. Низамова, Гузель Фанисовна Математическое и программное обеспечение составления расписания учебных занятий на основе агрегативных генетических алгоритмов // Уфа 2006.
9. С.В. Лаздынь, А. И. Секирин Оптимизация расписаний работы автоматизированных технологических комплексов механообработки с использованием генетических алгоритмов // Международный сборник научных трудов “Прогрессивные технологии и системы машиностроения”, выпуск 25. –Донецк: ДонНТУ.-2003. –С. 198-203.
10. Ю. С. Кабальнов, Л.И. Шехтман, Г.Ф. Низамова, Н.А. Земченкова // Композиционный генетический алгоритм составления расписания учебных занятий.