Scientific journal
Modern high technologies
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,940

METHODS AND ALGORITHMS OF FORMATION OF THE SEMESTRIAL SCHEDULE OF STUDIES AND ENTERING OF CHANGES INTO IT IN REAL TIME

Sidelev A.A. 1 Haritonov I.M. 2
1 Kamyshin Technical College
2 Kamyshin technological institute (branch of the State Volgograd technical University)
The present article is devoted to problems which the professional educational organizations when forming the semestrial lesson schedule face and to the methods allowing to automate process of compilation of the schedule the forthcoming week of a semester. The methods developed by the author allow not only to realize planning of the list of disciplines and the number of classes in them which are subject to placement in the lesson schedule next week of a semester, but also to create the schedule (to realize arrangement of occupations) taking into account restrictions and wishes, both from teachers, and from student’s groups. Besides the algorithm of implementation of operational changeovers in the existing lesson schedule, taking into account the hours which remained for a study of disciplines until the end of the current semester, and the current resource support is offered.
semestrial schedule
method of selection of disciplines
method of arrangement of disciplines
algorithm of implementation of operational changeovers
lesson schedule

Одной из составляющих уровня организации учебного процесса является расписание занятий.

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

В профессиональных образовательных организациях применяют расписания двух видов:

- недельное, построенное по принципу типовой недели, когда расписание одной или двух недель распространяется на весь семестр;

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

Опыт многолетней работы одного из авторов в должности заместителя директора по учебной работе в Камышинском техническом колледже (КТК) позволил выделить следующие особенности учебного процесса в профессиональных образовательных организациях, которые являются основными стимулами перехода учебных заведений к семестровому расписанию:

– неравномерное распределение учебной нагрузки в течение семестра, как для групп студентов, так и для преподавателей;

– занятия по одной и той же дисциплине могут вести разные преподаватели;

Таблица 1

Последовательность выдачи учебного материала преподавателями в рамках одной дисциплины

№ пары

Преподаватель 1

Преподаватель 2

55

Преподаватель 1

Преподаватель 2

56

Преподаватель 1

 

57

Преподаватель 1

 

58

Преподаватель 1

Преподаватель 2

59

Преподаватель 1

Преподаватель 2

60

Преподаватель 1

Преподаватель 2

61

Преподаватель 1

 

– практически полное отсутствие взаимозаменяемости преподавателей по причине того, что:

- ряд дисциплин из-за их специфики могут вести единичные преподаватели (штат преподавателей ограничен);

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

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

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

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

Процесс составления семестрового расписания осуществляется в два этапа:

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

2) расстановка запланированных занятий по «парам» в течение недели.

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

При этом ему необходимо учесть следующие ограничения, предъявляемые к семестровому расписанию:

1. Сумма блоков занятий (кортеж объектов – дисциплина, преподаватель/преподаватели, группа) GZ запланированных группе g на неделе w, должна соответствовать некоторому значению KG, определяемому требованиями образовательных стандартов (ФГОС) и календарному учебному графику

GZg,w = KGg,w.

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

PZp ≤ KPp.

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

Rp ≥ Sp.

Авторами работы предложен метод «отбора дисциплин», позволяющий получать список блоков занятий, которые необходимо включить в расписание, планируемое на следующую неделю семестра. Подробное описание разработанного метода опубликовано в работе [2].

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

Условия, предъявляемые к расписанию [7]:

1. Отсутствие «накладок» для аудиторий. Для каждой упорядоченной двойки элементов {аудитория – «пара»} существует либо единственный блок занятий из множества Z, что означает проведение занятия этого блока в этой аудитории в течение данной «пары», либо отсутствие блока занятия, указывающее на то, что аудитория свободна.

∀(ai, tj): ai∈A, tj∈T ($zk – единственный:((ai = ak)Λ(zk∈ t j Z ))V($zk: (ai = ak)Λ(zk∈ t j Z ))),,

