Расписание учебных занятий для учебных заведений (школ, колледжей, вузов и т.п.) относится к классу задач целочисленного программирования с булевыми переменными. Французские специалисты по методам исследования операций А.Кофман и А.Анри-Лабордер называют ее задачей “планирования загрузки преподавательского состава и обеспечение студентов аудиториями”.

Формально задачу составления учебного расписания можно поставить следующим образом:

Заданы множество преподавателей T, множество “учебных дисциплин” (учебный план) D, множество аудиторий H и множество рабочих часов (часовая сетка) S. Дано: " t Î T $ A(t) Í S (допустимые часы работы преподавателя), " d Î D $ A(d) Í S (допустимые часы для прохождения учебной дисциплины), " (t, d) Î TxD - число R(t, d) Î , называемое “требуемой нагрузкой”, и " (t, d) Î TxD $ A(h) Í H (допустимое множество аудиторий).

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

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

Решение задачи составления расписания сводится к следующей схеме:

Множество преподавателей T и множество учебных дисциплин D образуют соответственно две доли графа.

Матрица весов формируется на основе начальных условий ( а именно, множеств D и S).

Требуется найти каркас, удовлетворяющий целевой функции , где , – вес ребра, соединяющего вершины i и j, , где m – число ребер в исходном подграфе, и ограничениям Аmax = (A₁, …, A_i, …, A_n), Аmin = (a₁, …, a_i, …, a_n), где Аmax, Amin — векторы допустимых степеней (т.н. векторы топологии).

Алгоритм сводится к следующим построениям.

1. После упорядочения списка ребер исходного графа по возрастанию весов по первым n-1 ребрам вычисляется вектор начальных степеней и номер вершины с максимальным дефицитом степени , где S — вектор закрепленных степеней. Просматривая по возрастанию нумерации список ребер, находим первое ребро, инцидентное вершине с максимальным значением дефицита. Ребро помечается.
2. Выполняя n-3 итерации, аналогичных п.1, находим следующие ребра, инцидентные изолированным вершинам наращиваемого начального подграфа.
3. К полученным ребрам добавляется ребро из числа непомеченных, которое помечается. Из помеченных ребер формируется начальных подграф путем упорядочения его множества ребер E⁰ по возрастанию весов. Непомеченные ребра упорядочиваются также по возрастанию весов и становятся множеством E\ E⁰. Пометки с множества ребер E⁰ снимаются. Дальнейшее решение задачи выполняется по известной схеме замещений.

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

Описанный алгоритм был использован при разработке автоматизированной системы составления расписания учебных для лицея № 1501 при МГТУ “Станкин” и школы № 1201.

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

Литература.

1. Горшков А.Ф., Соломенцев Ю.М. //ДАН, 1994. Т.337, № 2, с.151-153.
2. Горшков А.Ф. //Сибирский математический журнал, 1985. Т.26, № 1, с.44-48.

Сервер поддерживается фирмой НПП "БИТ про" Лучшие программы для образовательного процесса