С каждой учебной группой k_r потока r в течение недели, согласно учебному плану, проводится W_kr занятий, из которых S_r лекционных и Q_kr практических. Обозначим:

s_r – номер дисциплины в списке лекционных занятий для потока r, s_r = 1 ,…,S_r;

q_kr – номер дисциплины в списке практических занятий для группы k_r, q_kr = 1 ,…, Q_kr.

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

ПРЕПОДАВАТЕЛИ

П усть p – номер (имя) преподавателя, p = 1 ,…, P. Введем в рассмотрение булевы значения и :

1, если на потоке r лекцию s_r читает преподаватель p;

0 – в противном случае;

1, если в группе k_r практическое занятие q_kr проводит преподаватель p;

0 – в противном случае;

=

Учебная нагрузка преподавателей планируется до составления расписания занятий, вследствие чего на данном этапе величины и можно считать заданными. Для каждого преподавателя p, p = 1 ,…,P, задана также его аудиторная нагрузка - N_p часов в неделю.

АУДИТОРНЫЙ ФОНД

Занятия каждого потока могут проводиться только в определенных аудиториях (например, практические занятия по информатике могут проводится только в дисплейных классах). Пусть:

{A_1r} – множество аудиторий для лекций на потоке r;

{A_2r} – множество аудиторий для практических занятий на потоке r;

A_1r – число элементов множества {A_1r};

A_2r – число элементов множества {A_2r};

A _1r + A_2r – число аудиторий объединения множеств {A_1r}∩{A_2r}.

Аудиторный фонд определяется до начала составления расписания, поэтому множества можно считать заданными.

2.1.2. Переменные

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

Введем следующие искомые булевы переменные:

1, если на потоке r в день t на паре j читается лекция s_r;

0 – в противном случае;

1, если на потоке r в день t на паре j у группы k_r проводится практическое занятие q_kr;

0 – в противном случае;

=

=

В случае составления расписания для групп вечерней формы обучения J=2. Обобщение модели на все формы обучения см. [1], стр. 669.

2.1.3. Ограничения

Для каждой группы k_r должны выполняться все виды аудиторной работы в течение недели:

(1)

В любой день t на каждой паре j для каждой группы k_r может проводиться не более одного занятия:

(2)

Каждые лекция s_r и практическое занятие q_kr соответственно для всех потоков r и всех групп k_r могут проводиться не более одного раза в любой день t:

(3)

Если переменные и увязывают все виды занятий с временем их проведения, то произведения и связывают время проведения с именем преподавателя.

В каждый день t и в каждой паре j преподаватель p может вести не более одного занятия по одной дисциплине на одном потоке или в одной группе:

(4)

Каждый преподаватель p в течение недели должен провести аудиторные занятия:

(5)

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

(6)

(7)

Кроме того, для всех совокупностей пересекающихся множеств {A_1r} и {A_2r} должны выполняться условия:

(8)

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

2.1.4. Целевая функция

Чтобы полноценно вести научную, учебно-методическую работу, готовиться к занятиям, преподаватель вуза должен иметь свободное время. Это условие недостаточное, но необходимое. Очевидно, что свободным временем он должен располагать не в “рваном” режиме, каковым, например, являются “окна” между занятиями со студентами, а по возможности в полностью свободные рабочие дни. Этому эквивалентна максимизация аудиторной нагрузки преподавателей в те дни, когда они ее имеют (см. (5)). Однако при этом претензии на свободное время у преподавателей неравны, так как у них разный творческий потенциал. Поэтому необходимо ввести весовые коэффициенты, посредством которых должен учитываться соответствующий статус преподавателя – его ученые степени и звание, занимаемая должность, научно-общественная активность и т.п. В некоторых случаях можно на основании экспертных оценок использовать индивидуальные весовые коэффициенты, учитывающие другие факторы.

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

Рассмотрим выражение для величины аудиторной нагрузки в день t преподавателя p:

(9)

Вводятся ограничения вида:

(10)

где M – произвольное положительное достаточно большое число; - искомая булева переменная.

Из (10) вытекает, что если , то = 1, и если , то = 0.

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

(11)

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

2.2. МЕТОДЫ РЕШЕНИЯ ПОСТАВЛЕННОЙ ЗАДАЧИ

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

В [3] – [8] описаны методы упорядоченной индексации и модифицированных пометок, основанные на лагранжевой декомпозиции исходной модели на ряд однострочных задач, решаемых соответственно методами упорядочивающей индексации или модифицированных пометок. К сожалению количество операций каждого из методов не допускает полиномиальной оценки; кроме того, размерность таблицы наборов (промежуточных значений) методов резко возрастает при увеличении размерности решаемой задачи, что недопустимо в нашем случае. Возможно, изменение алгоритма декомпозиции под конкретную математическую модель позволит уменьшить размерность таблиц, но пока такого алгоритма не существует.

В связи с этим в качестве методов решения были выбраны описанные в [2] модификации симплекс-метода для случая задачи целочисленного линейного программирования. В общем случае количество операций симплекс-метода не допускает полиномиальной оценки (был даже показан класс задач, для которых количество операций составляет O(eⁿ)), но для случая нашей задачи среднее число операций допускает полиномиальную оценку: O(n³m^1/(n-1)) (n – количество переменных; m – количество ограничений).

2.2.1. ПОЛНОСТЬЮ ЦЕЛОЧИСЛЕННЫЙ АЛГОРИТМ

Этот алгоритм назван полностью целочисленным, потому что если исходная таблица состоит из целочисленных элементов, то все таблицы, получающиеся в процессе работы алгоритма, содержат только целочисленные элементы. Подобно двойственному симплекс-методу, алгоритм начинает работать с двойственно допустимой таблицы. Если a_i0 (i = 1 ,…, n+m; a_i0 – коэффициенты целевой функции) – неотрицательные целые, то задача решена. Если для какой-нибудь строки a_i0<0, то составляется новое уравнение и записывается внизу таблицы. После этого используется двойственный симплекс-метод. Все элементы дополнительной строки должны быть целыми числами, а ведущий элемент равен –1. Введенная таким образом ведущая строка сохранит таблицу целочисленной.

Пусть задана задача целочисленного линейного программирования:

максимизировать

при условиях

(12)

Условия (12) могут быть записаны как

(13)

Предположим, что для t=0 (т.е. для исходной таблицы) все a_ij – целые и столбцы (j = 1 ,…, n) – лексикографически положительны. Тогда все столбцы на протяжении вычислений остаются лексикографически положительными.

Прежде чем изложить способ получения дополнительного ограничения из производящей строки, введем новое представление чисел. Пусть [x] обозначает наибольшее целое число, не превосходящее x. Для любого числа y (положительного или отрицательного) и положительного можно записать:

(14)

где (r_y – неотрицательный остаток от деления нацело y на ). В частности, . Поэтому если , то и r = 1. Если , то и r = 0.

Вводимое дополнительное неравенство должно выполняться при любом целом решении задачи (12). Рассмотрим некоторое уравнение в t – таблице (опуская индекс строки) с a₀<0:

(15)

где x – соответствующая компонента вектора , а - текущие небазисные переменные. Можно выразить x, a_{0 и} a_j, используя введенное выше представление (14):

(16)

(17)