Журналы Конференции Монографии Учебники Нормативные документы Мероприятия ВКР
Отправить рукопись
Главная / Журналы / Вестник Астраханского государственного технического университета. Серия: Управление, вычислительная техника и информатика / Том 2016 Номер 3 / ОБОБЩЕННЫЙ АЛГОРИТМ СОСТАВЛЕНИЯ РАСПИСАНИЯ В ВУЗЕ С УЧЕТОМ НОВЫХ ТРЕБОВАНИЙ ФЕДЕРАЛЬНЫХ ГОСУДАРСТВЕННЫХ ОБРАЗОВАТЕЛЬНЫХ СТАНДАРТОВ
ОБОБЩЕННЫЙ АЛГОРИТМ СОСТАВЛЕНИЯ РАСПИСАНИЯ В ВУЗЕ С УЧЕТОМ НОВЫХ ТРЕБОВАНИЙ ФЕДЕРАЛЬНЫХ ГОСУДАРСТВЕННЫХ ОБРАЗОВАТЕЛЬНЫХ СТАНДАРТОВ
Отправить рукопись
Цитировать
Цитирований:

ОБОБЩЕННЫЙ АЛГОРИТМ СОСТАВЛЕНИЯ РАСПИСАНИЯ В ВУЗЕ С УЧЕТОМ НОВЫХ ТРЕБОВАНИЙ ФЕДЕРАЛЬНЫХ ГОСУДАРСТВЕННЫХ ОБРАЗОВАТЕЛЬНЫХ СТАНДАРТОВ
Хасухаджиев Апти Саид-Ахмадович 1
Сибикина Ирина Вячеславовна 2
Авторы:
1.  Астраханский государственный технический университет

2.  Астраханский государственный технический университет (кандидат технических наук, доцент; доцент кафедры информационной безопасности )

Тип:
Статья
Страницы:
с 78 по 86
Статус:
Опубликован
Получено:
05.07.2016
Одобрено:
28.02.2020
Опубликовано:
25.07.2016
Классификаторы:
ВАК 05.12.2013 Системы, сети и устройства телекоммуникаций
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 519.854.2
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
Язык материала:
русский
Ключевые слова:
формирование расписания, управление, требования, алгоритм
Аннотация и ключевые слова
Аннотация (русский):
Описаны особенности процесса составления расписания в высших образовательных учреждениях, проведена классификация типов расписаний и требований к их составлению. Проанализированы достоинства и недостатки современных походов к автоматизации процесса составления расписания, представлены данные об используемых математических моделях и алгоритмах. Определены исходные данные, необходимые для формирования расписания учебных занятий. Сформировано множество показателей оценки качества расписания, представлены способы свертки критериев для упрощения процедуры выбора удовлетворительного расписания. Разработан алгоритм решения задачи по составлению расписания, представлена блок-схема алгоритма, обобщающая различные научные исследования по теме. Отмечается, что создание расписания - не одномоментный акт, т. к. во время учебного процесса может потребоваться его уточнение для обеспечения замены преподавателей при увольнении, отсутствии в связи с командировкой или болезнью, т. е. развитие базы знаний правил для автоматической генерации расписаний по-прежнему остается актуальной задачей.

