Выбор метода составления расписания в системе поддержки принятия решений (СППР) - Студенческий научный форум

XIV Международная студенческая научная конференция Студенческий научный форум - 2022

Выбор метода составления расписания в системе поддержки принятия решений (СППР)

Демехина В.А. 1, Зайцева Т.В. 1
1Белгородский государственный национальный исследовательский университет
 Комментарии
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

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

В данной работе будут рассмотрены методы составления расписания в университете с выделением наиболее подходящего и оптимального при помощи СППР «Решение». Первым делом необходимо дать определение учебному процессу. Так, учебный процесс – это система организации учебно-воспитательной деятельности, в основе которой – органическое единство и взаимосвязь преподавания и учения; направлен на достижение целей обучения и воспитания [1]. Если рассматривать работу в качестве проекта выбора метода составления расписания, тогда потребуется соблюдение основополагающих условий. Например, выделить цель проекта, его сроки, а также границы. Целью проекта будет являться выбор метода составления расписания. Наиболее подходящий метод будет использоваться в дальнейшем для использования в подсистеме университета для составления учебных занятий. Что касается сроков, то на изучение отобранных методов с дальнейшим выбором наилучшего потребуется 10 дней, то есть с 08.01.2022 по 18.01.2022. Границами проекта является следующее:

Детально описываются требования составления расписания учебных занятий в ВУЗе.

Рассматриваются существующие алгоритмы и подходы к составлению расписания.

Определяются критерии выбора рассмотренных подходов.

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

Формулируется вывод на основе результата использования системы поддержки принятия решений для выбора алгоритма.

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

В данном проекте не планируется анализировать существующие программные продукты на основе того или иного алгоритма.

Анализа бизнес-процессов деятельности ВУЗа также не предусмотрено.

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

Разработка информационной системы также не будет осуществляться.

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

Соблюдение баланса в количестве занятий у студентов. Это значит, что на одного студента в день должно выставляться не более 8 академических часов.

Минимизация «окон» у студентов. В лучшем случае, расписание должно составляться без «окон», в противном случае, минимизировать их количество.

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

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

В период пандемии не допускать аудиторные занятия студентов, количество которых превышает 50 человек.

Требований может быть гораздо больше в зависимости от специфики ВУЗа.

Далее стоит рассмотреть существующие методы составления расписания занятий:

Агентный подход. Этот метод подразумевает разбиение задачи на мелкие подзадачи. Решением каждой подзадачи занимается агент. Например, можно разделить агентов преподавателей, агентов аудиторий и агентов учебных групп. Все имеющиеся агенты представляют единую мультиагентную систему. Существует две роли: организаторы и участники. Первую группу представляют преподаватели, вторую – учебные группы и аудитории [2]. Однако данный метод плохо удовлетворяет многим требованиям, например, не допускает ручной правки полученного расписания.

Метод теории графов. В этом методе подразумевается следующее: вершины графа представляют события (занятия), а ребра проводят между конфликтующими событиями, если в аудитории не должно проводиться одновременно два занятия. Простыми словами, в теории раскраски графов никакие две смежные вершины не должны иметь одинаковые цвета. Главным недостатком является низкая точность метода при большой размерности. Кроме того, учет пожеланий преподавателей и кафедр также невозможно реализовать в данном методе. Однако, применение этого подхода в результате отражает простую для понимания математическую модель [3].

Метод решения по прецедентам. Подход подразумевает запоминание в базе данных использование старого опыта для дальнейшего решения аналогичной задачи. Например, на основе составленного расписания группе конкретного направления подготовки в том году, можно составить аналогичное расписание первокурсникам этого же направления. В этом случае, с большей вероятностью будут учтены многие предпочтения преподавателей по типу желаемых аудиторий, либо дней и времени для выставления им расписания [4]. Отсутствие гибкости данного метода, а также возможное малое количество прецедентов порождает низкое качество составленного расписания.

Метод целочисленного программирования. Ориентировано на решение задач математического программирования, в которых все или некоторые переменные должны принимать только целочисленные значения. Данный метод реализуется посредством объявления переменных и ограничений к ним, а также составления целевой функции. Количество переменных и ограничений определяют размерность модели. Заключительным этапом является нахождение максимума или минимума целевой функции, используя математические методы. Главным недостатком является сложность решения задачи, если имеется большое количество ограничений и переменных – время работы алгоритма становится неприемлемо большим. Кроме того, найденное оптимальное решение не гарантирует его реализацию на практике. Метод хорош для тех задач, где имеется небольшое количество критериев, но в случае с составлением расписания, их изобилие не позволит оценить их влияние на результат [5].

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

