Московский Государственный Университет имени М. В. Ломоносова
Факультет Вычислительной Математики и Кибернетики
Кафедра АСВК
Дипломная Работа
Алгоритм и инструментальные средства построения расписаний учебных организаций сочетающий жадные стратегии и стратегии ограниченного перебора
Выполнил: Балаханов В.А. группа 522
Научный руководитель: Костенко В.А.
Москва 2006
Содержание
1 Аннотация 3
2 Введение 4
3 Цели дипломной работы 5
4 Постановка задачи 6
4.1 Исходные данные 6
4.2 Расписание 8
4.3 Ограничения на расписание 9
4.4 Критерии оптимальности 10
5 Исследование задачи 12
5.1 Обзор программных средств 13
5.1.1 Цели обзора 13
5.1.2 Результаты обзора 13
5.1.3 Выводы 15
5.2 Обзор алгоритмов 15
5.2.1 Генетические алгоритмы 15
5.2.2 Алгоритмы с локальным преобразованием расписания 17
5.2.3 Метод имитации отжига 18
5.2.4 Алгоритмы ограниченного перебора 19
5.2.5 Жадные алгоритмы 20
5.2.6 Выводы 21
6 Описание алгоритма 23
6.1 Структуры данных 23
6.2 Основные операции 25
6.3 Описание основного алгоритма 27
6.4 Описание алгоритма ограниченного перебора 29
6.5 Алгоритм корректировки расписания 31
7 Описание программной реализации 34
7.1 Описание алгоритмической части 34
7.2 Описание интерфейсной части 35
8 Исследование алгоритма 38
8.1 Оценка сложности алгоритмов 38
8.2 Результаты испытаний 40
8.2.1 Методика испытаний 40
8.2.2 Результаты испытаний 41
9 Заключение 42
10 Список литературы 43
1Аннотация
В данной работе рассматривается решение задачи построения расписаний учебных организаций. Была исследована применимость различных алгоритмов для решения поставленной задачи, сделан обзор ряда существующих программных средств, предназначенных для автоматического построения расписаний учебных организаций. В рамках данной работы был разработан алгоритм построения расписаний учебных организаций, сочетающий жадные стратегии и стратегии ограниченного перебора, и проведено исследование эффективности этого алгоритма на данных факультета ВМиК МГУ. Также в данной работе описаны созданные программные средства, реализующие основные функциональные возможности данного алгоритма.
2Введение
Задача составления учебного расписания при кажущейся простоте постановки является весьма сложной. При составлении учебного расписания приходится учитывать целый ряд условий и ограничений. Некоторые из этих требований являются безусловными, без которых учебный процесс не может нормально функционировать. Такими требованиями являются, к примеру, назначение занятий в соответствии с учебным планом или исключение из расписания накладок в проведении занятий. Другие ограничения в той или иной мере определяют качество учебного процесса, как, например, равномерное распределение нагрузки в течение недели или требования к проведению определенных занятий в специализированных аудиториях. Некоторые условия могут лишь частично влиять на качество расписания, однако тоже могут являться немаловажными: личные пожелания преподавателей и учащихся к времени проведения занятий или минимизация переходов между аудиториями в течение учебного дня. Кроме этого, хотя многие из требований являются общими для многих учебных заведений, важность этих требований для различных учебных заведений могут различаться [1,2].
Однако при этом во многих учебных заведениях расписание составляется вручную и обычно представляет собой корректировку устоявшегося расписания и внесение в него незначительных доработок. Значительные же изменения в расписании представляют серьезную проблему, особенно при условии ограниченности учебных ресурсов.
В настоящее время существует ряд программных средств, позволяющих автоматизировать процесс создания и корректировки учебного расписания, однако они либо обладают ограниченными возможностями по заданию дополнительных ограничений и критериев качества расписания, либо всего лишь предоставляют возможность полуавтоматического составления и корректировки расписания при непосредственном участии в этом процессе человека.
|