Реализация задачи многокритериальной оптимизации при проектировании автоматизированных информационных систем составления расписания учебных занятий | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 13 марта, печатный экземпляр отправим 17 марта.

Опубликовать статью в журнале

Авторы: ,

Рубрика: Информационные технологии

Опубликовано в Молодой учёный №48 (338) ноябрь 2020 г.

Дата публикации: 28.11.2020

Статья просмотрена: 31 раз

Библиографическое описание:

Булатицкий, Д. И. Реализация задачи многокритериальной оптимизации при проектировании автоматизированных информационных систем составления расписания учебных занятий / Д. И. Булатицкий, Д. Г. Жилин. — Текст : непосредственный // Молодой ученый. — 2020. — № 48 (338). — С. 16-19. — URL: https://moluch.ru/archive/338/75820/ (дата обращения: 27.02.2021).



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

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

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

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

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

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

Система требований к учебному расписанию

Рис. 1. Система требований к учебному расписанию

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

– объем учебных элементов, отводимый учебным планом;

– соблюдение временных интервалов;

– занятость преподавателей и обучающихся в одно и то же время;

– занятость аудиторного фонда в одно и то же время.

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

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

Создание автоматизированной информационной системы, обеспечивающей составление рационального расписания, невозможно без учета научных данных [1,2,3,4,5,6,7,8].

Так, С. В. Балтак и Ю. Н. Сотсковым [1] исследованы различные подходы к проектированию автоматизированных информационных систем составления расписания учебных занятий и представлен процесс составления расписания в виде раскраски вершин графа с дополнительными ограничениями на множестве цветов [1]. Для оптимизации раскраски графа созданы эвристические алгоритмы, позволяющие строить практически приемлемые расписания учебных занятий практически во всех образовательных организациях.

Сходный теоретико-методологический подход был использован С. Н. Зиминым [2] для проектирования программного модуля DemoGraph , способного составлять учебные расписания на основе исходных данных, вводимых пользователем. При этом процесс визуализируется и сохраняются полученные результаты. Кроме модуля DemoGraph в программу включен модуль IniCreator , позволяющий создавать файлы входных данных.

В диссертационном исследовании Т. В. Милехиной [4] задача построения расписания учебных занятий определена как задача линейного целочисленного программирования. Автором [4] исследовано 4 жестких ограничений и 10 мягких, из которых сконструированы частные критерии оптимальности, и для них выполняется линейная свертка с получением одного критерия оптимальности. Т. В. Милехина [4] в исследовании применила эвристический алгоритм последовательного размещения учебных занятий в сетке расписания.

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

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

Н. Ж. Саитов [5], исследуя проблемы составления расписания учебного процесса, основанного на кредитных технологиях, определяет пути их решения посредством разработки интеллектуализированной системы принятий решении при составлении расписания учебных занятий AVN Sсhedule Maker.Интеграция данной системы с автоматизированной системой управления учебным процессом вуза «AVN» позволила частично автоматизировать процесс составления расписания учебных занятий с учетом кредитной технологии в образовании и осуществлять планирование, контролирование учебного процесса, а также автоматически отслеживать выполнение принятых решений в соответствии с нормативными параметрами.

А. С. Хасухаджиевым, И. В. Сибикиной [8] разработан алгоритм решения задачи по составлению расписания, представлена блок — схема алгоритма, обобщающая различные научные исследования по теме.

Необходимость перехода образовательных организаций на использование семестрового расписания занятий обоснована в научной работе А. А. Сиделевым [7]. Ученым подробно описан метод, позволяющий на первом этапе решить проблемы отбора дисциплин.

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

Литература:

  1. Балтак С. В., Сотсков Ю. Н. Построение расписаний учебных занятий на основе раскраски вершин графа / С. В. Балтак, Ю. Н. Сотсков // Информатика. — 2006. — № 3. — С. 58–69.
  2. Зимин С. Н. Составление учебного расписания, используя теорию графов / С. Н. Зимин //Современные наукоемкие технологии. — 2007.- № 11. — С. 89–90.
  3. Клеванский Н. Н. Математическое моделирование формирования начальных многопериодных расписаний / Н. Н. Клеванский, Е. Ф. Кравцов // Вестник Саратовского государственного технического университета. — 2009. — Т. 3, № 1. — С. 100–106
  4. Милехина Т. В. Повышение эффективности кластерных систем обработки информации при решении оптимизационных задач (на примере задачи составления расписания занятий): автореф. дис. … канд. техн. наук / Т. В. Милехина. — Москва, 2011. — 23 с.
  5. Саитов Н. Ж. Проблемы составления расписания занятий в вузах при организации учебного процесса, основанного на кредитных технологиях [Электронный ресурс] // Universum: технические науки. — 2016. — № 2 (24). — Режим доступа: https://cyberleninka.ru/article/n/problemy-sostavleniya-raspisaniya-zanyatiy-v-vuzah-pri-organizatsii-uchebnogo-protsessa-osnovannogo-na-kreditnyh-tehnologiyah (дата обращения: 04.11.2020).
  6. Самсонова Н. В., Симонов А. Б. Составление расписания в высшем учебном заведении: математические методы и программные продукты [Электронный ресурс] // E-Management. — 2018. — № 1. — Режим доступа: https://cyberleninka.ru/article/n/sostavlenie-raspisaniya-v-vysshem-uchebnom-zavedenii-matematicheskie-metody-i-programmnye-produkty (дата обращения: 21.10.2020).
  7. Сиделев А. А. Метод отбора дисциплин, используемых при формировании семестрового расписания занятий [Текст] / А. А. Сиделев // Вестник АГТУ. — Серия: Управление, вычислительная техника и информатика. — 2017. — № 1. — С.69–79.
  8. Хасухаджиев, А. С., Сибикина, И. В. Обобщенный алгоритм составления расписания в вузе с учетом новых требований федеральных государственных образовательных стандартов [Текст] / А. С. Хасухаджиев А. С., И. В. Сибикина // Вестник АГТУ. — Серия: Управление, вычислительная техника и информатика. — 2016. — № 3. — С. 78–85.
Основные термины (генерируются автоматически): занятие, система требований, автоматизация расписания, автоматизированная информационная система, аудиторный фонд, многокритериальная оптимизация, многокритериальная оптимизация расписания, профессиональная образовательная организация, учебный план, учебный процесс.


Задать вопрос