где sid03.wmf – множество блоков занятий, проводимых во время «пары» tj.

2. Отсутствие «накладок» для преподавателей: существует либо единственный блок занятий, которые ведет данный преподаватель во время заданной «пары», либо этого блока не существует вообще.

∀(pi, tj): pi∈P, tj∈T ($zk – единственный:((pi = pk)Λ(zk∈ t j Z ))V($zk: (pi = pk)Λ(zk ∈ t j Z ))),

где sid06.wmf – множество блоков занятий, проводимых во время «пары» tj.

3. Отсутствие «накладок» для учебных групп, т.е. для каждой пары элементов: {группа – «пара»}, сумма компонент sid07.wmf вектора zi блоков из множества sid08.wmf не превышает единицы.

Во время конкретной «пары» группа находится на одном занятии, или проводится занятие только у одной из подгрупп, либо у обеих, либо занятий нет вообще.

∀(qn, tj): qn∈G, tj∈T e 1,i z  n j , iZ g ? Zt" />

где sid11.wmf – множество блоков занятий, в которых присутствует группа qn, а sid12.wmf – множество блоков занятий, которые проводятся во время «пары» tj.

Авторами разработан метод «расстановки дисциплин», который подробно изложен в работе [3]. Этот метод осуществляет формирование расписания в два этапа. На первом этапе происходит равномерное распределение блоков занятий, относящихся к одной и той же дисциплине определенной группы по дням недели. На этом этапе используется идея оценки свободы расположения [4] отдельного занятия в полученном расписании. Блоки занятий, которые должны быть проведены в определенные дни недели, либо при проведении которых задействуются одновременно несколько преподавателей и т.д., имеют гораздо меньшую свободу расположения, чем иные. Поэтому составление расписания должно начинаться с добавления в расписание блоков занятий, имеющих наименьшую свободу расположения.

Итогом выполнения работ на первом этапе становится заполненная таблица, структура которой показана в табл. 2. В ячейках таблицы будут находиться номера объектов (блоки занятий, которые должны быть проведены на планируемой неделе).

sidelev1.tif

Рис. 1. Распределение учебной нагрузки

Таблица 2

Таблица распределения блоков занятий

Понедельник

Вторник

Среда

Четверг

Пятница

Суббота

           

На втором этапе данного метода (расстановка объектов в течение дня) предлагается использовать возможности генетического алгоритма (ГА) [5], получившего свою известность в результате работ Джона Генри Холлонда и его последователей.

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

Таблица 3

Матрица совместимости объектов

Номер объекта

Список несовместимых объектов

   

Таблица 4

Шаблон матрицы расписания

Группа

Номер объекта

Пара 1

Пара 2

Пара 3

Пара 4

Пара 5

Группа 1

1

– 1

 

– 1

   

Группа 1

4

– 1

   

– 1

 

Группа 1

14

– 1

       

Группа 2

           

           

Группа n

           

Кроме этого, создается шаблон матрицы расписания, структура которой соответствует табл. 4.

Значения «– 1» устанавливаются в тех ячейках таблицы, где проведение занятий по той или иной дисциплине (объект) в рамках рассматриваемого дня недели невозможно.

На следующем шаге формируются n копий шаблонов матрицы расписания.

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

Для определения лучшего варианта расписания занятий используется значение целевой функции (в терминах генетического алгоритма – функция приспособленности).

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

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

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

В работе классический алгоритм ГА модифицирован для того, чтобы исключить попадание недопустимых вариантов расписания в состав множества, рассматриваемого на следующей итерации: включение нового варианта в состав множества вариантов следующего поколения происходит только после проверки на допустимость согласно матрице совместимости (табл. 3).

sidelev2.tif

Рис. 2. Особь и ее гены

sidelev3.tif

Рис. 3. Граф, формируемый алгоритмом поиска замен

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

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

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

Предусмотрен список преподавателей, замена которых невозможна: для преподавателей из этого списка повторные проверки не проводятся.

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