Ключевые слова:
формирование расписания, управление, требования, алгоритм
Текст
Введение Внедрение кредитной технологии обучения требует от высших учебных заведений дальнейшего укрепления учебно-методической, материально-технической и научной базы. Задача составления расписания должна учитывать новые требования по организации учебного процесса. Это скажется на количестве показателей и ограничений при реализации алгоритмов выбора наилучшего расписания занятий. Задача автоматизации управления учебным процессом в высшем учебном заведении характеризуется [1]: - большим объемом разнородной обновляемой информации из различных структурных подразделений вуза, таких как учебный отдел, деканаты, кафедры, отделы АСУ и информационной безопасности; - сложностью формализации и идентификации параметров [2] и ограничений составляемого расписания, степень и качество учета которых полностью зависят от опыта и квалификации ответственного работника учебно-методического управления; - конфликтом интересов основных участников учебного процесса: студентов и преподавателей, кафедр - как владельцев специализированного оборудования и аудиторий, что налагает ограничения на свободу их использования в расписании; - трудоёмкостью адаптации универсальных алгоритмов составления расписания к нуждам конкретного учебного заведения, особенно с учетом новых условий работы вузов. Ключевыми направлениями модернизации новых возможностей реализации образовательных программ являются: - электронное обучение; - дистанционные образовательные технологии; - создание кафедр на производстве; - создание условий для обучения лиц с ограниченными возможностями здоровья и многое другое [3, 4]. Все это напрямую связано с планированием нагрузки преподавателей, которым потребуется больше свободного времени на внеаудиторную работу по подготовке новых курсов и их адаптации к новым требованиям на основе компетентностного подхода, подготовку научных статей, ведение документации и обновление учебно-методических комплексов каждые 5 лет, дистанционное общение со студентами и т. д. Следовательно, процесс формирования расписания также должен быть адаптирован к новым требованиям, а качество составленного расписания должно быть напрямую связано с эффективностью учебного и воспитательного процесса в вузах. Анализ задачи теории расписания в современных условиях Первые опубликованные исследования на тему автоматизации при составлении расписаний занятий появились еще в ХХ в. Математической основой таких работ является теория расписаний - раздел исследования операций, в котором строятся и исследуются математические модели календарного планирования. Задачи составления расписания возникают в разных сферах деятельности: - производство (упорядочение технологических операций по исполнителям и по времени); - транспорт; - образование (организация учебного процесса). Задаче о составлении оптимального расписания в той или иной области посвящено довольно большое количество работ [1, 5-24], что говорит о ее сложности и практической значимости. Подобные задачи связаны с упорядочением некоторых работ в зависимости от количества исполнителей или времени. Одновременно необходимо учитывать ограничения на последовательность выполнения работ, ограничения, связанные с исполнителями, и т. п. Цель решения таких задач - это построение допустимых расписаний при соблюдении всех ограничений или нахождение оптимального допустимого расписания по тому или иному критерию оптимальности (понятие оптимальности здесь заменяется понятием допустимости, удовлетворительности, рациональности), что является ещё более сложной задачей. Задача о составлении расписания в вузе является задачей многокритериальной оптимизации, т. к. необходимо учитывать достаточно большое количество критериев. Как правило, критериям назначается степень важности, оказывающая существенное влияние как на процесс, так и на качество составляемого расписания. Решение задач теории расписаний усложняется тем фактом, что большинство из них являются NP-трудными [4], и алгоритмы их решения, реализованные на ЭВМ, должны быть адаптированы для получения приемлемого варианта за предельно допустимое время. Отметим, что задача составления расписания зависит от других смежных задач, которые необходимо решать при организации учебного процесса, например от задачи составления учебной нагрузки, т. к. варианты ее распределения могут по-разному влиять на качество итогового расписания. Представим классификацию типов расписаний, которые генерируются в ходе реализации образовательных программ. Видами учебных расписаний для студентов являются: - расписание теоретических занятий (лекционных); - расписание практических занятий (семинары, практики); - расписание лабораторных занятий; - расписание промежуточной аттестации (экзаменационной сессии); - расписание ГИА (государственной итоговой аттестации); - расписание ГАК (государственной аттестационной комиссии); - расписание ликвидации академической задолженности; - расписание консультаций студентов; - расписание дистанционного общения со студентами, имеющими ограничения по здоровью. Сбор входных данных Исходными данными для составления расписания учебных занятий являются: - компетентностно-ориентированный учебный план специальности; - график учебного процесса; - тарификационная нагрузка преподавателей на учебный год; - виды учебных занятий (лекции, практические занятия, лабораторные работы); - сведения об имеющемся аудиторном фонде и его оборудовании; - данные о количестве студентов в учебных группах (подгруппах); - распределение групп для практических занятий между преподавателями; - мотивированные пожелания преподавателей. Таким образом, в качестве исходной информации при составлении расписания учебных занятий выступают: 1.Множество дисциплин изучения S (S1, …, SNs). Будем считать, что дисциплины S1 и S2, ассоциированные с одним и тем же предметом, например предметом «Методы оптимизации», различаются по признаку «Тип занятия»: S1 - «Методы оптимизации - лекция»; S2 - «Методы оптимизации - лабораторная». 2. Множество учебных групп G (G1, …, GNg). 3. Множество преподавателей T (T1, …, TNt). 4. Множество аудиторий, имеющихся в распоряжении A (A1, …, ANa). 5. Множество временных интервалов (пар) P (P1, …, PNp). 6. Множество требований D (D1, …, DNd). В вышеперечисленных множествах приняты следующие обозначения: NS - число дисциплин обучения; NG - число учебных групп; NT - число преподавателей; NA - число аудиторий; NP - число пар в течение семестра, причём пара представима в формате неделя.день.пара и их количество строго оговорено с учетом режима работы учреждения (пятидневка или шестидневка и др.) и определяется произведением числа дней в неделе (5 или 6), пар в течение дня (максимум 6) и количеством типов недель при формировании расписания (2 - четная и нечетная); ND - множество требований. Такие элементы расписания, как ПРЕДМЕТ, АУДИТОРИЯ И ПРЕПОДАВАТЕЛЬ не равноценны по отношению друг к другу по разным причинам и могут быть проранжированы. Например, в обеспечение требований новых федеральных государственных образовательных стандартов (ФГОС) доля работников из числа руководителей и работников организаций, деятельность которых связана с направленностью (профилем) образовательной программы, должна составлять не менее 10 %. Для них и сотрудников, совмещающих административные или другие должности, должны быть обеспечены «льготные» условия расписания в первую очередь. При распределении нагрузки, а следовательно, и составлении расписания (учитываем, что разрабатываемое информационное обеспечение специалисты в вузах, как правило, стараются интегрировать друг с другом) необходимо учитывать, чтобы кадровое обеспечение (доля ставки имеющих образование, соответствующее профилю преподаваемой дисциплины) было не менее 70 %. Это означает, что актуальна и задача оценки качества расписания по построенной модели нагрузки преподавателей кафедры с учетом новых требований ФГОС. Аудитории также могут различаться в зависимости от их соответствия: - правилам и нормам безопасности; - нормативам площадей; - возможностям индивидуального доступа к сети Интернет; - наличию свободного и лицензионного программного обеспечения; - наличию в аудитории специальных технических средств (электронные замки для учета посещаемости, видеокамеры для осуществления видеозаписи при защите выпускной квалификационной работы, проекторы, интерактивные доски; специальное оборудование для учащихся с ограниченными возможностями). Требования, предъявляемые к расписанию учебных занятий К расписанию предъявляется множество требований. Требования при составлении расписания также ранжируются и делятся на основные и второстепенные. К основным требованиям можно отнести следующие: 1. Отсутствие накладок. 2. Соответствие количества мест в аудитории количеству человек в группе. 3. Отсутствие «окон». 4. Соответствие аудитории типу занятия. 5. Обязательное проведение полного объёма занятий по учебному плану. 6. Ограничение на объём ежедневных занятий. К второстепенным требованиям отнесём следующие: 1. Равномерность нагрузки студентов в течение всего семестра и конкретного учебного дня. 2. Минимизация переходов между аудиториями или корпусами. 3. Избыточность количества мест в аудитории по отношению к количеству учащихся. 4. Компактность нагрузки преподавателей. Для сравнения вариантов расписания с точки зрения компактности (т. е. количества свободных дней для подготовки к аудиторным занятиям и выполнению научной, методической и организационной работы) предлагается следующая формула: , где - суммарное количество дней с аудиторными занятиями; - суммарное количество пар в течение недели. 5. Периодичность расписания и т. д. Обобщённая классификация требований к расписанию в вузе приведена на рис. 1. Рис. 1. Классификация требований при составлении расписания Общие этапы процесса обработки данных для формирования расписания приведены на рис. 2. Рис. 2. Диаграмма потоков данных Требования к составлению расписания экзаменационных сессий и показатели качества при составлении расписания Кроме требований, предъявляемых к расписанию учебных занятий, существует ряд требований к составлению расписания экзаменов: 1. Не менее 2 дней для подготовки к экзамену. 2. Не более 6 часов на экзамен для одной группы. 3. Не менее 2 часов на консультацию перед экзаменом. 4. Экзаменов в году не более 8, зачётов не более 10. 5. Время на сдачу устного экзамена - не более 15 минут. 6. Время на сдачу комплексного экзамена - не более 23 минут на одного студента. 7. Время на сдачу письменного экзамена - не более 3 часов (академических). 8. Время на выполнение задания билета - не более 1 часа (академического). 9. Время консультации перед комплексным экзаменом - не менее 2 часов на дисциплину, входящую в программу экзамена. Алгоритмы составления расписания должны опираться на ряд ограничений основного и второстепенного значения. Качество расписания оценивается через систему показателей, которые отражают уровень удовлетворенности заданным ограничениям. После учёта основных требований по составлению расписания учитываются второстепенные требования, в том числе пожелания преподавателей по проведению занятий (количество дней, определенные дни недели, определенная половина дня недели - особенно это актуально для внештатных преподавателей), географическое расположение корпусов (аудиторий) вуза для обеспечения минимума переходов студентов (преподавателей) между занятиями из аудитории в аудиторию, количество «окон». Тем самым преподаватели определяют множество запретов или ограничений на множестве требований, которые представляют собой векторы значений целевых функций. Требования, преподаватели и атрибуты аудиторий могут быть проранжированы. Определенные требования могут быть объединены в один обобщенный показатель качества на основе различных метрик. Обзор существующих методов для решения задачи составления расписаний и имеющихся программных разработок Задача составления расписания принадлежит классу NP-полных задач и может быть решена на базе таких различных подходов и методов, как: - классические методы в терминах целочисленного линейного программирования или задачи о раскраске графа [8-11]; - метаэвристические методы - метод имитации отжига, генетические алгоритмы и др. [7, 12, 15, 17, 18]; - мультиагентные системы, метод решения по прецедентам [13-15]. Обобщенный алгоритм составления расписания Систем для автоматического составления расписания достаточно много, например «Астра», «1С: ХроноГраф Расписание», «АВТОРасписание» и др. Практика показывает, что среди существующих систем больше тех, которые используются для первоначальной расстановки предметов и элементов расписания (обычно от 40 до 70 %) с последующей ручной доработкой [25]. Существующие программы ориентированы в основном на школы, колледжи и не всегда могут быть адаптированы к реалиям вуза, кроме того, они отличаются высокой стоимостью. Алгоритмы формирования расписания основаны на переборах вариантов с проверкой качества расписания на базе разных эвристик для облегчения и ускорения процедуры поиска. Особый интерес представляют эвристические алгоритмы, не имеющие строгого математического обоснования, но демонстрирующие приемлемое качество решения на практике. Так, опыт сотрудников учебного отдела показывает, что формирование расписания начинают с распределения предметов «первостепенных» - физкультура, иностранный язык и др. Далее имеет место декомпозиция задачи составления расписания в зависимости от множества участников, включенных в текущее распределение. Задача разбивается на части или, точнее, на ряд последовательно решаемых задач, при этом каждая задача, решенная на предыдущем шаге, является ограничением для задачи, подлежащей решению на следующем шаге. Потом, при доработке расписания, текущее расписание может видоизменяться по мере включения в распределение все большего количества новых участников. Соответственно, нужно определить величины, задающие уровень уступки в требованиях при изменении варианта расписания. Кроме того, необходимо определить целевую функцию, объединив структуру показателей качества расписания в ней. Обобщённый алгоритм составления расписаний представлен на рис. 3 со следующими обозначениями: Ns - число дисциплин обучения; Ng - число учебных групп; Nt - число преподавателей; Na - число аудиторий; Np - число пар в течение семестра; Nd - множество требований; - матрица разрешений: - матрица запретов: ; Ksпорог, Ktпорог - пороговые значения; Psпорог, Ptпорог - приоритеты дисциплин и преподавателей. Рис. 3. Обобщённый алгоритм составления расписаний Предложенный обобщенный алгоритм составления расписания учитывает результаты ряда научных исследований, касающихся решения задач теории расписания. Заключение В ходе исследований было сформировано множество показателей оценки качества расписания, представлены способы свертки критериев для упрощения процедуры выбора удовлетворительного расписания. Предложен обобщенный алгоритм составления расписания, учитывающий различные научные исследования, связанные с решением задач теории расписания. В настоящее время количество требований при формировании расписаний растет, вследствие чего автоматизированные комплексы необходимо перестраивать. Решение задачи по автоматическому формированию расписания сэкономит трудозатраты сотрудников учебных отделов, обеспечит принципы справедливости при составлении расписания, создаст максимально удобные условия для преподавательской деятельности, которая не ограничивается аудиторной нагрузкой. Создание расписания - это не одномоментный акт, во время учебного процесса может понадобиться доработка расписания, чтобы обеспечить замену преподавателей при увольнении, нахождении в командировке или при болезни коллег. Очевидно, что развитие базы знаний правил для автоматической генерации расписаний по-прежнему остается актуальной задачей.
Список литературы

