Тип работы:
Предмет:
Язык работы:


РЕШЕНИЕ ЗАДАЧИ СОСТАВЛЕНИЯ РАСПИСАНИЯ С ПОМОЩЬЮ ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ

Работа №85756
Тип работыДипломные работы, ВКР
Предметматематика
Объем работы50
Год сдачи2017
Стоимость4260 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено 8
Не подходит работа?

Узнай цену на написание

Введение 3
1. Теоретические основы составления расписаний биоинспирированными
методами 5
1.1. Принципы и методы составления академических расписаний 5
1.2. Общие сведения о генетических алгоритмах 9
2. Математическая модель ГА для составления расписаний 19
2.1. Математическая модель составления академического расписания 19
2.2. Применение генетического алгоритма для составления академического
расписания 22
Заключение 29
Литература 30
Приложение 32
Приложение 1 32
Приложение 2 44

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

Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании студенческих
и аспирантских работ!


Составление академического расписания с помощью автоматизированных биоинспирированных методов представляет собой сложную организационную систему. Поскольку в настоящее время не существует универсальных прикладных программ для решения данной задачи, их разработка весьма актуальна.
Генетические алгоритмы являются универсальными методами оптимизации многопараметрических функций, что позволяет решать обширный диапазон задач. ГА имеют множество модификаций и сильно зависят от параметров. Зачастую небольшое изменение одного из них может привести к неожиданному улучшению результата. При применении генетических алгоритмов, следует помнить, что алгоритм полезен только в тех случаях, когда для данной задачи нет подходящего специального алгоритма решения. Именно поэтому их применение для разработки структуры академического расписания вполне обосновано.
В ходе исследований была написана программа в среде разработки Microsoft Visual Studio 2015 на языке C#, реализующая предложенный алгоритм составления академического расписания.
Представление результатов выполненной программы потребовалось написание собственного языка разметки на основе XML. Он позволяет в удобной форме хранить и производить автоматизированную обработку данных, что в дальнейшем может быть использован при написании программы, позволяющего осуществить ручную корректировку расписания.
Результаты экспериментальных расчетов показали, что разработанный комплекс может быть успешно реализован для составления основы академического расписания.



1. Gantt, H.L. A graphical daily balance in manufacture / H.L. Gantt // ASME Transactions. — 1903. — Vol. 24. — P. 1322 - 1336.
2. Bellman, R. Mathematical aspects of scheduling theory / R. Bellman // Journal of the Society of Industrial and Applaid Mathematics. 1956. Vol. 4. — P. 55 - 59.
3. Панченко, Т.В. Генетические алгоритмы: учебно-методическое
пособие / Т. В. Панченко; под ред. Ю. Ю. Тарасевича. — Астрахань: Издательский дом «Астраханский университет», 2007. — 87 с.
4. Лазарев, А. А. Методы и алгоритмы решения задач теории расписаний для одного и нескольких приборов и их применение для задач комбинаторной оптимизации/ А. А. Лазарев: диссертация доктора физико-математических наук: 01.01.09 Москва, 2007. — 426 с.
5. Еремеев, А. В. Генетические алгоритмы и оптимизация: учебное пособие / A. B. Ермеев. — Омск, ОмГУ, 2008. — 36 с.
6. Гладков, Л.А. Генетические алгоритмы: учебное пособие /
Л. А. Гладков, В. В. Курейчик, В. М. Курейчик // под ред.
B. М. Курейчика. — 2-е изд., испр. и доп. — М.: ФИЗМАТЛИТ, 2006.— 320 с.
7. Еремеев, А.В. Эволюционные алгоритмы: конспект лекций /
А. В. Ермеев. — Омск, ОмГУ. 2015.— 51 с.
8. De Jong, K.A. A formal analysis of the role of multi-point crossover in genetic algorithms. / K.A. De Jong, W.M. Spears // Annals of Mathematics and Artificial Intelligence, no. 5(1), 1992.
9. Лазарев, А.А. Теория расписаний. Задачи и алгоритмы. / А. А. Лазарев, Е. Р. Гафаров // МГУ РАН С.Н. Васильева, 2011. — 213 с.
10. Кабальнов, Ю.С Композиционный генетический алгоритм соствления расписания учебных занятий / Ю.С. Кабальнов, Л. И. Шехтман, Г. Ф. Низамова, Н. А. Земченкова // Вестник УГАТУ, Т.7, № 2 (15).
C. 99 - 107.
11. Астахова, И.Ф. Составление расписания учебных занятий на основе генетического алгоритма / И. Ф. Астахова, А. М. Фирас // Вестник Воронежского государственного технического университета, серия: Системный анализ и информационные' технологии. — 2013. — № 2. C.93 - 99.
12. Шарп, Д. Microsoft Visual C#. Подробное руководство. / Д. Шарп. — М.: Питер, 8-е издание, 2017. — 848 с.
13. Неруш, Ю.М. Проектирование логистических систем: Учебник и практикум для бакалавриата и магистратуры / Ю.М. Неруш, С.А. Панов, А.Ю. Неруш. — Люберцы: Юрайт, 2016. — 422 c.
14. Мартишин, С.А. Проектирование и реализация баз данных в СУБД MySQL с использованием MySQL Workbench: Методы и средства проектирования информационных систем и технологий. Инструментальные средства информационных систем: Учебное пособие / С.А. Мартишин, В.Л. Симонов. — М.: ИД ФОРУМ, НИЦ ИНФРА-М, 2012. — 160 c.
15. Елизаров, А.М. Веб-технологии для математика: основы MathML. Практическое руководство. / А.М. Елизаров, Е.К. Липачев, М.А. Малахальцев. — М.:ФИЗМАТЛИТ, 2010. — 192 с.


Работу высылаем на протяжении 30 минут после оплаты.



Подобные работы


© 2008-2022 Cервис помощи студентам в выполнении работ