Содержание к диссертации
ВВЕДЕНИЕ 5
ГЛАВА 1. ОБЗОР СРЕДСТВ И МЕТОДОВ ФОРМИРОВАНИЯ
УЧЕБНЫХ РАСПИСАНИЙ 13
1.1. Основные требования к учебному расписанию и к способам
его составления 13
Обзор программных средств формирования расписаний для различных учебных заведений. 20
Обзор и классификация методов составления учебных расписаний 36
1.4. Основные выводы и результаты главы 47
ГЛАВА 2. СОСТАВ И СТРУКТУРА АВТОМАТИЗИРОВАННОЙ
ИНФОРМАЦИОННОЙ СИСТЕМЫ "РАСПИСАНИЕ ВУЗА" 49
2.1. Функциональные подсистемы системы "Расписание ВУЗа"
Существующий порядок формирования учебного расписания в ВУЗе 50
Характеристика функциональных подсистем системы "Расписание ВУЗа" 51
2.2. Задача формирования календарного учебного расписания
ВУЗа 53
Содержательная постановка задачи 53
Формализация задачи 55
Постановки задач формирования расписаний занятий
в ВУЗе 58
Понятия о iVP-полноте и М>-трудности комбинаторных задач 60
Доказательство NP-попноты и iVP-трудности задач
формирования учебных расписаний в ВУЗе 64
2.2.5.1 Общие сведения о методах доказательства
jVP-полноты. 64
2.2.5.2 Доказательство Л^Р-полноты и JVP-трудности 66
задач формирования учебных расписаний
2.3. Организация хранения данных системы "Расписание ВУЗа". 67
2.3.1. Состав данных системы "Расписание ВУЗа". 67
Обзор известных моделей представления данных 68
Модели данных системы "Расписание ВУЗа" 75
Реляционные модели данных в системе "Расписание ВУЗа" 75
Многомерные модели данных в системе "Расписание ВУЗа" 76
2.3.3.3 Слабоструктурированные модели данных
в системе "Расписание ВУЗа". 80
2.4. Основные выводы и результаты главы 85
ГЛАВА 3. АЛГОРИТМЫ РЕШЕНРІЯ ЗАДАЧ СОСТАВЛЕНИЯ
УЧЕБНЫХ РАСПИСАНИЙ ВУЗА 88
Обзор подходов к решению комбинаторных оптимизационных задач - 88
Обоснование и общее описание метода решения задачи формирования учебного расписания ВУЗа 94
Алгоритмы формирования календарного учебного расписания в составе информационной системы "Расписание ВУЗа" 105
3.3.1 Алгоритмы решения задач подсистемы "Формирова
ние баз данных и базы локальных алгоритмов" 105
3.3.2 Алгоритмы решения задач подсистемы "Подготовка ин
формации для составления календарных расписаний" 106
3.3.3 Генерация трехмерных гиперкубов расписаний. 108
3.3.4. Ввод ограничений -"запретов". 109
Ручной режим включения дисциплин в расписание 110
Декомпозиция исходной задачи на подзадачи меньшего размера (кластеры). 111
Настройка алгоритма формирования учебного расписания под требования конкретного ВУЗа 113
3.3.8 Алгоритм автоматического формирования календар
ного учебного расписания 115
3.3.9 Диалоговая доработка сформированного расписания 121
3.4. Основные выводы и результаты главы 123
ГЛАВА 4 ПРОГРАММНЫЙ КОМПЛЕКС "РАСПИСАНИЕ ВУЗА" 125
Функциональное назначение 125
Выбор и краткое описание средства разработки 126
Основные компоненты программного комплекса 131
Описание интерфейса программного комплекса 133
Основные выводы и результаты главы 143
ЗАКЛЮЧЕНИЕ 144
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 148
ПРИЛОЖЕНИЯ 161
Приложение 1. Список печатных работ по теме диссертации. 161
Приложение 2. Диаграммы бизнес-процессов формирования 163
учебного расписания в ВУЗе
Приложение 3. Состав функциональных задач системы 173
"Расписание ВУЗа"
Приложение 4. Диаграммы ER-типов данных системы 174
"Расписание ВУЗа"
Приложение 5. Структуры баз данных системы "Расписание 176
ВУЗа"
Приложение 6. Схемы представления и хранения гиперкубов рас- 178
писаний "Преподаватели", "Группы", "Аудитории"
Приложение 7. Перечень базовых алгоритмов включения в 181
учебное расписание "блоков" размеров 1,2,3,4.
Приложение 8. Перечень локальных алгоритмов включения в 184
учебное расписание "блоков" размеров 1,2,3,4.
Приложение 9 Структуры некоторых таблиц базы данных "Рас- 193
писание ВУЗа"
Приложение 10. Документы, подтверждающие внедрение. 196
Введение к работе
Актуальность работы. Одной из важнейших проблем качественной организации учебного процесса в высшем учебном заведении (ВУЗе) является задача формирования качественного учебного расписания. Эта задача является основной в деятельности диспетчерской службы ВУЗа. Качественно составленное расписания должно обеспечить в очередном семестре равномерную загрузку студенческих групп и профессорско-преподавательского состава.
Следует отметить, что на период 2001-2010 года правительством РФ принята "Концепция модернизации российского образования", главной целью которой является обеспечение современного качества образования. Согласно принятой "Концепции..." в сфере образования проводятся изменения, усложняющие учебный распорядок образовательных учреждений и устанавливающие более жесткие требования к расписанию. Расписание должно учитывать большее количество ограничений различного вида, что связано, например, с введением модульно- рейтинговой системы образования. От расписания требуется также оптимизация учебной, психологической и физической нагрузки студентов и прочие новшества.
В частности, это выражается в потребности учитывать действующие санитарно эпидемиологические правила и нормы (СаНПиН) [41], деление студенческих групп на подгруппы, наличие преподавателей-совместителей и многое другое. При составлении расписания диспетчеру необходимо учитывать дидактические требования по организации учебного процесса, указания администрации по распределению аудиторного фонда (и иных ресурсов, необходимых для реализации учебного процесса), а также личные пожелания преподавателей и студенческих групп к составлению расписания. Помимо этого, специфика конкретного ВУЗа отражается в задаче составления расписания в виде специфичных целей
и ограничений. В результате всего вышеизложенного, задача составления расписания становится очень сложной для решения вручную. В настоящее время при актуальности вопроса качества образовательных услуг и требований экономии ресурсов на практике востребовано не только составление некоторого "чернового" варианта расписания, но и получение оптимального (с точки зрения введенных критериев и имеющихся ограничений) либо близкого к оптимальному (по некоторой мере) расписания. И если составление расписания вручную является трудной и затратной по времени задачей, то решение задачи оптимизации учебного расписания вручную практически не реализуемо.
Несмотря на большой выбор автоматизированных систем составления расписания и способов учета ограничений в них, на практике нередкой является ситуация, когда выбранная система не имеет возможности учесть конкретное ограничение, важное в текущем состоянии при составлении расписания в ВУЗе. Поэтому в настоящее время учебное расписание во многих ВУЗах по прежнему формируется вручную.
При выборе средств автоматизации учебного расписания следует также учитывать размерность реальной задачи составления расписания, которая может быть весьма велика даже для небольшого ВУЗа. Часть имеющихся разработок по составлению расписания в силу используемого алгоритма имеют ограничения на размерность решаемой задачи, и поэтому могут оказаться непригодными. Большинство реальных задач составления учебного расписания, кроме этого, являются TVP-трудными [54]. Для подобных задач, согласно теории сложности [16], не существует алгоритма с полиномиальной оценкой сложности, а число вариантов для перебора растет экспоненциально с ростом длины вектора неизвестных.
Многочисленные попытки автоматизировать процесс формирования учебного расписания ВУЗа успехов пока не принесли. Исследования в
этой области продолжаются, что говорит об актуальности данного направления.
Таким образом, актуальной является проблема создания информационной системы "Расписание ВУЗа", центральной задачей которой является оптимизационная задача формирования учебного расписания, учитывающего требования, изложенные в "Концепции модернизации российского образования" и, в частности, требования действующих СаНПиН. Кроме этой задачи в рамках подсистемы "Расписание ВУЗа" необходимо решение ряда задач по вводу и размещению на машинных носителях всей информации, необходимой для формирования расписания, и ряда задач по формированию выходных документов, необходимых для качественной организации учебного процесса в высшем учебном заведении.
Объектом исследования данной работы является процесс составления учебного расписания для ВУЗов. Предметом исследования является автоматизация процесса составления учебного расписания с учетом предпочтений студентов и преподавателей и требований СаНПиН.
Целью данной работы является разработка автоматизированной системы "Расписание ВУЗа", центральным элементом которой является задача формирования оптимального учебного расписания ВУЗа, удовлетворяющего современным образовательным требованиям (в частности, требованиям СаНПиН).
К задачам исследования относятся:
Исследование функциональных возможностей разработанных ранее автоматизированных систем формирования учебных расписаний.
Анализ постановок, методов и алгоритмов решения задач формирования учебных расписаний.
3) Проектирование структуры автоматизированной системы "Расписание ВУЗа". Декомпозиция системы на функциональные и обеспечивающие подсистемы.
Содержательная и формализованная постановки задачи "Автоматизированное формирование оптимального учебного расписания ВУЗа"
Разработка логической и физической моделей данных системы "Расписание ВУЗа".
Разработка алгоритмов решения функциональных задач системы "Расписание ВУЗа"
Создание программного комплекса, реализующего разработанные методы решения функциональных задач системы "Расписание ВУЗа" и обеспечивающего создание и ведение информационной базы данных системы "Расписание ВУЗа".
Методологической основой исследования явились общие законы, принципы и методы системного подхода и математического моделирования, теория реляционных баз данных, методы проектирования баз данных, методы календарного планирования, технология объектно-ориентированного программирования, принципы построения систем, ориентированных на анализ данных.
Научная новизна. Новыми в работе являются:
структура автоматизированной системы "Расписание ВУЗа" с выделением функциональных и обеспечивающих подсистем;
модель процесса формирования оптимального учебного расписания ВУЗа в терминах методологии календарного планирования;
математическая модель задачи "Автоматизированное формирование оптимального учебного расписания ВУЗа";
- логическая и физическая модели данных системы "Расписание ВУЗа";
- эвристический алгоритм решения оптимизационной задачи формирование оптимального учебного расписания ВУЗа;
- программный комплекс, обеспечивающий решение в автоматизированном режиме всех функциональных задач, необходимых для организации учебного процесса в ВУЗе на стадии формирования учебного расписания.
Теоретическая ценность работы заключается в исследовании с единых позиций в рамках одной системы всех задач, связанных с формированием учебного расписания ВУЗа, в применении для решения задачи формирования оптимального учебного расписания ВУЗа спискового жадного алгоритма.
Практическая ценность работы заключается в том, что с помощью созданного программного комплекса становится возможной реальная работа всех служб ВУЗа (деканатов, кафедр, диспетчерской службы) по формированию в автоматизированном режиме качественных учебных расписаний. Имеется возможность настройки созданного программного комплекса для функционирования в любом ВУЗе.
Внедрение результатов работы. С использованием разработанного программного комплекса "Расписание ВУЗа" осуществлялось формирование учебных расписаний в двух ВУЗах г.Красноярске (акты о внедрении представлены в приложении 10). Предложенные в работе методы создания баз данных и хранилищ данных внедрены в учебный процесс в СибГТУ и КрасГАУ. С использованием этих методов выполнялись лабораторные и курсовые работы по дисциплинам: "Структуры и алгоритмы обработки данных", "Базы данных", "Проектирование информационных систем".
На защиту выносится: - математическая модель задачи "Автоматизированное формирование оптимального учебного расписания ВУЗа";
- логическая и физическая модели данных системы "Расписание
ВУЗа";
- эвристический алгоритм решения оптимизационной задачи форми
рование оптимального учебного расписания ВУЗа.
Апробация работы. Основные результаты работы докладывались на:
XL Международной конференции "Студент и научно-технический прогресс" (Новосибирск, 2002);
Межвузовской научной конференции "Информатика и информационные технологии" (Красноярск, 2002);
Научном фестивале студентов, аспирантов и молодых ученых "Молодежь и наука - третье тысячелетие" (Красноярск. 2003);
III Всесибирском конгрессе женщин-математиков (в день рождения Софьи Васильевны Ковалевской) (Красноярск, 2004);
Всероссийской научно-технической конференции "Лесной и химический комплексы - проблемы и решения (экологические аспекты)" (Красноярск, 2004);
Межвузовской научной конференции "Информатика и информационные технологии" (Красноярск, 2004);
Девятой Всероссийской научно-практической конференции "Проблемы информатизации региона: ПИР-2005" (Красноярск, 11-12 октября 2005 г.);
IV Всесибирском конгрессе женщин-математиков (в день рождения Софьи Васильевны Ковалевской) (Красноярск, 2006);
- Всероссийской научной конференции молодых ученых "Наука.
Технологии. Инновации" (Новосибирск, 2006).
Публикации. По теме диссертации опубликовано 13 работ. Список этих работ представлен в "Приложении 1".
Структура и содержание работы. Диссертация состоит из введения, пяти глав, заключения, библиографического списка литературы из 131 наименования и десяти приложений.
В первой главе сформулированы основные требования к учебному расписанию и к способам его составления. Отмечено, что при составлении учебного расписания нужно учитывать разные критерии оптимальности и большое число ограничений различного вида. Конкретизированы требования к ручному, автоматическому и интерактивному режимам формирования учебного расписания. Выполнен обзор и проведен анализ наиболее популярных программных комплексов формирования расписаний для различных учебных заведений. Выяснено, что в полной мере ни один этих программных комплексов не отвечает требованиям, предъявляемым к системам автоматического формирования учебного расписания ВУЗа. Выполнен обзор и проведена классификация методов составления учебных расписаний.
Во второй главе выполнен анализ существующего порядка формирования учебного расписания в ВУЗе. Предложена методология проектирования информационной системы "Расписание ВУЗа", основу которой составляет системный подход. Определены состав и содержание функциональных и обеспечивающие подсистемы системы "Расписание ВУЗа". Сформулированы все функциональные задачи системы "Расписание ВУЗа". Построена математическая модель центральной функциональной задачи информационной системы "Расписание ВУЗа" - задачи формирования календарного учебного расписания. Доказано, что сформулированная оптимизационная задача является Л^Р-трудной.
В третьей главе выявлен состав информации, циркулирующей в информационной системе "Расписание ВУЗа", и дана ее краткая характеристика. Предложена модель хранения данных системы "Расписание ВУЗа".
В составе хранилища данных системы "Расписание ВУЗа" выделено три типа моделей: реляционную, многомерную и слабоструктурированную. Предложены методы проектирования баз данных всех трех типов моделей. Введены понятия: базовый и локальный алгоритмы включения "блоков" дисциплин в учебное расписание. Выведены формулы для вычисления возможного числа этих алгоритмов.
В четвертой главе содержится обоснование и изложение нового алгоритма решения задачи формирования учебного расписания ВУЗа. Его можно охарактеризовать так: приближенный, гибридный, жадный списковый алгоритм с использованием последовательных, кластерных, эвристических методов и методов распространения ограничений. Разработанный алгоритм включает в ряд этапов, для реализации каждого из которых предложены соответствующие алгоритмы. Реализован режим настройки алгоритма формирования учебного расписания под требования конкретного ВУЗа.
В пятой главе содержится краткое описание разработанного программного комплекса, с использованием которого решаются все функциональные задачи информационной системы "Расписание ВУЗа".
