Фураева И.И.
Евразийский национальный университет им. Л.Н.Гумилева
методы АНАЛИЗа распределения
учебной нагрузки и формирования непротиворечивых начальных данных для задачи
составления расписания
Одной
из важнейших задач планирования учебного процесса является составление
расписания учебных занятий. Для решения этой задачи используются данные рабочих
учебных планов специальностей (РУП), распределения учебной нагрузки на кафедрах
и имеющегося аудиторного фонда, как специализированного, так и общего пользования.
Для повышения эффективности составления
расписания учебных занятий необходимо применение математических методов [1-2].
Распределение
учебной нагрузки на кафедре наибольшим образом влияет на формирование
расписания учебных занятий. Если учебная нагрузка кафедры равномерно распределена
по семестрам, то это существенно облегчает процесс составления расписания [3]. Нагрузка
может быть распределена таким образом, что задача составления расписания может не иметь решения. Анализ нагрузки можно
проводить как для каждого потока студентов, так и для общей нагрузки кафедры. Особенно
важен такой анализ для выпускающей кафедры, так как количество преподавателей,
которые ведут занятия для одних и тех же
студентов, на этих кафедрах достаточно велико.
Рассмотрим,
например, распределение нагрузки для потока студентов третьего курса, состоящих
из 3 групп казахского и 2 групп русского отделения. В семестре изучаются шесть
дисциплин с распределением часов 2+0+2+2 (лекции, практические занятия, лабораторные
и СРСП). Все эти дисциплины проводятся преподавателями выпускающей кафедры.
Каждую дисциплину разделим на компоненты: лекция для потока, СРСП для каждой из
3 групп и лабораторные занятия для каждой из 6 подгрупп. Для проведения анализа составим таблицу,
содержащую номер потока, номер компонента дисциплины, номер преподавателя и
информацию о подгруппах, занятых на соответствующих занятиях. На рис. 1 представлен фрагмент таблицы
распределения учебной нагрузки. Так первая строка соответствует лекционному
занятию, которое проводит преподаватель (1) для всех 6 подгрупп студентов,
седьмая строка соответствует СРСП в первой группе, 26 строка - лабораторному
занятию во второй подгруппе первой группы.
|
№
потока |
№
дисц |
№ ППС |
студенты |
|||||
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
2 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
6 |
3 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
… |
|
|
|
|
|
|
|
|
1 |
7 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
1 |
8 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
|
1 |
9 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
|
1 |
25 |
7 |
1 |
0 |
0 |
0 |
0 |
0 |
|
|
… |
|
|
|
|
|
|
|
|
1 |
26 |
7 |
0 |
1 |
0 |
0 |
0 |
0 |
|
1 |
27 |
7 |
0 |
0 |
1 |
0 |
0 |
0 |
|
1 |
28 |
7 |
0 |
0 |
0 |
1 |
0 |
0 |
Рис.1. Таблица распределения учебной нагрузки
В
рассматриваемом примере количество компонент равно 60 для первого потока и 41
для второго потока. Обозначим компоненты дисциплин 
. Введем в рассмотрение связки компонентов 
, состоящие из компонент дисциплин, занятия которых можно
проводить одновременно (на каждом из таких занятий нет одних и тех же студентов
и преподавателей). На рис. 2 приведен фрагмент списка связок компонентов
дисциплин. Связки могут содержать от одного до 6 компонентов (т.к. в
рассматриваемом примере 6 подгрупп студентов).
Расчет
показал, что общее количество связок в рассматриваемом примере составляет для
первого потока 4986 и для второго потока 1578. Для составления расписания
занятий без окон для студентов следует выбирать только те связки, в которых
задействованы все студенты. Таких связок 1350 и 786 для рассматриваемых потоков
студентов.
|
1 |
|
|
|
|
|
|
2 |
|
|
|
|
|
|
… |
|
|
|
|
|
|
8 |
21 |
22 |
|
|
|
|
9 |
10 |
14 |
|
|
|
|
… |
|
|
|
|
|
|
7 |
24 |
52 |
57 |
|
|
|
8 |
10 |
29 |
36 |
|
|
|
… |
|
|
|
|
|
Рис. 2 Связки компонентов дисциплин
Связку
компонентов дисциплин можно представить также в виде матрицы размером k*n, причем 
, где 
, если в i-тую связку
входит j- тый компонент и 
в противном случае.
Такой подход позволяет привести задачу анализа распределения учебной нагрузки к
задаче булева линейного программирования.
Обозначим
количество часов
недельной нагрузки по каждой компоненте, 
количество связок
каждого вида, которое необходимо использовать для выполнения требований
РУП. Тогда в качестве целевой функции
можно использовать требование минимума общего количества связок, а в качестве
ограничений – выполнение недельной нагрузки по всем компонентам:
Таким
образом, мы получили задачу булева линейного программирования с n ограничениями в виде
равенств. Если эта задача имеет решение, то нагрузка распределена правильно,
если решения нет, то составить расписание занятий без окон для студентов невозможно.
Значение целевой функции показывает общую длину расписания в неделю. Отсутствие
решений для полных связок приводит к необходимости решать задачу в общей постановке
для всех связок. Задача в общей постановке имеет решение, т.к. для каждой компоненты
можно выбрать отдельное занятие. Длина такого расписания составит n часов. Оптимальное значение F будет тем больше, чем хуже распределена нагрузка на кафедре, что приведет
не только к появлению окон в расписании занятий, но и к увеличению общей
продолжительности расписания.
Количество неизвестных в рассматриваемой задаче
достаточно велико даже для одного потока. Если же рассматривать не один, а два
потока, то получим в данном примере 75672 переменных, вместо 1350.
Исследуем
способы уменьшения количества переменных. Рассмотрим вместо связок дисциплин
связки преподавателей, которые могут одновременно проводить занятия на данном
потоке студентов, причем соответственно каждой подгруппе. При таком подходе
получим 45 различных связок. На рис.3 представлен фрагмент связок
преподавателей. В первой строке
представлена лекция на всем потоке, которую проводит ППС 3; во второй строке
указано, что СРСП в первой группе проводит 1 ППС, по второй группе 2 ППС, в
третьей группе 3 ППС; из пятой строки видно, что в 1 группе проводят
лабораторную работу 7 и 8 ППС, во второй группе СРСП 1 ППС, в третьей группе
СРСП 2 ППС. Как видно из рисунка при таком подходе не указаны компоненты дисциплин.
|
3 |
3 |
3 |
3 |
3 |
3 |
|
1 |
1 |
2 |
2 |
3 |
3 |
|
1 |
1 |
3 |
3 |
2 |
2 |
|
… |
|
|
|
|
|
|
2 |
2 |
1 |
1 |
8 |
7 |
|
7 |
8 |
1 |
1 |
2 |
2 |
|
… |
|
|
|
|
|
|
3 |
3 |
8 |
7 |
2 |
2 |
|
7 |
8 |
3 |
3 |
2 |
2 |
|
8 |
7 |
3 |
3 |
2 |
2 |
Рис.3
Связки преподавателей
Представим
связку преподавателей в виде матрицы, содержащей нули и единицы. При этом
количество строк матрицы не изменяется, а количество столбцов равно произведению
количества подгрупп на количество ППС, занятых на проведении занятий выбранного
потока. Обозначим 
связки ППС, где p- общее количество таких связок. 
. Пусть xi
– количество i-той
связки, необходимой для выполнения недельной нагрузки. Тогда целевая функция и
ограничения имеют вид:
Количество
неизвестных равно количеству связок, количество ограничение равно произведению
количества подгрупп на количество ППС. Через tj обозначено количество часов недельной нагрузки по
каждому ППС для каждой подгруппы.
Рассмотрение
связок ППС привело к уменьшению количества неизвестных в рассматриваемом примере в 30 раз, что
позволило использовать инструмент MS
Excel «Поиск
решения», который был недоступен для 1350 неизвестных.
Анализ
распределения нагрузки является важной составляющей проверки исходных данных
для задачи составления расписания занятий. Использование связок ППС позволяет уменьшить
количество переменных и проводить такой анализ, не прибегая к применению
сложных программ.
Литература:
1.
Абдыманапов
С.А, Фураева И.И. Рабочий учебный план в условиях кредитной системы обучения.
// Вестник ЕНУ им. Л.Н. Гумилева №
1(47), 2006, с. 6-12
2.
Фураева
И.И. Об одной математической модели формирования расписания учебных
занятий в вузе для кредитной системы
обучения.// Вестник ПГУ, № 1, 2007, с.
147-159
3.
Фураева
И.И. Вопросы моделирования и автоматизации управления учебным процессом вуза.
// Вестник ПГУ, 2007, № 1, с. 135-146