Введение
ГЛАВА 1. Обзор и анализ существующих подходов и моделей, постановка научной проблемы и основные этапы её решения 17
1.1. Обзор и анализ существующих методов и моделей составления расписаний учебных занятий 17
1.1.1. Основные направления решения задачи составления расписания учебных занятий 17
1.1.2. Точные алгоритмы генерации расписаний 18
1.1.3. Эвристические подходы 25
1.1.4. Диалоговые методы 35
1.2. Общая постановка задачи составления расписания на примере МГУПБ 37
1.2.1. Этапы постановки задачи автоматизации создания расписания учебных занятий 37
1.2.2. Документы, используемые при планировании учебного процесса и составлении расписания 38
1.2.3. Ограничения и пожелания, учитываемые при составлении расписания 41
1.2.4. Требования к разрабатываемой программе 43
Выводы по главе 1 45
ГЛАВА 2. Формализация задачи, математическая модель составления расписания учебных занятий в высшем учебном заведении 46
2.1. Математическая модель задачи составления расписания учебных занятий в вузе 46
2.2. ЛГР-трудность задачи составления расписания учебных занятий 58
2.3. Методика оценки и сравнения различных вариантов расписаний .60
2.4. Иерархическая многоуровневая схема упорядочения критериев по их значимости 62
Выводы по главе 2 64
ГЛАВА 3. Алгоритмы решения задачи составления расписания учебных занятий в высшем учебном заведении 65
3.1. Эвристический алгоритм составления расписания 65
3.1.1. Исследование критичности занятий при формировании расписаний. Разработка алгоритма назначения занятий... 65
3.1.2. Разрешение конфликтных ситуаций возникающих при распределении заявок . 73
3.2. Решение задачи с использованием генетического алгоритма 80
3.2.1. Представление расписания в виде хромосомы (chromosomal representation) .82
3.2.2. Начальное решение (initial population).. 82
3.2.3. Селекция (selection) 82
3.2.4. Система скрещивания 88
3.2.5. Кроссовер (crossover) 88
3.2.6. Мутация (mutation) :...,..90
3.2.7. Естественный отбор 90
3.2.8. Оценка расписания (fitness evaluation) 94
3.2.9. Условия завершения (stopping conditions, termination) 94
Выводы по главе 3 96
ГЛАВА 4. Описание практической реализации автоматизированных систем составления расписаний 97
4.1. Архитектура разработанных систем 97
4.2. Описание программного обеспечения применявшегося для решения задач 100
4.3. Программное обеспечение необходимое для функционирования программ 100
4.4. Автоматизированная система составления расписания учебных занятий 101
4.4.1. Функциональная структура системы составления расписания учебных занятий 101
4.4.2. Сравнительный анализ автоматизированной системы "Университетское расписание" с аналогичными программами 105
4.4.3. База данных автоматизированной системы составления расписания учебных занятий 112
4.5. Автоматизированная система планирования графиков работы сотрудников 116
4.5.1. Функциональное назначение программы 116
4.5.2. Обзор разработанных алгоритмов для решения задачи составления графиков работы персонала 125
Выводы по главе 4 130
Заключение 132
Литература 135
Приложения 164