Генетический алгоритм. Основан на природных процессах (использующий эволюционные принципы). Данный алгоритм реализуется в следующем порядке:

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

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

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

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

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

проверить условие прекращения работы алгоритма, при необходимости вернуться на этап селекции;

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

Теперь необходимо выделить критерии, по которым будет выбираться алгоритм (альтернатива) для составления расписания учебных занятий в университете при помощи метода анализа иерархий (МАИ). Для этого можно воспользоваться инструментом СППР «Решение». Метод анализа иерархий предусматривает использование ступенчатой структуры решения поставленной проблемы. На первом уровне указывается возникшая проблема (цель), второй уровень заполняется критериями, на третьем уровне указываются альтернативные решения, которые будут сравниваться по выделенным критериям. При отсутствии того или иного уровня задача считается не решаемой [8].

В этой работе будет использоваться программа СППР «Решение» - она построена на методе анализа иерархий. Достижение цели обусловливается выполнением следующих этапов:

Постановка проблемы (цели).

Декомпозиция проблемы.

Формирование команды экспертов.

Распределение решаемых задач по экспертам.

Попарное сравнение компонентов иерархии.

Обработка и вывод результата проверки.

Главным преимуществом программы является отражение отчета после выдачи результата. Отчет представляется в виде диаграмм и таблиц [9].

На Рисунке 1 представлена проблема и критерии для выбора метода составления расписания.

Рисунок 1 – критерии выбора метода

Как видно из рисунка, было выделено 5 критериев, по которым в дальнейшем будут сравниваться альтернативные решения для выбора наиболее подходящего. Следующим этапом является сравнение критериев по важности между собой (Рисунок 2).

Рисунок 2 – сравнение критериев

Далее начинается самый важный этап анализа, в котором будет происходить сравнение альтернативных решений по критериям. На Рисунке 3 представлено сравнение альтернатив по критерию «Гибкость».

Рисунок 3 – сравнение альтернатив по критерию «Гибкость»

В результате использования метода иерархии удалось получить наглядный результат выбора метода составления расписания в виде диаграммы (Рисунок 4).

Рисунок 4 – результат выбора метода

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

Таким образом, условия разработки проекта выполнены:

Определена цель проекта.

Определены сроки выполнения проекта.

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

Учебный процесс [Электронный ресурс]. – Режим доступа: https://center-yf.ru/data/stat/uchebniy-process.phphttps://center-yf.ru/data/stat/uchebniy-process.php

Дворянкин, А. М. Обзор методов составления расписания вузов / А. М. Дворянкин, В. С. Чалышев // Известия Волгоградского государственного технического университета. – 2011. – № 9(82). – С. 110-113.

Свиридова, О. В. Обобщенный анализ методов проектирования и разработки автоматизированного составления расписания образовательных учреждений / О. В. Свиридова, А. В. Михайлов. — Текст : непосредственный // Молодой ученый. — 2013. — № 6 (53). — С. 214-216. — URL: https://moluch.ru/archive/53/7132/ (дата обращения: 06.12.2021).

Введение в метод рассуждений по прецедентам [Электронный ресурс]. – Режим доступа: http://systematy.ru/articles/vvedenie_v_metod_rassujdeniy_po_pretsedentam

Алексеева Е. В. Построение математических моделей целочисленного линейного программирования. Примеры и задачи: Учеб. пособие / Новосиб. гос. ун-т. Новосибирск, 2012. 131 с.

Алгоритм имитации отжига [Электронный ресурс]. – Режим доступа: https://russianblogs.com/article/1710105576/

Астахова, И. Ф. Составление расписания учебных занятий на основе генетического алгоритма / И. Ф. Астахова, А. М. Фирас // Вестник Воронежского государственного университета. Серия: Системный анализ и информационные технологии. – 2013. – № 2. – С. 93-99.

Кравченко Г. М., Болотина А.Б., Андреев П.А. Принятие управленческих решений с использованием метода анализа иерархий: Учебно-методическое пособие для практических занятий. – М.: РУТ (МИИТ), 2018. – 31с., илл.

Лифиренко М.В., Ломакин В.В. Система поддержки принятия управленческих решений на основе усовершенствованного аналитико-иерархического процесса//Свидетельство о государственной регистрации программы для ЭВМ №2013616249 от 2 июля 2013 года.

Просмотров работы: 27