Введение 3
Глава 1. Теоретические основы задачи составления расписания 5
1.1 Общие сведения о Теории Расписаний 5
1.2 Формулировка задачи составления расписания 7
1.3 Основные вопросы и подходы автоматического составления
расписания 9
1.4 Обзор и анализ алгоритмов решения задачи составления расписания
и существующих программ на рынке ПО 12
Выводы к главе 1 31
Глава 2. Исследование процесса оставления расписания в институте. Математическая постановка задачи 33
2.1 Порядок составления расписания института в ручном режиме 33
2.2 Математическая постановка задачи 35
Глава 3. Программная реализация комплекса составления расписания 42
3.1 Организация хранения данных для составления расписания 42
3.2 Модуль расчета поставленной задачи 45
3.3 Модуль проверки сформированного расписания 49
Заключение 54
Список использованных источников 56
Приложение A
Приложение B
Быстрое развитие высших учебных заведений требует нового подхода к решению задач управления учебной деятельностью вузов. Этот подход в последние годы находит свое воплощение в применении математических методов в управлении и современных средств вычислительной. К техническим процессам, которые всегда выполнялись вручную применяют различного рода системы автоматизации и это получает все большее распространение в современном мире.
Один из таких процессов в учебных заведениях - это формирование расписания. Ручное составление расписания составителем расписания для достаточно большого количества учебных групп института занимает большое количество времени. К тому же большое количество ограничений и требований, которые необходимо учесть при формировании расписания ведут к многочисленным ошибкам, которые сказываются как на организации учебного процесса, так и на эффективности обучения. На сегодняшний день задача составления расписания (в том числе для высших учебных заведений) является очень распространенной и несмотря на то, что область знаний берет свое начало с начала 20 века, до сих пор данный вопрос остается открытым. Этим подтверждается актуальность выбранной темы исследования.
Целью данной работы является создание комплекса программ для автоматизации процесса составления расписания в институте.
Для достижения поставленной цели определены ряд задач:
1) Исследовать предметную область и изучить теоретическую базу для решения задач теории расписаний.
2) Рассмотреть алгоритмы для решения поставленной задачи, проанализировать рынок программных обеспечений автоматизированного составления расписания.
3) Изучить процесс составления расписания в институте, выявить основные особенности и построить математическую модель для решения задачи.
4) Организовать способ хранения данных для формирования расписания.
5) Разработать модуль считывания входных данных, модуль решения задачи линейного программирования и модуль проверки сформированного расписания.
Новизна диссертационной работы раскрывается следующими пунктами:
- Использование технологии интеграции программы с таблицами MS Excel, что является достаточно простым и удобным для пользователя. С одной стороны, интерфейс таблиц достаточно прост и удобен для редактирования, с другой, входные данные (такие как учебная нагрузка групп) изначально формируются в формате Excel.
- Разработка модулей программы, адаптированных для определенного института. Системы составления расписания сильно зависимы от специфики и особенностей учебных заведений. Это проявляется уже на этапе построения математической модели и представления данных. С этой точки зрения было принято решение создавать модули, ориентированные на конкретное учебное заведение.
В ходе проделанной работы были изучены теоретические основы области Теории Расписаний. Была сформулирована задача составления расписания для учебных заведений, в общем случае она описывается следующим образом: «С использованием множества учебных аудиторий (компьютерных, лекционных, лабораторных и так далее) и заданного набора временных интервалов (учебных пар, уроков) необходимо составить распределение учебных занятий для объектов (преподавателей, учителей, учебных групп) с наилучшим критерием оптимальности». Рассмотрены основные вопросы автоматизации данного процесса.
На этапе обзора и сравнения существующих программных средств автоматического составления расписания, были проанализированы 4 популярные системы, широко распространенные на российском рынке. Оценка программ производилась по заданным ранее критериям (гибкость настройки, удобство интерфейса, эффективность алгоритма, цена, системные требования программ, возможность корректировки и оптимизации оставленного расписания). Данное исследование послужило ориентиром для создания интерфейса и возможностей комплекса, разрабатываемого в ходе работы. На этапе изучения алгоритмов решения поставленной задачи были рассмотрены достоинства и недостатки каждого из них. Было принято решение использовать алгоритм целочисленного линейного программирования для решения поставленной задачи.
Был исследован процесс ручного составления расписания в институте, выделены особенности. На основе данных исследований построена математическая модель задачи, которая включает в себя ограничения для расписания и возможные постановки целевых функций.
На этапе реализации комплекса организована структура хранения данных, необходимых для составления расписания в формате Excel таблиц.
Был разработан модуль проверки расписания (на основе актуального на сегодняшний день формата формирования расписания в институте) на накладки по времени для аудиторий и преподавателей. С использованием библиотеки решения задач линейного программирования симплекс методом была рассчитана конкретная задача формирования расписания для небольшого количества входных данных.
Результаты работы могут быть применены для исследования задач формирования расписания в высших учебных заведениях и для дальнейшей разработки автоматического составления расписания в институте. В том числе работа может быть частично использована для формирования расписания диспетчером в институте (ответственным за составление расписания).
Помощь студентам и аспирантам в выполнении работ от наших партнеров