1. Об образовании в Российской Федерации: федер. закон от 29 декабря 2012 г. N 273-ФЗ (в ред. Федеральных законов от 07.05.2013 N 99-ФЗ, от 07.06.2013 N 120-ФЗ, от 02.07.2013 N 170-ФЗ, от 23.07.2013 N 203-ФЗ, от 25.11.2013 N 317-ФЗ, от 03.02.2014 N 11-ФЗ, от 03.02.2014 N 15-ФЗ, от 05.05.2014 N 84-ФЗ). N 273-ФЗ). URL. http://www.consultant.ru/document/cons_doc_LAW_140174/.

2. Об утверждении порядка организации и осуществления образовательной деятельности по образовательным программам высшего образования - программам бакалавриата, программам специалитета, программам магистратуры: приказ Минобрнауки России от 19.12.2013 N 1367. URL: http://www.garant.ru/ products/ipo/prime/doc/70503294/.

3. Hahn-Goldberg S. Defining, Modeling, and Solving a Real University Course Timetabling. URL: http://tidel.mie.utoronto.ca/pubs/Theses/hahn-goldberg.masc.pdf.

4. Конвей Р. В., Максвелл В. Л., Миллер Л. В. Теория расписаний. М.: Наука, 1975. 360 c.

5. Crainic T. G., Toulouse M. Parallel Meta-heuristics. Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT-2009-22). Canada, 2009. 51 p.

