Разработка моделей и алгоритмов составления расписаний в системах административно-организационного управления

• Автор: Маслов, Михаил Геннадьевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Москва
• Количество страниц: 217 с.

Содержание
ВВЕДЕНИЕ
ГЛАВА 1. ОБЗОР И АНАЛИЗ СУЩЕСТВУЮЩИХ ПОДХОДОВ И МОДЕЛЕЙ, ПОСТАНОВКА НАУЧНОЙ ПРОБЛЕМЫ И ОСНОВНЫЕ ЭТАПЫ ЕЕ РЕШЕНИЯ

1.1. Обзор и анализ существующих методов и моделей составления

РАСПИСАНИЙ УЧЕБНЫХ ЗАНЯТИЙ

1.1.1. Основные направления решения задачи составления расписания учебных занятий.

1.1.2. Точные алгоритмы генерации расписаний

1.1.3. Эвристические подходы

1.1.4. Диалоговые методы

1.2. Общая постановка задачи составления расписания на примере МГУПБ.

1.2.1. Этапы постановки задачи автоматизации создания расписания учебных занятий.

1.2.2. Документы, используемые при планировании учебного процесса и составлении расписания
1.2.3. Ограничения и пожелания, учитываемые при составлении расписания
1.2.4. Требования к разрабатываемой программе.
ВЫВОДЫ ПО ГЛАВЕ 1.
ГЛАВА 2. ФОРМАЛИЗАЦИЯ ЗАДАЧИ, МАТЕМАТИЧЕСКАЯ МОДЕЛЬ СОСТАВЛЕНИЯ РАСПИСАНИЯ УЧЕБНЫХ ЗАНЯТИЙ В ВЫСШЕМ УЧЕБНОМ ЗАВЕДЕНИИ
2.1. Математическая модель задачи составления расписания учебных занятий в вузе.
2.2. АРтрудность задачи составления расписания учебных занятий
2.3. Методика оценки и сравнения различных вариантов расписаний
2.4. Иерархическая многоуровневая схема упорядочения критериев по их значимости.
ВЫВОДЫ ПО ГЛАВЕ 2
ГЛАВА 3. АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ СОСТАВЛЕНИЯ РАСПИСАНИЯ УЧЕБНЫХ ЗАНЯТИЙ В ВЫСШЕМ УЧЕБНОМ ЗАВЕДЕНИИ.
3.1. Эвристический алгоритм составления расписания.
3.1.1. Исследование критичности занятий при формировании расписаний. Разработка алгоритма назначения занятий
3.1.2. Разрешение конфликтных ситуаций возникающих при распределении заявок.
3.2. Решение задачи с использованием генетического алгоритма.
3.2.1. Представление расписания в виде хромосомы i
3.2.2. Начальное решение iii i.
3.2.3. Селекция i.
3.2.4. Система скрещивания
3.2.5. Кроссовер v.
3.2.6. Мутация i.
3.2.7. Естественный отбор.
3.2.8. Оценка расписания i vi.
3.2.9. Условия завершения i ii, ii
ВЫВОДЫ ПО ГЛАВЕ 3
ГЛАВА 4. ОПИСАНИЕ ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИ АВТОМАТИЗИРОВАННЫХ СИСТЕМ СОСТАВЛЕНИЯ РАСПИСАНИЙ
4.1. Архитектура разработанных систем
4.2. Описание программного обеспечения применявшегося для решения
4.3. Программное обеспечение необходимое для функционирования программ
4.4. Автоматизированная система составления расписания учебных занятий.
4.4.1. Функциональная структура системы составления расписания учебных занятий
4.4.2. Сравнительный анализ автоматизированной системы Университетское расписание с аналогичными программами.
4.4.3. База данных автоматизированной системы составления расписания учебных занятий
4.5. Автоматизированная система планирования графиков работы сотрудников.
4.5.1. Функциональное назначение программы.
4.5.2. Обзор разработанных алгоритмов для решения задачи составления графиков работы персонала
ВЫВОДЫ ПО ГЛАВЕ 4.
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Обзор и анализ существующих подходов и моделей, постановка научной проблемы и основные этапы е решения. Методы первого направления разнообразны, но применимы лишь при малом объеме пространства поиска решения. В противном случае объем вычислений при решении задачи резко увеличивается. Упрощения же, применяемые к задаче составления учебного расписания в вузе, могут значительно исказить настоящую картину процесса, если используемые допущения не могут быть выполнены. При эвристическом моделировании оказывается возможным организовать направленный поиск при решении задачи в полном объеме. Данные методы используют, как эвристическое моделирование действий человека, составляющего расписание, при наличии некоторых количественных критериев, так и специализированные математические и эвристические методы направленного поиска. Работы данного направления характерны обилием различных математических методов при сильном искусственном упрощении настоящей картины процесса. Это объясняется большим объемом пространства поиска решения, присущим задачам составления учебных расписаний. При большом объеме пространства поиска метод полного перебора, как и метод случайного поиска решения, не представляется возможным изза трудности вычислений. Естественны два пути поиска решения направленный поиск и сокращение пространства поиска до таких размеров, когда ненаправленный поиск станет эффективным. Алгоритмы этой группы используют методы теории графов, комбинаторного анализа. Эти алгоритмы обеспечивают пересмотр допустимых вариантов расписания, базируясь на выборе того или другого метода их построения, с целью определения такого варианта расписания, который в наибольшей степени соответствует принятым критериям оптимальности. Например, в результате соответствующей модификации существующих программ расчета временных параметров сетевых графиков, можно создавать программные генераторы допустимых расписаний, при наличии которых задача построения оптимального расписания может быть решена перебором конечного числа возможных вариантов расписания 7. Изза большой размерности задачи составления учебного расписания однократное решение ее на ЭВМ требует выполнения большого числа машинных операций. Кроме того, число допустимых вариантов расписания обычно тоже очень большое. В связи с этим реализация алгоритмов второй группы требует больших затрат машинного времени, что делает данные алгоритмы практически непригодными для крупных вузов. Пространство распределения при этом является трехмерной конструкцией преподавателиклассывремя. В работах Готлиба и Гзимы 5, 6 используется матричный метод решения в трехмерном пространстве поиска с координатами преподаватель, классы, время, предполагающий в качестве исходных данных матрицу требований II, элементы которой Гу представляют целые числа, означающие, что преподаватель I, в классе Су должен проводить Гу часов в день. Расписание подучается в виде трехмерной конструкции Бк с элементами 5ук, которые могут принимать значения 0 или 1, в зависимости от того, должен или не должен преподаватель находиться в классе с в течение часа Существование такой конструкции предполагает удовлетворение ряда некоторых неравенств 6. Предложен алгоритм случайного поиска, на основании которого из всех возможных соотношений выбирается такое, которое удовлетворяет условиям однозначности нахождения преподавателя и класса и условиям недельных требований. При положительном исходе следующее соотношение выбирается также случайным образом, и выработанная последовательность операций приводит к конечному расписанию. При сбое поставленная задача считается неразрешимой. Алгоритм требует снабжения отдельных элементов матрицы признаками запрещений, и применим при ограниченном размере задачи. Создание аналогичной трехмерной конструкции проводится и в работе Шталкнехта 9, в которой задача составления расписания рассматривается как задана о назначениях. Составление матриц занятости для каждого учителя производится также исходя из возможности удовлетворения некоторых условий, разбитых по степени важности на две категории.