ПРИЛОЖЕНИЕ РАСКРАСКИ ВЕРШИН ГРАФА К ЗАДАЧЕ СОСТАВЛЕНЯ РАСПИСАНИЯ

Мария Деканова

(Новополоцк, Белоруссия)

ПРИЛОЖЕНИЕ РАСКРАСКИ ВЕРШИН ГРАФА К ЗАДАЧЕ

СОСТАВЛЕНЯ РАСПИСАНИЯ

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

1. Локально-эволюционный метод позволяет находить решение в сильно ограниченном пространстве поиска. Дополнительное сжатие пространства поиска становится возможным за счет использования эвристик особого типа – рекурсивных [2, с. 28].

Достоинствами метода являются:

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

2. Гибкость, которая обеспечивается содействием различных стратегий.

3. Возможность видоизменять участвующие в алгоритме эвристические стратегии.

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

2. Многоагентный подход состоит в разбиении исходной задачи на несколько мелких задач. Для решения каждой мелкой задачи выделяется агент – самостоятельный объект системы, обладающий свойством коммуникабельности и наделённый собственной системой принятия решений [3, с. 56-78].

Идея применения агентного подхода к задаче составления расписания состоит в том, чтобы заменить агентами каждого пользователя расписания [1, с. 21].

Достоинства агентного подхода:

1. Сильная индивидуальность предпочтений (каждый пользователь имеет возможность высказать свои предпочтения).

2. Динамическое изменение предпочтений.

3. Существование частичного решения.

Недостатки агентного подхода:

1. Распределенность (агент – это самостоятельный программный модуль, все агенты исполняются на разных компьютерах).

2. Резко (экспоненциально) увеличиваются временные затраты на поиск лучшего (приемлемого) решения с ростом размерности решаемой задачи.

3. Большой риск (отсутствует гарантия получения приемлемого решения задачи построения расписания занятий).

3. Интеллектуальный метод базируется на использовании различных эвристик, основанных на интуитивных соображениях, не подкрепленных математическим обоснованием. Это позволяет ускорить поиск расписания, но не гарантирует нахождения точного решения [2, с 88-92]. В этом случае возникает проблема оценки близости найденного локального экстремума к глобальному экстремуму. При составлении расписания занятий в системах массового обучения предлагается использовать математический аппарат нечеткой логики для перехода от «жестких» ограничений к более «мягким» требованиям. Это позволяет упростить формализацию требований, предъявляемых к расписанию, но рассмотрение наиболее важных требований в качестве «мягких» может привести к «плохому» расписанию (появлению «окон», накладок и т.д.).

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

Генетический алгоритм, комбинируя переборные и эвристические методы, позволяет находить приближенное решение, точность которого возрастает при увеличении времени расчета [1, с. 6-13].

Преимущества генетического алгоритма:

1. Возможность получения близких к оптимальному решений за небольшое время.

2. Результатом поиска является не одно решение, а сразу несколько.

3. На любой итерации есть возможность получения наилучшего на данный момент решения, что важно для задач высокой размерности.

Недостатки:

1. Качество решения зависит от начальной размерности данных.

2. Недостаточное разнообразие данных может привести к преждевременному окончанию работы алгоритма и, как следствие, к получению некорректного расписания.

5. Метод раскраски вершин графа

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

В процессе решения задачи построения расписания необходимо назначить каждое занятие на конкретный промежуток времени рабочего дня недели. Обозначим через W множество всех таких известных интервалов времени в рассматриваемом при составлении расписания плановом периоде. При построении расписания учебных занятий необходимо выполнить следующие требования (условия).

1. Если два занятия проводятся с одной и той же группой студентов, то они должны быть назначены на различные интервалы времени.

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

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

4. Пусть V_k обозначает множество всех занятий, которые должны быть проведены в аудиториях типа k. Тогда мощность подмножества занятий множества V_k, которые могут быть назначены на один и тот же интервал времени из множества W, не должна превышать общего числа имеющихся в ВУЗе аудиторий типа k.

5. Необходимо предусмотреть возможность запрещать назначение пар для конкретной группы учащихся на тот или иной интервал времени из множества W.

6. Необходимо предусмотреть возможность запрещать назначение пар для преподавателя на тот или иной интервал времени (методический день).

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

8. Необходимо обеспечить возможность проводить какие-либо занятия в разные дни (например, три занятия по высшей математике не должны проводиться в один день с одной группой учащихся).

9. Для студентов в построенном расписании не должно быть так называемых форточек.

Процесс построения расписания сводится к раскраске вершин V графа G=(V, E) с множеством ребер E и дополнительными ограничениями на множества цветов.

