КОНЦЕПЦИЯ ПОСТРОЕНИЯ АВТОМАТИЗИРОВАННОЙ ИНФОРМАЦИОННОЙ СИСТЕМЫ СОСТАВЛЕНИЯ РАСПИСАНИЯ

Для решения многих прикладных задач не разработаны точные алгоритмы, позволяющие получить их оптимальное решение. На практике для решения таких задач используют эвристические алгоритмы [1, с. 19].

Одной из задач, для решения которой используется эвристический алгоритм, является задача составления расписания учебных занятий для ВУЗов.

Современные высшие учебные заведения остро нуждаются в создании системы, позволяющей планировать и составлять расписания занятий студентов и преподавателей, так как задача автоматизации работы расписаний до сих пор не реализована. Поэтому данная задача является актуальной и требующей решения.

Для реализации общих принципов математической модели и алгоритма решения задачи составления расписания учебных занятий необходимо спроектировать функциональную и информационную модели.

1. Функциональная модель

Для полной реализации функций автоматизированной информационной системы (АИС), учета взаимосвязей модулей системы по информации разработана функциональная модель на основе методологии IDEF3 и IDEF0. Метод IDEF3 целесообразно использовать для моделей процессов, в которых важно понять последовательность выполнения действий и взаимозависимости между ними. Основой модели IDEF3 служит сценарий процесса, который выделяет последовательность действий и подпроцессов анализируемой системы. Методология функционального моделирования IDEF0 – это технология описания системы в целом как множества взаимозависимых действий, или функций. Важно отметить функциональную направленность IDEF0 – функции системы исследуются независимо от объектов, которые обеспечивают их выполнение. «Функциональная» точка зрения позволяет четко отделить аспекты назначения системы от аспектов ее физической реализации. Наиболее часто IDEF0 применяется как технология исследования и проектирования систем на логическом уровне. По этой причине он, как правило, используется на ранних этапах разработки проекта. Результаты IDEF0 анализа применяются при проведении проектирования [2, с. 12].

На рисунке 1 показана модель процессов АИС, разработанная на основе методологии IDEF3. Система должна выполнять следующие функции:

1. Ввод сетки распределения учебных часов кафедры (подразумевается работа с данными о преподавателях, группах и аудиториях).

2. Учет студенческих потоков, групп, подгрупп.

3. Автоматическое составление расписания учебных занятий.

4. Формирование и редактирование расписания вручную.

5. Формирование расписания по группам, курсам, для аудиторий.

6. Формирование графика работы преподавателей, кафедр.

7. Экспорт расписания в MS Excel.

Общая модель АИС представлена на рисунке 2. Модель блока А2 «Формирование гиперграфа распределения нагрузки» ­­– на рисунке 3. Данные модели разработаны на основе методологии IDEF0.

Общую модель системы можно разбить на 5 основных блока:

1. Составление сетки учебных занятий.

2. Формирование базы данных (информационная модель).

3. Формирование математической модели распределения нагрузки.

4. Формирование расписания учебных занятий.

5. Назначение аудиторий.

При этом необходимо учитывать «жесткие» требования (ограничения), критерии оптимизации расписания, ограничения по аудиториям.

Рисунок 1 – Модель процессов АИС на основе методологии IDEF3

Рисунок 2 – Общая модель АИС

Блок «Формирование гиперграфа распределения нагрузки» включает в себя следующие этапы:

1. Создание гипервершин.

2. Формирование гиперребер для идентичных преподавателей.

3. Формирование гиперребер для идентичных групп.

4. Формирование гиперребер для идентичных аудиторий.

5. Добавление фиктивных вершин.

При этом необходимо учитывать ограничения по преподавателям, группам, аудиториям, а также пожелания преподавателей.

Рисунок 3 – Формирование гиперграфа распределения нагрузки

1. Информационная модель

Для реализации функций системы спроектируем структуру базы данных. Для этого используем методологию IDEF1Х. Информационная модель изображена на рисунке 4.

Рисунок 4 – Информационная модель системы

Цель моделирования данных состоит в обеспечении разработчика системы концептуальной схемой базы данных в форме одной модели или нескольких локальных моделей, которые относительно легко могут быть отображены в любую систему баз данных. Наиболее распространенным средством моделирования данных (предметной области) является модель «сущность-связь» (ERM). Базовыми понятиями ERM являются сущность, связь и атрибут [3, с. 27].

Сущность (Entity) – реальный, либо воображаемый объект, имеющий существенное значение для рассматриваемой предметной области. Связь (Relationship) – поименованная ассоциация между двумя сущностями, значимая для рассматриваемой предметной области. Связь – это ассоциация между сущностями, при которой каждый экземпляр одной сущности ассоциирован с произвольным (в том числе нулевым) количеством экземпляров второй сущности, и наоборот. Атрибут (Attribute) – любая характеристика сущности, значимая для рассматриваемой предметной области и предназначенная для квалификации, идентификации, классификации, количественной характеристики или выражения состояния сущности [4, с.88].

