METHOD OF CHOOSING OF DISCIPLINES, USED DURING THE FORMATION OF TERM TIMETABLE
Authors:
1.
Kamyshin Technical College
Type:
Article
Pages:
from 69
to 79
Status:
Published
Received:
05.01.2017
Accepted:
25.01.2017
Published:
25.01.2017
Subject area:
VAC 05.12.2013 Системы, сети и устройства телекоммуникаций
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 519.8
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 519.8
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
Language:
Russian
Keywords:
fixed principle of education process scheduling, term timetable, algorithm of timetable formation, list of disciplines
Abstract (English):
The necessity for transition of a number of educational institutions to the use of term timetable has been explained. The stages of formation of such a class timetable are defined. They are: preliminary (a list of disciplines and a number of class hours a week are determined) and basic (class scheduling during a week is carried out). The problems the dispatcher of educational institution faces weekly when scheduling, are stated. The method allowing at the first stage solution of the problems of choosing the disciplines is described in detail. This method has been realized as a part of the information system "Management of the college", developed and implemented in the educational process at Kamyshin technical college (Volgograd region), that made it possible both to reduce the time spent on scheduling and improve its quality.
The necessity for transition of a number of educational institutions to the use of term timetable has been explained. The stages of formation of such a class timetable are defined. They are: preliminary (a list of disciplines and a number of class hours a week are determined) and basic (class scheduling during a week is carried out). The problems the dispatcher of educational institution faces weekly when scheduling, are stated. The method allowing at the first stage solution of the problems of choosing the disciplines is described in detail. This method has been realized as a part of the information system "Management of the college", developed and implemented in the educational process at Kamyshin technical college (Volgograd region), that made it possible both to reduce the time spent on scheduling and improve its quality.
Keywords:
fixed principle of education process scheduling, term timetable, algorithm of timetable formation, list of disciplines
fixed principle of education process scheduling, term timetable, algorithm of timetable formation, list of disciplines
Введение В образовательных учреждениях профессионального образования применяются расписания занятий двух видов [1]: - недельное, построенное по принципу типовой недели, когда расписание одной или двух недель распространяется на весь семестр; - семестровое, построенное по принципу планирования каждой недели семестра, когда расписания для всех или большинства недель различаются между собой. В 2010 г. в систему среднего профессионального образования на смену государственным образовательным стандартам пришли федеральные государственные образовательные стандарты. Они предусматривают концентрированный принцип организации учебного процесса - дисциплины могут преподаваться в сжатые сроки, не растягиваясь на весь семестр. При этом не требуется соблюдать правило кратности объема часов на освоение программы учебной дисциплины неделям в учебном семестре. Таким образом, учебные заведения, не соблюдающие в учебных планах кратность объема часов либо применяющие концентрированный принцип организации учебного процесса, в первую очередь вынуждены переходить на использование семестрового расписания. Процесс составления семестрового расписания занятий можно представить в виде двух основных этапов: - предварительный - определяются перечень дисциплин и количество учебных часов по дисциплине на той или иной неделе; - основной - осуществляется распределение занятий в течение недели. В связи с неравномерным распределением учебной нагрузки для групп в течение семестра диспетчер образовательного учреждения на первом этапе формирования расписания учебных занятий на неделю вынужден осуществлять выравнивание учебной нагрузки до значений, установленных образовательным стандартом. При этом диспетчеру необходимо для каждого из преподавателей оценить возможность проведения занятий, запланированных на текущую неделю, и, в случае отсутствия такой возможности, принять решение об изменении часовой нагрузки по дисциплинам в группах. Кроме этого, диспетчер должен заранее предпринять действия по уменьшению нагрузки преподавателей в рамках тех недель, где планируемое количество занятий по дисциплинам окажется больше, чем количество занятий, которые преподаватели смогут провести. Существует большое количество работ, посвященных изучению проблемы основного этапа. В частности, в работах [2-7] рассматриваются возможности применения генетических алгоритмов для расстановки дисциплин в течение недели таким образом, чтобы выполнялся ряд требований (обеспечение занятий необходимыми аудиториями, отсутствие накладок у преподавателей и групп и т. д.). В то же время метод отбора дисциплин на предварительном этапе процесса составления семестрового расписания занятий остается вне поля зрения исследователей, занимающихся проблемой формирования расписания в образовательных учреждениях. По всей видимости, именно отсутствие подобного метода приводит к тому, что широко известные информационные системы, предназначенные для оказания помощи при формировании расписания учебных занятий, оставляют решение этой задачи диспетчеру образовательного учреждения. Время на поиск этого решения является существенно ограниченным, поэтому разработка метода отбора дисциплин и количества занятий по ним на той или иной неделе семестра, а также внедрение его в программное обеспечение в настоящее время достаточно актуальны. Метод отбора дисциплин Основная идея метода, предлагаемого нами, состоит в том, чтобы для каждой учебной группы выровнять учебную нагрузку в течение семестра и по полученной информации о распределении учебной нагрузки для групп распределить учебную нагрузку для каждого преподавателя. После этого необходимо оценить возможности каждого преподавателя провести запланированное количество часов на текущей неделе (для которой составляется расписание занятий). В случае превышения запланированного количества учебных часов над нормативом предельной нагрузки преподавателя следует внести изменения в учебную нагрузку той или иной группы путем замены дисциплин, читаемых преподавателем, или уменьшения количества учебных часов на текущей неделе. Часы, освободившиеся на текущей неделе, заполняются за счет дисциплин, читаемых другими преподавателями. Метод реализован в форме последовательности этапов, на каждом из которых прогнозируются последствия принимаемых решений с тем, чтобы не допускать перегрузок преподавателей в рамках учебных недель, следующих за рассматриваемой. Такой подход позволяет упорядочить последовательность планирования нагрузки для преподавателей на текущей неделе. В первую очередь рассматривается возможность увеличения количества занятий по дисциплинам для тех преподавателей, у которых суммарное оставшееся количество занятий больше, чем они могут провести за оставшееся время. Во вторую очередь рассматривается возможность увеличения количества занятий по дисциплинам для тех преподавателей, у которых разница между количеством запланированных часов и количеством занятий, которые они могут провести, - наименьшая. Если на определенном временном интервале суммарное планируемое количество занятий какого-либо преподавателя окажется больше, чем количество занятий, которые он сможет провести, то увеличение его нагрузки на текущей неделе (если такая возможность имеется) будет осуществляться за счет уменьшения на текущей неделе учебной нагрузки других преподавателей. Опишем этапы, реализующие предложенный метод. Этап 1. Определяем перечень дисциплин, из которых будет составлен итоговый список, используемый при формировании расписания на неделю. Результатом этого этапа является создание табл. 1. В эту таблицу записываем данные на начало недели, для которой формируется расписание занятий: - ns - число, определяющее номер недели семестра, с которой начинается чтение дисциплины; - nf - число, определяющее номер недели семестра, на которой заканчивается выдача часов по дисциплине; на которой заканчивается чтение дисциплины; - he - число, определяющее количество учебных часов по дисциплине, включенных в расписание; - hs - число, определяющее количество оставшихся учебных часов по дисциплине; - hm - число, определяющее среднее количество занятий, необходимое еженедельно для равномерного проведения занятий по дисциплине. Это число определяется по формуле ; - hd - число, определяющее разницу между оставшимся количеством занятий по дисциплине и количеством занятий, которые будут проведены, если еженедельно вносить в расписание количество занятий, определяемое значением параметра hm. Это число определяется по формуле Таблица 1 Таблица дисциплин (для всех групп), преподавание которых не завершено Дисциплина Параметр ns nf he hs hm hd Этап 2. На основании данных табл. 1 осуществляем формирование таблицы для каждой учебной группы. Ниже представлен пример, в котором занятия рассматриваются в виде сдвоенных учебных часов - «пар». Необходимо обратить внимание на то, что номера недель в таблице могут отличаться от номеров недель семестра. В случае формирования расписания занятий для первой недели семестра эти номера совпадают. Но при формировании расписания на вторую и последующие недели номер последней недели в табл. 2 будет последовательно уменьшаться на 1, начиная с 9. При этом номер первой недели всегда будет оставаться равным 1. Таблица 2 Распределение учебной нагрузки группы по неделям семестра Дисциплина Параметр ns nf hs 1 2 3 4 5 6 7 8 9 10 Предмет 1 1 6 12 2 2 2 2 2 2 Предмет 2 1 6 16 3 3 3 3 3 1 Предмет 3 1 10 30 3 3 3 3 3 3 3 3 3 3 Предмет 4 1 10 36 4 4 4 4 4 4 4 4 4 0 Практика 3 1 2 24 12 12 Предмет 5 2 5 8 2 2 2 2 Практика 1 6 7 18 12 6 Практика 2 8 10 36 12 12 12 Итого 24 26 14 14 14 22 13 19 19 15 Этап 3. Осуществляем выравнивание недельной учебной нагрузки каждой группы до значений, установленных стандартом обучения (для среднего профессионального образования для групп очной формы обучения - 36 учебных часов (18 занятий), для групп очно-заочной формы - 18 учебных часов (9 занятий) в неделю). Выполнение данного этапа базируется на следующих правилах. 1. Выравнивание недельной учебной нагрузки осуществляем последовательно с первой недели семестра до последней недели включительно (слева - направо). 2. Если в группе сумма планируемых занятий на неделе оказывается больше, чем предусмотрено стандартом, то последовательно, переходя от одной дисциплины к другой, уменьшаем количество занятий путем их переноса на другие недели. При этом выбор дисциплин осуществляем в порядке увеличения количества занятий, предусмотренных на неделю. 3. Перемещение занятия по практике не допускается. 4. Первоначально увеличиваем количество занятий по дисциплине в рамках тех недель, где их количество меньше среднего. 5. Перенос занятий на более раннюю неделю возможен только в том случае, если общее количество занятий на догружаемой неделе меньше количества, определяемого стандартом. 6. Если количество занятий на рассматриваемой неделе по дисциплинам одинаково, то в случае переноса занятий на более раннюю неделю приоритет отдается той дисциплине, проведение занятий по которой заканчивается раньше, и при переносе на более позднюю неделю - той, проведение занятий по которой заканчивается раньше. При одинаковых характеристиках дисциплина выбирается случайным образом. 7. Если на рассматриваемой неделе количество занятий по дисциплине стало равным минимально допустимому значению и она ранее уже читалась, то эту дисциплину оставляем в списке дисциплин, планируемых для преподавания на рассматриваемой неделе. 8. Перенос занятий по дисциплине с рассматриваемой недели на иную, где число занятий стало равным максимально допустимому значению, не осуществляем. 9. Пункты 7 и 8 нарушаем в том случае, если произведенные действия не позволили достичь суммарной недельной нагрузки, установленной стандартом. Результат выравнивания нагрузки для примера, представленного в табл. 2, приведен в табл. 3. Таблица 3 Распределение учебной нагрузки группы для выполнения требований стандарта Дисциплина Параметр ns nf hs 1 2 3 4 5 6 7 8 9 10 Предмет 1 1 6 12 1 1 3 3 3 1 Предмет 2 1 6 16 1 1 4 5 4 1 Предмет 3 1 10 30 1 1 4 4 4 2 6 3 3 2 Предмет 4 1 10 36 3 2 4 4 5 2 6 3 3 4 Практика 3 1 2 24 12 12 Предмет 5 2 5 8 1 3 2 2 Практика 1 6 7 18 12 6 Практика 2 8 10 36 12 12 12 Итого 18 18 18 18 18 18 18 18 18 18 Этап 4. Для каждой группы создаем таблицу «Дисциплины, планируемые для группы», структура которой соответствует табл. 4. В нее помещаются дисциплины и количество занятий, которые планируются для группы на первой неделе (данные выбираем из таблицы «Распределение учебной нагрузки группы»). Таблица 4 Дисциплины, планируемые для группы Дисциплина Число занятий Этап 5. На основании таблиц распределения учебной нагрузки для групп и информации о последовательности проведения занятий преподавателями (пример см. в табл. 5) для каждого преподавателя формируем таблицы распределения нагрузки на каждую неделю семестра (табл. 6). Таблица 5 Последовательность проведения занятий преподавателями № пары Преподаватель 55 Преподаватель 1 Преподаватель 2 56 Преподаватель 1 57 Преподаватель 1 58 Преподаватель 1 Преподаватель 2 59 Преподаватель 1 Преподаватель 2 60 Преподаватель 1 Преподаватель 2 61 Преподаватель 1 62 Преподаватель 3 Преподаватель 4 Таблица 6 Распределение учебной нагрузки преподавателя Дисциплина Параметр ns nf 1 2 3 4 5 6 7 8 9 10 Предмет 2 1 6 1 1 4 5 4 Предмет 3 1 10 1 1 4 4 2 6 3 Предмет 4 1 10 3 2 4 4 5 2 6 3 Практика 3 1 2 12 12 Предмет 5 2 5 2 2 Практика 1 6 7 12 6 Практика 2 8 10 12 12 12 Итого 17 16 17 12 17 16 18 18 12 12 Свободные занятия 16 18 15 18 17 18 18 18 18 18 Х -1 2 -2 6 0 2 0 0 6 6 В табл. 6 значения в строке «Свободные занятия» определяют количество занятий, которые преподаватель имеет возможность провести на той или иной неделе семестра; X - число, определяющее разность между количеством занятий, которые преподаватель может провести на определенной неделе семестра, и планируемым количеством. Этап 6. Создаем таблицу «Таблица преподавателей», структура которой соответствует структуре табл. 7. В нее заносится информация о том, сколько занятий можно еще запланировать преподавателям на первой неделе (для которой создается расписание занятий). Таблица 7 Таблица преподавателей Преподаватель Количество занятий Этап 7. Осуществляем изменения в таблицах распределения учебной нагрузки преподавателей. Выполнение данного этапа базируется на следующих правилах. 1. Изменения начинаем с таблицы того преподавателя, у которого на первой неделе X < 0 (в порядке от большего значения к меньшему). 2. Последовательно, переходя от одной дисциплины к другой, уменьшаем количество занятий по дисциплинам на первой неделе путем их переноса на следующую неделю. При этом выбор дисциплин осуществляется в порядке увеличения количества занятий, запланированных на первой неделе. 3. Если количество занятий по дисциплинам одинаково, то при переносе выбираем ту, проведение занятий по которой заканчивается позднее. При одинаковых характеристиках дисциплина выбирается случайным образом. 4. Если на первой неделе количество занятий по дисциплине стало равным минимально допустимому значению и эта дисциплина ранее уже преподавалась, то оставляем ее в списке дисциплин, планируемых к преподаванию. 5. Перемещение занятия по практике не допускается. 6. При перемещении занятий преподавателя вносим изменения в таблицы учебной нагрузки преподавателей, используя информацию, приведенную в табл. 5, и в данные табл. 7. 7. Пункт 4 нарушаем в том случае, если произведенные действия не позволили достичь суммарной недельной нагрузки, установленной стандартом. Этап 8. Анализируя таблицы «Распределение учебной нагрузки преподавателя», вносим изменения в таблицы «Дисциплины, планируемые для группы» (см. табл. 4). Результат этих изменений - уменьшение для некоторых групп количества занятий, запланированных на этапе 3. Этап 9. Для каждого преподавателя создаем таблицы «Сводные часы преподавателя», структура которых соответствует структуре табл. 8, где Ni - номер недели, на которой заканчивается преподавание какой-либо дисциплины преподавателя (номера недель располагаются в порядке возрастания); Xsvodi - число, определяемое по формуле , где - значения, взятые из табл. 6. Таблица 8 Сводные часы преподавателя Номер недели N1 N2 N3 … Nn Сводные часы Xsvod1 Xsvod2 Xsvod3 … Xsvodn Этап 10. Используя таблицы «Сводные часы преподавателя», формируем табл. 9, где Ri - номер временного промежутка, по истечении которого преподаватель заканчивает преподавание какой-либо дисциплины. Если у преподавателя количество временных промежутков меньше, чем предусмотрено в таблице, соответствующие ячейки не заполняются. Таблица 9 Промежуточные суммы часов преподавателей Преподаватель Номер временного промежутка R1 R2 … Rn Преподаватель 1 N1n X1svodn N1n-1 X1svodn-1 … N11 X1svod1 Преподаватель 2 N2n X2svodn N2n-1 X2svodn-1 … … Этап 11. На данном этапе, анализируя табл. 9, выполняем действия по ликвидации разницы между планируемым количеством занятий и количеством занятий, которые преподаватель может провести в рамках определенного временного промежутка в течение семестра. Ликвидацию этой разницы пытаемся осуществить за счет освободившихся занятий в группах на этапе 8 (табл. 4). Для этого выполняем действия, представленные в виде блок-схемы на рис. 1. Рис. 1. Последовательность действий при наличии «свободных пар» в группах Этап 12. Если перенос занятий осуществлен, однако X < 0 и преподавателю на текущей неделе еще можно увеличить количество занятий (табл. 7), то увеличиваем количество занятий этому преподавателю на первой неделе за счет уменьшения количества занятий у других преподавателей, оставшаяся нагрузка которых позволяет это сделать. Для этого: 1. Если в табл. 9 рассматривается первый временной промежуток, то выполняем последовательно действия, представленные на рис. 2. Рис. 2. Последовательность действий при замене дисциплины одного преподавателя на дисциплину другого 2. Если в табл. 9 рассматривается иной временной промежуток, то: - определяем значение , где Х - это значения предыдущих временных промежутков, взятые из табл. 9; - определяем список дисциплин, которые продолжают включаться в расписание по окончании этого временного промежутка; - определяем значения: , , , , где Xi - количество занятий по дисциплине, взятое из табл. 6; Cd - количество занятий по дисциплине, взятое из табл. 7. По формуле осуществляем проверку: , где - значение X на рассматриваемом временном промежутке табл. 9. 3. Если условие выполняется, то это означает, что за счет переноса занятий по дисциплинам, планируемых на рассматриваемом временном промежутке на будущие периоды, значение будет выровнено. Таким образом, «снимать» какие-либо другие дисциплины из планируемого расписания на неделю необходимости нет. 4. Если условие не выполняется, то осуществляем перестановку занятий аналогично пункту 1 на разницу . Этап 13. Если в таблицах «Дисциплины, планируемые для группы» (см. табл. 4) по-прежнему остаются «свободные» занятия, то: 1. Создаем таблицу, структура которой представлена в виде табл. 10. 2. Заполняем эту таблицу, указывая преподавателей, у которых имеется возможность увеличить количество занятий на первой неделе (Xsvodn - значения получаемые из табл. 8). Таблица 10 Загруженность преподавателей Преподаватель Xsvodn Записи в табл. 10 сортируем в порядке уменьшения значения параметра Xsvodn. Дальнейшие действия осуществляем согласно блок-схеме на рис. 3. Рис. 3. Последовательность действий при ликвидации «свободных» пар, оставшихся после выполнения предыдущих этапов В результате выполнения всех этапов получаем список дисциплин и количество занятий по этим дисциплинам, которые диспетчеру образовательной организации необходимо использовать на предварительном этапе формирования семестрового расписания занятий. Заключение В результате исследований были выявлены проблемы, с которыми диспетчер образовательной организации еженедельно сталкивается при формировании семестрового расписания занятий. Разработан метод, позволяющий решить проблему отбора дисциплин, включаемых в расписание для той или иной группы на определенную неделю семестра. Метод апробирован в условиях Камышинского технического колледжа (Волгоградская область). Данный метод позволяет не только существенно сократить время, затрачиваемое на формирование расписания занятий, но и улучшить качество расписания.
1. Dement'ev I. A., Toyvonen N. R., Vasenev Yu. B. Kreditno-modul'naya sistema i raspisanie zanyatiy // Sankt-Peterburgskiy universitet. 2006. № 17. URL: http://www.spbumag.nw.ru/2006/17/3.shtml.
2. Nizamova G. F. Matematicheskoe i programmnoe obespechenie sostavleniya raspisaniya uchebnyh zanyatiy na osnove agregativnyh geneticheskih algoritmov: avtoref. dis. … kand. tehn. nauk. Ufa, 2006. 16 s.
3. Makarcova E. A. Sredstva modelirovaniya i chislennye metody v zadache formirovaniya nachal'nogo raspisaniya zanyatiy: avtoref. dis. … kand. tehn. nauk. Saratov, 2006. 17 s.
4. Voronin I. V. Modeli i metody resheniya zadachi avtomatizirovannogo sostavleniya raspisaniy s intellektual'noy podderzhkoy prinyatiya resheniy: avtoref. dis. … kand. tehn. nauk. SPb., 2008. 16 s.
5. Asvad F. M. Modeli sostavleniya raspisaniya zanyatiy na osnove geneticheskogo algoritma na primere vuza Iraka: avtoref. dis. … kand. tehn. nauk. Voronezh, 2013. 16 s.
6. Maslov M. G. Razrabotka modeley i algoritmov sostavleniya raspisaniy v sistemah administrativno-organizacionnogo upravleniya: avtoref. dis. … kand. tehn. nauk. M., 2004. 24 s.
7. Semenyuta I. S. Sistemnyy analiz i optimizaciya tehnologicheskogo processa avtomatizacii sostavleniya raspisaniya zanyatiy vuza s determinirovannymi ogranicheniyami: avtoref. dis. … kand. tehn. nauk. Krasnodar, 2011. 23 s.
