Когда завуч самостоятельно составляет расписание, он ориентируется на большое количество информации, сверяет её, чтобы не случилось не приятных ситуаций. Другими словами, чтобы не поставить одного преподавателя в один и тот же урок в разные классы, завуч должен проверить списки классов, уроков и преподавателей. В программе это осуществляется благодаря программному коду, который все это сверяет сам. Но для начала осуществляются другие операции. Давайте по порядку рассмотрим алгоритм «запихивания» предмета в ячейку расписания.
Когда мы выбрали какой-то предмет в ячейке определенного класса.… Хотя давайте рассмотрим сразу на примере: Мы выбираем предмет черчение в 9 «Б» классе. Для начала программа должна знать ведется ли черчение в 9 классе, и она начинает проверять по базе — сколько часов стоит в неделю черчения в этом классе. Если количество часов равно нулю, то и выведется соответствующее сообщение.
Если же не равно нулю, то программа просматривает предметы за всю неделю в этом классе и просчитывает сколько раз черчение уже поставлено и если эта цифра равна общему количеству часов черчения в неделю, программа также выводит сообщение. В противном случае проверка продолжается. Далее происходит проверка преподавателя, т.е. не ведет ли он урок в этот момент в другом классе. А также проверяется рабочее время преподавателя, в котором расставляется время, когда он может работать, а когда не может.
5. Автоматическое составление расписания занятий образовательного учреждения
где 
– множество блоков занятий, в которых присутствует группа qn, а 
– множество блоков занятий, которые проводятся во время «пары» tj.
Авторами разработан метод «расстановки дисциплин», который подробно изложен в работе [3]. Этот метод осуществляет формирование расписания в два этапа. На первом этапе происходит равномерное распределение блоков занятий, относящихся к одной и той же дисциплине определенной группы по дням недели.
На этом этапе используется идея оценки свободы расположения [4] отдельного занятия в полученном расписании. Блоки занятий, которые должны быть проведены в определенные дни недели, либо при проведении которых задействуются одновременно несколько преподавателей и т.д., имеют гораздо меньшую свободу расположения, чем иные. Поэтому составление расписания должно начинаться с добавления в расписание блоков занятий, имеющих наименьшую свободу расположения.
Итогом выполнения работ на первом этапе становится заполненная таблица, структура которой показана в табл. 2. В ячейках таблицы будут находиться номера объектов (блоки занятий, которые должны быть проведены на планируемой неделе).
Рис. 1. Распределение учебной нагрузки
Таблица распределения блоков занятий
На втором этапе данного метода (расстановка объектов в течение дня) предлагается использовать возможности генетического алгоритма (ГА) [5], получившего свою известность в результате работ Джона Генри Холлонда и его последователей.
6 Составление расписания
Для формирования особей первоначальной популяции предлагается использовать матрицу совместимости, структура которой показана в табл. 3.
Матрица совместимости объектов
Список несовместимых объектов
Шаблон матрицы расписания
Кроме этого, создается шаблон матрицы расписания, структура которой соответствует табл. 4.
Значения «– 1» устанавливаются в тех ячейках таблицы, где проведение занятий по той или иной дисциплине (объект) в рамках рассматриваемого дня недели невозможно.
На следующем шаге формируются n копий шаблонов матрицы расписания.
Используя информацию, содержащуюся в матрице совместимости, последовательно заполняют копии матрицы расписания. При заполнении i-ой копии матрицы расписания последовательность групп определяется случайным образом.
Для определения лучшего варианта расписания занятий используется значение целевой функции (в терминах генетического алгоритма – функция приспособленности).
Лучшим вариантом расписания занятий (в терминах генетического алгоритма – особь) считается тот, для которого функция приспособленности имеет минимальное значение.
Фрагментом расписания (в терминах генетического алгоритма – ген) выступает совокупность строк расписания занятий, относящихся к определенной учебной группе.
Для итеративного получения состава вариантов расписаний занятий в ГА используют известный состав операций (селекция, скрещивание и мутация). В состав множества вариантов расписания, подлежащих рассмотрению на следующей итерации (поколения) включаются несколько вариантов расписания предыдущей итерации с самыми лучшими значениями функций приспособленности (так называемая элита). Такое же число вариантов с самыми худшими значениями функций приспособленности исключается. Часть вариантов расписания (потомков) образуется путем обмена случайно выбранных компонентов векторов пар вариантов расписания (родителей), отобранных случайно с преимущественным выбором особей с лучшими значениями функций приспособленностей (операция скрещивания). Для того, чтобы мощность множества вариантов на каждой итерации не изменялась, состав множества пополняется включением оставшихся вне скрещивания вариантов со случайным изменением одного или нескольких компонентов векторов (генов особи, операция мутации).
В работе классический алгоритм ГА модифицирован для того, чтобы исключить попадание недопустимых вариантов расписания в состав множества, рассматриваемого на следующей итерации: включение нового варианта в состав множества вариантов следующего поколения происходит только после проверки на допустимость согласно матрице совместимости (табл. 3).
Рис. 2. Особь и ее гены
Рис. 3. Граф, формируемый алгоритмом поиска замен
Кроме еженедельной проблемы, связанной с составлением расписания занятий, диспетчер образовательной организации практически ежедневно сталкивается с необходимостью внесения изменений в него, в связи с невозможностью выхода того или иного преподавателя на работу в определенный день. При этом изменения касаются не просто смены одного преподавателя на другого, а замены дисциплины.
При формировании расписания занятий и внесении изменений в него диспетчер образовательной организации вынужден учитывать не только последовательность чередования лекций и лабораторных работ, в рамках дисциплины, но и следить за тем, кто из преподавателей проводит, то или иное занятие. Авторами работы разработан алгоритм, позволяющий получить список блоков занятий, которые необходимо использовать, для того чтобы осуществить замену в существующем расписании занятий. Пошаговая реализация этого алгоритма представлена в работе [6]. Алгоритм реализован в виде рекурсивной функции, которая строит граф и осуществляет в нем поиск.
Каждый раз при рассмотрении вопроса выставления той или иной дисциплины в список – «Преподаватели» помещается список тех преподавателей, которые должны будут проводить занятие по новой рассматриваемой дисциплине. Это необходимо для того, чтобы при попытке замены одной дисциплины на другую убедиться в том, что необходимые преподаватели ранее не задействованы в данном цикле замен.
Предусмотрен список преподавателей, замена которых невозможна: для преподавателей из этого списка повторные проверки не проводятся.
Применение разработанных методов и алгоритмов, реализованных в рамках единой информационной системы управления колледжем, позволило не только значительно облегчить работу диспетчера образовательной организации, но и получать более качественное расписание, отвечающее не только обязательным ограничениям, но и пожеланиям как со стороны преподавательского состава, так и со стороны учебных групп.
Источник: top-technologies.ru
Saved searches
Use saved searches to filter your results more quickly
Cancel Create saved search
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window.
Reload to refresh your session.
Дипломный проект на кафедре ИУ9 (бакалавриат) на тему «Составление расписания занятий в университете с помощью SMT-солвера»
aikarkin/iu9.diploma
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Switch branches/tags
Branches Tags
Could not load branches
Nothing to show
Could not load tags
Nothing to show
Name already in use
A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Cancel Create
- Local
- Codespaces
HTTPS GitHub CLI
Use Git or checkout with SVN using the web URL.
Work fast with our official CLI. Learn more about the CLI.
Sign In Required
Please sign in to use Codespaces.
Launching GitHub Desktop
If nothing happens, download GitHub Desktop and try again.
Launching GitHub Desktop
If nothing happens, download GitHub Desktop and try again.
Launching Xcode
If nothing happens, download Xcode and try again.
Launching Visual Studio Code
Your codespace will open once ready.
There was a problem preparing your codespace, please try again.
Latest commit
Git stats
Files
Failed to load latest commit information.
Latest commit message
Commit time
README.md
В данном репозитории приводятся исходный код к програмному решению, реализованному в рамках дипломной работы.
Програмное решение выполняет решение задачи автоматического составления расписания занятий в университете для заданного списка учебных групп с помощью SMT солвера. Более подробное описание дипломной работы можно найти в расчетно пояснительной записке. Данное решение соститоит из базы данных, в которой хранится вспомогательная информация для составления расписания, а также из ряда утилит для генерации расписания и формирования pdf-документа с раписанием занятий группы.
Проект реализован на языке Java. Для сбоорки проекта использовался Maven. Весь проект состоит из следующих модулей (каждому модулю соответствует одноименная папка в корневой директории проекта):
- dbfill — консольная утилита для заполения базы;
- smtgen — косольная утилита для автоматического составления расписания с помощью SMT-солвера.
- pdfgen — консольная утилита для генерации pdf-документа для заданной группы.
- schedule-core — вспомогательны модуль, содержит базовые классы, необходимые для решения вышеописанных утилит: классы-сущности базы, репозитории для доступа к данным, файл конфигурации настройки Hibernate (параметры подключения, стратегия обновления сущностей, список сущностей) и др.
- schedule-parser — вспомогательный модуль, содержит классы для парсинга csv-файлов, а также парсинга html-страниц с расписанием. Парсинг html-страниц используется для сбора вспомогательной информации, которая нужна на этапе составления расписания. Парсинг csv-файлов используется для заполнения базы данными с помощью утилиты dbfill.
По-мимо папки с модулями, в данном репозитории можно найти следующие директории:
- ./build — готовые jar-приложения (утилита smtgen может не работать на разных архитектурах из-за библиотеки Z3, поэтому может понадобиться пересборка данного модуля).
- ./docs — папка с вспомогательными материалами (документами), которые использовались входе выполнения ВКР.
- ./sql — скрипты для создания базы.
Для запуска утилит понадобиться JRE 1.8, и PostgreSQL версии 10.8, либо docker в зависимости от выбранного способа установки и настройки базы.
Установка и настройка базы