Задачи составления расписания возникают там, где существует некоторая возможность планового выполнения работ: на производстве, при обслуживании клиентов в банках, организациях торговли и т.п., при формировании очередности выполнения программ вычислительным центром, организации отдыха в выходные дни, а также при организации занятий в учебных заведениях.
Составление плана учебной работы на семестр с помощью известных подходов и алгоритмов является весьма сложной задачей, так как при этом должны учитываться все требования учебных планов и программ, требований Министерства образования и науки, возможностей ресурсов учебного заведения, положения преподавателей.
В настоящее время не существует универсальных и общедоступных прикладных программ для решения данной задачи и поэтому их разработка на сегодняшний день весьма актуальна.
Целью данной работы является построение математической модели автоматизации составления расписания, основанной на применении генетических алгоритмов, и ее практическая реализация на языке программирования C#.
Для достижения цели работы требуется решить следующие задачи:
1) изучить теорию составления расписаний;
2) построить вариант генетического алгоритма для автоматизации составления расписаний;
3) разработать программное обеспечение, на основе которого
может быть построена математическая модель алгоритма.
4) создать собственный язык разметки, для представления и автоматизированной обработки расписаний.
Работа носит практико-ориентированный характер. В качестве новизны можно отметить разработанный язык разметки расписания, основанный на язык XML.
Выпускная квалификационная работа объемом 31 страницы основного текста состоит из, введения, двух частей, заключения, списка литературы, двух приложений и включает 11 рисунков и одну таблицу. Первая часть работы посвящена обзору теории расписаний и такому аппарату решения трудно формализуемых задач как эволюционные (или, по-другому, генетические) алгоритмы. Во второй части построена математическая модель и алгоритм решения поставленной задачи, а также представлено программное обеспечение для составления расписания, создание собственного языка разметки; приведены полученные результаты. В заключении проведены итоги проделанной работы.
Составление академического расписания с помощью автоматизированных биоинспирированных методов представляет собой сложную организационную систему. Поскольку в настоящее время не существует универсальных прикладных программ для решения данной задачи, их разработка весьма актуальна.
Генетические алгоритмы являются универсальными методами оптимизации многопараметрических функций, что позволяет решать обширный диапазон задач. ГА имеют множество модификаций и сильно зависят от параметров. Зачастую небольшое изменение одного из них может привести к неожиданному улучшению результата. При применении генетических алгоритмов, следует помнить, что алгоритм полезен только в тех случаях, когда для данной задачи нет подходящего специального алгоритма решения. Именно поэтому их применение для разработки структуры академического расписания вполне обосновано.
В ходе исследований была написана программа в среде разработки Microsoft Visual Studio 2015 на языке C#, реализующая предложенный алгоритм составления академического расписания.
Представление результатов выполненной программы потребовалось написание собственного языка разметки на основе XML. Он позволяет в удобной форме хранить и производить автоматизированную обработку данных, что в дальнейшем может быть использован при написании программы, позволяющего осуществить ручную корректировку расписания.
Результаты экспериментальных расчетов показали, что разработанный комплекс может быть успешно реализован для составления основы академического расписания.