Функцию ф называют раскраской (вершин) графа G = (V, E), если для каждой вершины v_i Î V она определяет натуральное число (называемое цветом) ф(v_i) Î N так, что из включения [v_i, v_j] Î Е следует соотношение ф(v_i) ≠ ф(v_j). Здесь N обозначает подмножество множества натуральных чисел.

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

Предполагается, что каждая нефиктивная вершина графа G = (V, E) соответствует определенному занятию, которое проводится конкретным преподавателем с конкретной группой учащихся в конкретной аудитории (если аудитория задана заранее) или в аудитории конкретного типа (если аудитория заранее не задана). Раскраска ф: V → N интерпретируется следующим образом: если нефиктивная вершина v_i Î V окрашена в цвет ф(v_i) Î N = {1, 2, …, n}, то занятие, определенное вершиной v_i Î V, должно быть проведено в ф(v_i)-й по порядку следования интервал времени из упорядоченного множества W интервалов. Граф G = (V, E) может содержать фиктивные вершины, включение которых во множество V определяется правилами представления условия 5 и 6 в терминах раскраски графа.

Ребра множества Е графа G = (V, E) используются для определения условий и ограничений 1–9. В частности, ребро [v_i, v_j] Î Е, инцидентное нефиктивным вершинам v_i Î V и v_j Î V, может обозначать, что занятия, соответствующие данным вершинам, проводятся у одной и той же группы (условие 1), у одного и того же преподавателя (условие 2), в одной и той же аудитории (условие 3).

Следующее ограничение, которое необходимо учитывать при составлении расписания, связано с количеством имеющихся в ВУЗе аудиторий каждого типа (условие 4). Это ограничение учитывается путем введения дополнительного условия на использование одного и того же цвета для ограниченного числа вершин из заданного подмножества множества V. Конкретный цвет вершин означает, что занятия, представленные вершинами одного цвета, проводятся в один и тот же интервал времени из множества W. Следовательно, учет при построении раскраски ф: V → N заданной границы на число вершин одного цвета позволяет ограничить количество аудиторий соответствующего типа, которые могут быть использованы в одном и том же интервале времени из множества W.

При составлении расписания следует учитывать необходимость или пожелания преподавателей или группы не назначать для них занятия на какие-то конкретные промежутки времени из множества W (или не проводить занятия в каких-то аудиториях в конкретные промежутки времени). Для задания такого требования или пожелания требуется сопоставить преподавателю (группе или аудиториям определенного типа) конкретные цвета (номера интервалов времени из множества W), запрещенные для них по тем или иным причинам (условия 5 и 6).

Условие 7 учитывается в процессе построения допустимой раскраски ф: V → N следующим образом. При окрашивании подмножества вершин, связанных условием 7, цвет необходимо выбирать только для основной вершины из этого подмножества. При этом неосновным вершинам подмножества цвета назначаются исходя из их расположения относительно окрашенной основной вершины.

Условия 8 и 9 отражаются непосредственно в целевой функции, которая используется при построении оптимальной допустимой раскраски графа G, и учитываются как тенденция к запрещению цветов, нарушающих эти условия уже в самом алгоритме построения допустимой раскраски.

Алгоритм раскраски вершин графа G:

1. Назначаются последовательно цвета из множества N всем вершинам, которые необходимо раскрасить.

2. Вычисляются оценки качества полученного назначения цветов (назначаются штрафы)

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

4. Разрешение конфликтов.

6. Сравнение методов составления расписания учебных занятий

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

Все рассмотренные методы вообще не учитывают такие ограничения как:

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

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

Выводы

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

Основной проблемой разработки методик автоматизации составления расписания занятий в ВУЗе является отсутствие однозначных решений следующих вопросов:

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

2. Проблема многокритериальности чаще всего рассматривается только на уровне математической постановки задачи, но не учитывает совмещения задач оптимизации показателей качества автоматизации процесса составления расписания и критериев оптимальности формируемой сетки расписания.

Литература:

1. S.V. Baltak, Yu.N. Sotskov. Generation coursetimetabling on the basis of vertex graphcoloring. – 69 p.

2. Haupt, R.L. Practical Genetic Algorithms / R.L. Haupt, S.E. Haupt. – NJ: John Wiley & Sons. – 2004. – 261 р.

3. Leighton, F.T. A graph coloring algorithm for large scheduling problems // Journal of Research of the National Bureau of Standards. – 1979. – P. 489–506.

Научный руководитель: к. ф.-м. наук, доцент Голубева Оксана Валерьевна