Упрощенная полиномиальная задача составления школьного расписания

Особенности составления школьных и университетских расписаний

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

При составлении расписаний часто используются модели ДО с бинарными переменными[2]. В настоящее время для решения задач составления учебных расписаний часто используются языки логического программирования в ограничениях (см. тему 10 настоящего пособия, а также статью Goltz и Matzke[3]).

Составление школьного расписания

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

Упрощенная полиномиальная задача составления школьного расписания

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

Математическая модель выглядит следующим образом:

(TTP1) Найти

при ограничениях

(9.7)

(9.8)

(9.9)

(9.10)

Здесь , если учитель проводит урок в классе в период и ‑ в противном случае.

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

Для учета невозможности использования учителей и классов в некоторые периоды времени вводятся бинарные матрицы и , причем (соответственно ), если учитель (класс ) доступен в период , в противном случае (соответственно ). Заменяя ограничения (9.8) и (9.9) в модели TTP1 на ограничения (9.11) и (9.12) ниже, получим модель (TTP2):

(TTP2) Найти

при ограничениях

(9.11)

(9.12)

De Werra [40] рассматривает дополнительные ограничения, учитывающие возможность назначенных заранее занятий:

, (9.13)

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

Задача TTP2 NP-полная, что доказано Even et al. (1976)[4], которые также показали, что эта задача полиномиальна для случая, когда классы доступны всегда и преподаватели доступны для двух периодов.