Методология моделирования данных IDEF1X, входящая в семейство стандартов IDEF, использует разновидность модели «сущность-связь». Диаграмма «сущность-связь» является самым высоким уровнем в модели данных и определяет набор сущностей и атрибутов проектируемой системы. Целью этой диаграммы является формирование общего взгляда на систему для ее дальнейшей детализации, предоставление информации администратору базы данных для создания эффективной структуры хранения, включающей в себя записи, формирующие базу данных. Модель IDEF1X должна помочь разработчикам выбрать структуру хранения данных и реализовать систему доступа к ним.

Основными объектами изучения предметной области стали: данные о преподавателях; данные о группах; данные об аудиториях; структура кафедр факультета; учебные группы (в том числе потоки, подгруппы); предметы (дисциплины); сетка занятий (на предстоящий семестр); «пары» (занятия); зависимости по виду занятий, по дисциплине; предпочтения; дни недели; вид занятия; желаемые аудитории; расписание.

Рассмотрим некоторые объекты подробнее.

Данные о преподавателях включают в себя: ФИО, дата рождения, возраст, семейное положение, адрес проживания, социальное положение, предыдущее место работы, владение иностранными языками, специальность, стаж работы, квалификация, ученое звание, ученая степень и тому подобные данные. Следует учесть, что интересы преподавателей, работающих по совместительству, имеют больший приоритет чем интересы преподавателей являющихся штатными работниками университета. То есть, в первую очередь следует заботиться о совместителях, при условии, что их интересы не противоречат и интересам студентов. Учитываются пожелания преподавателей, например, о наличии методического дня.

Данные об аудиториях содержат: название аудитории, тип аудитории, вместимость. Следует отметить для каких целей используется аудитория: для проведения лекционных занятий, практических, лабораторных либо это вообще спортивный зал. Необходимо указать наличие или отсутствие мультимедийного проектора, компьютеров (их количество), и тому подобное оборудование.

Сетка занятий – сетка распределения часов кафедры на определенный семестр (желаемые требования), в которой указываются следующие данные: наименование дисциплины, курс, количество групп, количество подгрупп, лекций, лабораторных, семинаров, практических занятий, количество часов в неделю, номер и название группы, преподаватели, которые предположительно будут вести данный предмет, номер желаемой аудитории.

Автоматизированная система должна позволять изменение периода планирования расписания (количество недель), учитывать, в какую смену проходят занятия и контролировать количество пар в день.

Зависимости по виду занятий и по дисциплине необходимы для обеспечения корректности расписания. С помощью данных зависимостей можно, например, запретить проводить три «пары» занятий по одному и тому же предмету в один день или обеспечить возможность проводить сдвоенные «пары» (для лабораторных занятий).

Атрибуты используются для хранения информации об объектах, представленных в базе данных. Каждый атрибут описывает некоторое свойство сущности. Атрибуты могут располагаться в любом порядке – независимо от их переупорядочивания сущность будет оставаться одной и той же, а потому иметь тот же смысл. Выделяются атрибуты сущностей, рассмотренные ниже.

1. Кафедры: название кафедры, название факультета.

2. Дисциплины: наименование, курс, вид занятия.

3. Преподаватели: фамилия, имя, отчество, должность, кафедра.

4. Желаемые аудитории: код аудитории, код занятия.

5. Сетка занятий: дисциплина, вид занятия, количество занятий, преподаватель, группа, подгруппа, аудитория, неделя 1, неделя 2, неделя 3, неделя 4.

6. Группы: наименование, курс, количество, количество подгрупп.

7. Расписание: неделя занятий, день недели, номер пары, занятие, группа, подгруппа, аудитория.

8. Пары: код пары, время проведения пары.

9. Аудитории: код аудитории, № аудитории, корпус, спкциализация, количество мест, наличие проектора, наличие компьютеров, наличие спецоборудования.

10. Вид занятия: код занятия, название вида занятия, часы лекций, часы практик, часы лабораторных занятий.

11. Форточки: преподаватель, неделя, день недели, пара.

12. Зависимости по виду занятий: занятие, код зависимости, главное значение.

13. Зависимости по дисциплине: занятие, код зависимости.

Выводы

Предложена функциональная модель системы. Данная модель основана на методологиях IDEF0, IDEF3. Спроектирована общая модель, модель блока формирования математической модели распределения нагрузки. Выделены функции системы. Разработана информационная модель системы на основе методологии IDEF1Х. Выделены основные сущности, описаны атрибуты.

Литература :

1. S.V. Baltak, Yu.N. Sotskov. Generation coursetimetabling on the basis of vertex graphcoloring. – 69 p.

2. Клеванский Н. Н. Моделирование стратегии формирования расписания занятий вуза средствами реляционной алгебры / Н.Н. Клеванский, Е.А. Мокарцова, С.А. Костин // Прикладные проблемы образовательной деятельности межвуз. сб. науч. тр. Воронеж: ВГПУ. – 2003. – С. 71-74.

3. Клеванский Н.Н. Приоритетность использования приближенных методов в составлении расписания занятий вуза / Н.Н. Клеванский, А.А. Пузанов // Моделирование и управление в сложных системах: сб. науч. ст. Саратов: СГТУ. – 2005. – С. 11-15.

4. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. – М.: Наука, 1975. – 270 с.

Научный руководитель:

к. ф.-м. наук, доцент Голубева Оксана Валерьевна.