6. Burke E. K., Marecek J., Parkes A. J., Rudova H. A supernodal formulation of vertex colouring with applications in course timetabling // Annals of Operational Research. 2010. Vol. 179, No. 1. P. 105-130.

7. Kuhn F. Weak Graph Colorings: Distributed Algorithms and Applications // SPAA '09 Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures. 2009. P. 138-144.

8. Burke E. K., Marecek J., Parkes J., Andrew J., Rudova H. Penalising Patterns in Timetables: Novel Integer Programming Formulations. In: Operations Research Proceedings 2007. Berlin: Springer, 2008. P. 409-414.

9. Boehning R. L., Butler R. M., Gillett B. E. A parallel integer linear programming algorithm // European Journal on Operations Research. 1988. Vol. 34, iss. 3. P. 393-398.

10. Abdullah S., Hamdan A. R. A Hybrid Approach for University Course Timetabling // International Journal of Computer Science and Network Security. 2008. Vol. 8, No. 8. P. 127-131.

11. Babkin E., Abdulrab H., Babkina T. Agent Time: A Distributed Multi-agent Software System for University’s Timetabling. Ma Aziz-Alaoui & C. Bertelle (eds.). From System Complexity to Emergent Properties. Heidelberg, Springer, 2009. P. 141-154.

