Реферат 2
ВВЕДЕНИЕ 3
1 Задача о расписании 6
2 Классические методы решения задачи о расписании 9
2.1 Точные алгоритмы решения задачи об оптимальном расписании 9
2.2 Приближенные алгоритмы решения задачи об оптимальном расписании 10
2.3 Подход, основанный на сведении одной задачи к другой 10
3 Метод решения задачи о расписании на основе раскраски графа конфликтов 12
3.1 Графы конфликтов событий 12
3.2 Раскраска графа 12
3.2.1 Приближенный алгоритм раскраски графа 14
3.3 Дополнительные ограничения для событий и оптимизация расписания 14
3.4 Программная реализация и компьютерные эксперименты 15
ЗАКЛЮЧЕНИЕ 19
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 20
ПРИЛОЖЕНИЕ А 21
С необходимостью составления расписаний человек сталкивается ежедневно на всем протяжении своей жизни. И если в детстве нас это не заботило, этим занимались родители, то, вступив во взрослую жизнь, мы фактически вынуждены планировать личное время - иначе просто не успеть за ритмом современной жизни. Обычно у нас есть сроки для выполнения разных работ и примерное понимание, сколько это займет времени. Но поскольку делать несколько дел одновременно трудно, если не сказать невозможно, приходится составлять расписание, исходя из важности работ, их относительной зависимости друг от друга, продолжительности и т.д. Чаще всего мы успешно справляемся с задачей составления личного расписания. Можно даже сказать, что практически все люди руководствуются «похожими алгоритмами», стремясь сделать все дела к назначенному сроку. Очевидно, мы распределяем наши действия в порядке возрастания крайних сроков исполнения работ (дел). То есть задача, со сроком, который закончится в ближайшее время, естественно выполняется в первую очередь. Например, студенты во время экзаменационной сессии учат предмет с наименьшим директивным сроком (ближайший по дате сдачи экзамен). Если первый экзамен необходимо сдать 10-го июня, второй 14-го, а третий 18-го, при этом на каждый экзамен необходимо 3 дня, то большинство студентов составят такое расписание: «с 7-го по 10-ое подготовка к первому экзамену, с 10-го по 13-ое соответственно ко второму и с 14-го по 17-ое - к третьему». Но мы неизбежно столкнемся со сложностями при составлении расписаний, когда работ будет становиться все больше и больше при этом нужно учесть множество дополнительных условий и/или при составлении расписаний не для одного человека, а например для коллектива. Представьте себе сотни работ, проектов и десятки исполнителей, для которых необходимо составить расписание.
В процессе решения таких задач, были выработаны общие рекомендации, принципы и методики составления расписаний. В результате возник специальный раздел науки — теория расписаний. Эта наука возникла на основе других областей знания и тесно с ними связана. Таким образом, теория расписаний — это раздел прикладной математики, в котором изучаются математические постановки, и методы решения задач оптимального упорядочивания некоторых действий во времени.
Задачи составления расписаний возникают в частности:
• на производстве, при упорядочивании отдельных операций по исполнителям (цеха, станки) и по времени;
• при составлении расписания движения поездов, самолетов, общественного транспорта;
• при планировании занятий в учебных заведениях; при планировании занятости персонала, например график работы медработников;
• при выполнении многозадачных продолжительных проектов, например строительства зданий;
• при планировании проведения спортивных мероприятий;
• в компьютерных сетях при планировании очередности передачи пакетов информации и т.д.
Многие задачи в теории расписаний формулируются как оптимизационные, то есть среди множества допустимых расписаний необходимо найти такое расписание, при котором достигается оптимальное значение некоторого параметра. Под термином «оптимальность» подразумевается минимальное или максимальное значение выбранного параметра. Под «допустимостью» расписания подразумевается его (физическая) осуществимость.
Пример: необходимо построить спортивную площадку за наиболее короткий промежуток времени, при этом существующая последовательность выполнения работ должна быть соблюдена. Тогда допустимым расписанием будет то, при котором будет соблюдена последовательность работ, а оптимальное расписание - это допустимое расписание, при котором проект будет завершен в минимальные сроки.
В нашей работе мы рассматриваем задачу о составлении расписания факультета. Имеются группы студентов, занятия, которые должны посещаться студентами и преподаватели, которые ведут эти занятия. Расписание желательно составить так, чтобы не было противоречий (например, в одной и той же аудитории не должны вестись два разных занятия одновременно), чтобы были учтены пожелания преподавателей, чтобы количество занятий для каждой группы студентов в каждый день недели было примерно одинаковым и чтобы между занятиями было как можно меньше «окон». Конечно, поскольку все рассматриваемые множества в нашей задаче о расписании конечны, задачу можно решить перебором: переберём все возможные последовательности занятий (то есть построим все расписания для заданного множества занятий), проверим для каждой последовательности выполнение всех ограничивающих условий (то есть проверим расписание на допустимость) и среди допустимых выберем наиболее оптимальное по всем параметрам. Однако такой перебор займёт огромное количество времени.
Поэтому основная цель нашей работы - это разработать и реализовать алгоритм построения необходимого нам расписания, пусть и не самого оптимального, за разумное время.
Проделанную работу можно разделить на 2 этапа: 1-теоритическое введение в основные понятия теории расписаний , 2- практическая реализация программ.
В итоге мы имеем раскрашенный граф конфликтов, с назначенными ресурсами событиям, то есть построенное расписание. Без изучения теоретически основ теории расписаний решение задачи было бы сомнительным. Был проведен анализ методов решения задачи и выбран наиболее походящий - метод на основе раскраски графа конфликтов. Так же в работе рассмотрены классические методы решения задач расписания, наиболее подробно разобран один из них на примере метода полного перебора. Этому в частности посвящена 2 глава работы. В первой главе описывается задача на формальном и неформальном языках для полного понимания всей глобальности задачи построения автоматизированного расписания. А 3 глава собрана из частей, с которыми непосредственно было «взаимодействие», то есть описаны метод решения задачи, дополнительные ограничения и собственно сам алгоритм решения. Работа основана на данных 3 курса радиофизического факультета 1 семестра 2019 года. Полное количество событий - 84. Результат раскраски графа - 12 цветов. Все события распределены по дням и аудиториям - получено расписание, но не оптимальное.
Заметим, что текущая версия программы не учитывает ограничения пожелания преподавателей, но на данном этапе учитывает ограничения, возникающие из -за конфликтов между событиями и привязкой предметов к аудиториям.