12. Autry B. M., Squire K. University course timetabling with probability collectives. URL: http://bosun.nps.du/ uhtbin/hyperion-image.exe/08Mar_Autry.pdf.

13. Burke E. K., Petrovic S., Qu R. Case-based heuristic selection for timetabling problems // Journal of Scheduling. 2006. Vol. 9, No. 2. P. 115-132.

14. Yu E., Sung K. S. A genetic algorithm for a university weekly course timetabling // International Transactions In Operational Research. 2002. Vol. 9. P. 703-717.

15. Nandhini M., Kanmani Dr. S. A Survey of Simulated Annealing Methodology for University Course Timetabling // International Journal of Recent Trends in Engineering. 2009. Vol. 1, No. 2. P. 255-257.

16. Kirkpatrick S., Gelatt C. D., Vecchi M. P. Optimization by Simulated Annealing // Science. New Series. 1983. Vol. 220, No. 4598. P. 671-680.

17. Давыдов С. В. Система автоматического построения расписания учебных занятий. URL: http://davidovsv narod.ru/schedule/index.html.

18. Береговых Ю. В., Васильев Б. А., Володин Н. А. Алгоритм составления расписания занятий // Искусственный интеллект. 2009. № 2. С. 35-43.

19. Верёвкин В. И., Исмагилова О. М., Атавин Т. А. Автоматизированное составление расписания учебных занятий вуза с учётом трудности дисциплин и утомляемости студентов // Докл. Томск. гос. ун-та систем управления и радиоэлектроники. 2009. № 1 (19), ч. 1. С. 221-225.

20. Балтак С. В., Сотсков Ю. Н. Построение расписаний учебных занятий на основе раскраски вершин графа // Информатика. 2006. № 3 (11). С. 56-69.

21. Кабальнов Ю. С., Шехтман Л. И., Низамова Г. Ф., Земченкова Н. А. Композиционный генетический алгоритм составления расписания учебных занятий // Вестн. Уфим. гос. авиац. техн. ун-та. 2009. Т. 7, № 2 (15). С. 99-107.

22. Яндыбаева Н. В. Генетический алгоритм в задаче составления учебного расписания вуза // Современные наукоемкие технологии. 2009. № 11. С. 97-98.

23. Соуса Ф., Алвес А. Полностью эвристическое расписание занятий, управляемое пожеланиями студентов // Наукові праці Вінниц. нац. техн. ун-ту. 2009. № 2. С. 1-4.

24. Шишканова Т. А. Разработка методики построения автоматизированной системы управления учебным процессом. URL: http://www.giab-online.ru/files/Data/2013/12/366-372_SHishkanova_-_7_str.pdf.

25. Пиликов Н. П. Проблема полной автоматизации при составлении школьного расписания. URL: http://www.mnogosmenka.ru/pilikov/timetable.htm.

Контент доступен под лицензией Creative Commons Attribution 3.0 Unported

Поддержка Powered by Editorum,  Инструкции
Войти или Создать
* Забыли пароль?