автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Средства моделирования и численные методы в задаче формирования начального расписания занятий

На правах рукописи

МАКАРЦОВА Екатерина Алексеевна

СРЕДСТВА МОДЕЛИРОВАНИЯ И ЧИСЛЕННЫЕ МЕТОДЫ В ЗАДАЧЕ ФОРМИРОВАНИЯ НАЧАЛЬНОГО РАСПИСАНИЯ

ЗАНЯТИЙ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Саратов 2006

Диссертация выполнена в ГОУ ВПО «Саратовский государственный технический университет»

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

кандидат технических наук, доцент Клеванский Николай Николаевич

Официальные оппоненты

доктор технических наук, профессор Львов Алексей Арленович доктор технических наук, профессор Кузнецов Валентин Николаевич

Ведущая организация

Саратовская государственная академия права

Защита диссертации состоится 21 апреля 2006 года в 1300 на заседании диссертационного совета Д 212.242.08 при Саратовском государственном техническом университете по адресу: 410054, г. Саратов, ул. Политехническая, 77, корп. 1, ауд. 319.

С диссертацией можно ознакомиться в научно-технической библиотеке Саратовского государственного технического университета.

Автореферат разослан «20» марта 2006 года.

Ученый секретарь диссертационного совета

Большаков А.А.

ОСНОВНЫЕ ПОЛОЖЕНИЯ

Актуальность исследования. Информатизация процессов управления деятельностью высшего учебного заведения отнесена к одному из основных направлений «Концепции информатизации высшего образования РФ». Информационные системы различной степени интеграции созданы для управления учебным процессом. В большинстве случаев они представляют собой совокупность разрозненных подсистем, каждая из которых решает свою отдельную задачу, используя локальную базу данных (БД).

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

Составление расписания занятий, являясь итерационным процессом, состоит вместе с тем из двух основных этапов. На первом этапе формируется начальное расписание на основе исходных данных об аудиторной нагрузке преподавателей. Основная проблема здесь связана со стратегией включения в расписание всей нагрузки. Расписание должно быть непротиворечивым и, по возможности, оптимальным. Непротиворечивость связана с соблюдением обязательных ограничений: у академической группы или преподавателя в одно и то же время может быть только одно занятие, отсутствие «окон» в занятиях студентов и др. Оптимальность расписания обеспечивается соблюдением желательных ограничений. Например, минимизация количества «окон» у преподавателей и/или равномерность распределения занятий студентов по дням недели и др. Всё это определяет сложность формирования начального расписания, а также его существенную значимость для следующего этапа. На втором этапе производится глобальная корректировка расписания с целью его оптимизации. Методы глобальной корректировки расписания рассмотрены в диссертации Костина С.А. «Модели и методы многокритериальной оптимизации начального расписания занятий».

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

"ЛЬ ИДЯ

аил ¡¡о; скд

С.-Петербург

ОЭ актМй

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

В составлении начального расписания занятий используются два подхода. В первом первоначально распределяются два ресурса - контингент учащихся и учебные аудитории, то есть формируется «сетка» занятий, заполняемая затем занятиями конкретных преподавателей. Во втором подходе начальное расписание формируется на основе одновременного распределения всех трех ресурсов (учащиеся, преподаватели, аудитории).

Уменьшение числа распределяемых ресурсов в первом подходе (работы Ерунова В.П., Морковина И.Н.) упрощает алгоритмы решения, кроме того, возможны минимизация количества требуемых учебных аудиторий и обеспечение равномерности загрузки академических групп. Оптимизация работы преподавателей при этом затруднена.

Второй подход (работы Давыдова C.B., Лагоша Б.А., Петропавловской A.B., Пантелеева Е.Р.) требует более сложных и трудоемких в вычислительном плане алгоритмов, но позволяет оптимизировать загруженность трех основных ресурсов, благодаря чему он был принят к использованию в данной работе.

Практически не исследованными при составлении начального расписания занятий являются:

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

- подходы с использованием рассчитываемых на каждой итерации приоритетов не включенных в расписание элементов входного множества, благодаря чему возможно автоматическое управление выбором элементов с наиболее загруженными ресурсами и их включением в формируемое расписание;

- вопросы создания средств генерации тестовых заданий для задач составления расписания занятий. Использование этих средств обеспечит отладку и анализ процессов составления начального расписания занятий.

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

К основным задачам работы, обеспечивающим достижение указанной цели, отнесены:

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

- реализация алгоритмов составления начального расписания занятий вуза;

- разработка средств генерации тестовых заданий;

- исследование характеристик разработанных методов и алгоритмов

Объект исследования - теория расписаний.

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

Методологическая и теоретическая основа исследования - в диссертационной работе использован математический аппарат теории множеств, исследования операций, теории графов и целочисленного линейного программирования, а также общей теории расписаний.

В работе использованы методы системного анализа, статистики, оптимизации, компьютерной графики.

Научная новизна исследования состоит в следующем:

- разработана модель расписания занятий на основе учебных поручений в составе общей модели управления учебным процессом вуза;

- предложен метод решения задачи формирования начального расписания занятий, отличающийся от известных решений:

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

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

На защиту выносятся:

- математическая модель и формализованная постановка задачи составления начального расписания занятий вуза, в которой учитываются требования интегрированной системы управления учебным процессом вуза;

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

риев загруженности основных ресурсов - академических групп, преподавателей, учебных аудиторий и многокритериальной оценки для выбора времени и места проведения занятий;

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

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

Апробация результатов исследования - предложенные в диссертации модели, методы и алгоритмы были использованы при разработке и практической реализации информационных систем управления учебным процессом вуза. Система прошла внедрение в Саратовском государственном техническом университете и Саратовской государственной академии права и продолжает совершенствоваться.

Основные результаты работы докладывались на 2-й Всероссийской научной конференции молодых ученых и аспирантов (г.Таганрог, 1999), XI, XII, XIII и XV международных конференциях-выставках: «Информационные технологии в образовании» (г. Москва, 2001, 2002, 2003 и 2005).

Публикации. По теме диссертации опубликовано 8 работ.

Объем работы. Диссертационная работа состоит из введения, четырех глав и заключения, изложенных на 125 страницах машинописного текста, 33 рисунков, 24 таблиц, списка использованной литературы.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Показано, что:

- имеющиеся в настоящее время системы управления учебным процессом, как правило, имеют узкую направленность, так как автоматизируется работа одного из подразделений (кафедры, факультета и т.д.). Базы данных подсистем разобщены. Подсистема формирования расписания, как правило, автономна, что требует ввода больших объемов исходной информации. Реализация подсистем подготовки расписания занятий в

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

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

Во второй главе рассматривается общая постановка задачи состав-

РихД.Документы управления учебным процессом вуза ления расписания занятий в составе интегрированной системы управления

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

Множественно-графовая интерпретация модели исследования включает следующее.

Множество академических групп (7. Ас = {аС1, аж2, ак3, аС4} - атрибуты (асI - количество запланированных «пар» занятий группы за две недели; аСг ~ количество распределенных в расписание «пар» занятий группы; асз -критерий загруженности группы; аа4 - количество студентов группы).

„ _ «а\-«аг ~ 12* N-0^

где N - количество регламентированных для расписания «пар» занятий в день.

Множество потоков р групп для проведения лекционных занятий. Множество подгрупп Q, на которые могут быть разделены академические группы для проведения некоторых занятий (например, практические занятия по иностранному языку или лабораторные занятия).

Гиперграф структуры групп и потоков С = \/3,Р}, а гиперграф структуры групп и подгрупп А = {(<3,2)}. На рис.2 оба гиперграфа представлены трехдольным графом для академических групп трех специальностей. Две специальности относятся к одному направлению. Каждая группа в рассматриваемом случае содержит две подгруппы для проведения лабораторных занятий.

Множество преподавателей Т, разделяемое на подмножества преподавателей кафедр. Ат = {ап,атг,ап} - атрибуты (аТ1 -количество запланированных «пар» занятий преподавателя за две недели; а-п - количество распределенных в расписании «пар» занятий преподавателя; атз -критерий загруженности преподавателя).

_ ат\~ат1 . " ~\2*И-атг

Рассчитываемая и распределяемая учебная нагрузка включает проведение занятий:

- одной группы с одним преподавателем;

- нескольких групп (потока) с одним преподавателем;

Группы Подгруппы в

я ег

Рие.2.Граф структуры контингента студентов

И И

- одной группы с несколькими преподавателями подгрупп.

Из трех сущностей студенческого контингента (ПОТОК, ГРУППА, ПОДГРУППА) только одна (ГРУППА) является устойчивым образованием. Поэтому гиперграф индивидуальной нагрузки определен как Н - {в,Т,1н,Ан}, где 1Н -чгацидентор, порождающий множество пар I = {(в^Уи (яД g ев, 1 е т}. Инцидентность между ^и » означает, что занятие Ь в академической группе g проводит преподаватель I. А-н = {ат>ан2>ан1'ат>ан>} - атрибуты Ь (аН] - поток группы, включая пустой поток; ан2 - подгруппа группы, включая пустую подгруппу; анз - дисциплина; аН4 - вид занятия; анз - количество часов занятий за две недели). Гиперграфы Н содержат неизменяемые в течение года (по крайней мере, семестра) связи между элементами множеств би Ги являются подграфами гиперграфов учебной нагрузки кафедр. На рис.3 гиперграф Я представлен многодольным графом, множество вершин которого содержит три непересекающихся множества (7, Ь и Г.

практическое занятие

лекция

лабораторное занятие

Рис.З.Граф индивидуальной учебной нагрузки преподавателей

Множество аудиторий Л. Ал = {дт,ап ,яяз,я„4} - атрибуты {ащ - количество запланированных «пар» занятий в аудитории за две недели; аю - количество распределенных в расписании «пар» занятий в аудитории; а« - критерий загруженности аудитории; аЯ4 - атрибут, представляющий вместимость аудитории).

д = Я181 ~аК2

"3 12*№-ак1

Гиперграф учебных поручений (/ = {£,Л, 11/), где ¡и - инцидентор, порождающий множество пар М = {(/,г)|/(,(/,г), / е I, г е я}. Инцидентность между /иг означает, что поручение М для занятия I содержит требуемую аудиторию г или «пустую» аудиторию, вместо которой необходимо распределить подходящую при составлении расписания занятий. В реляцион-

ном представлении модели исследования (рис.4) гиперграфу 1} соответствует сущность НАГРУЗКА.

Рис.4 .Реляционное представление модели исследования

Для моделирования временных сущностей введено множество тайм-слотов V, элементы которого включают атрибуты учебного дня, «пары» и признака недели.

Гиперграф расписания е = {m,v,ie}, где /£ - инцидентор, порождающий множество учебных «пар» {(m,v)|/£(w,v), те М, veV}.

В работе представлен и исследован эвристический алгоритм преобразования гиперграфа U в гиперграф Е.

Гиперграф учета загрузки групп X = ÍG. £>. /,}. где Iz - инцидентор, порождающий множество пар Zg = {(g, d\lz (g, d\ geG, d e d}. A7 ={aZÍ,an} - атрибуты Zg (az¡ - количество «пар» группы g в учебный день d; aZ2 - разница количеств «пар» группы g в учебный день d для двух недель расписания). Аналогичным образом определены гиперграфы учета загрузки преподавателей и аудиторий, необходимые для интенсификации процесса формирования начального расписания занятий.

Реляционное представление модели исследования показано в виде схемы фрагмента базы данных в нотации унифицированного языка моделирования UML. Отношение НАГРУЗКД содержит учебные поручения преподавателей кафедр для проведения занятий с академическими группами. В зависимости от студенческого контингента на проводимом занятии в

учебном поручении может присутствовать информация о потоке или подгруппе (в виде первичных ключей соответствующих сущностей). Каждому учебному поручению (одному кортежу в отношении НАГРУЗКА) должно соответствовать одно занятие (один кортеж в отношении ЗАНЯТИЕ).

Формирование начального расписания занятий завершено, если каждому учебному поручению поставлены в соответствие:

- время — день недели, «пара» академических часов, признак одной из двух возможных недель занятий;

- место - требуемая по учебному поручению или выбираемая аудитория.

На рис.5 в нотации ЦМЬ показана принципиальная схема метода формирования начального расписания занятий. Преобразование информации об учебных поручениях (отношение НАГРУЗКА) в занятия (отношение ЗАНЯТИЕ) представлено в виде диаграммы деятельностей. В качестве исходных данных используются учебные поручения. На каждом шаге осуществляется выбор наиболее «загруженного» поручения, для чего используется функция выбора. В зависимости от типа занятия выбранного поручения на основе функции оценки расписания определяются время и место проведения. После этого осуществляется преобразование каждого

С

с

Функция выбора учебного поручения

Функция оценки расписания

Ж

1

Выбор учебного поручения

>

Выбор Бремени и места\ проведения занятия )

НАГРУЗКА

(Преобразование _

поручения в заилив }

I

ЗАНЯТИЕ

Рис.5.Метод формирования начального расписания

учебного поручения в занятие.

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

Функция выбора рассчитывается для каждого не включенного в расписание учебного поручения. Функция является мультипликативным критерием загруженности основных ресурсов - групп, преподавателей и аудиторий, а также потоков и подгрупп. То есть, мультипликативный критерий учитывает загруженность всех пяти параметров учебного поручения. Загруженность потоков и подгрупп каждого поручения определяется в начальной фазе и остается неизменной. Загруженность групп, преподавате-

лей и аудиторий переопределяется для каждого поручения на каждой итерации.

В разработанном на базе предложенного метода алгоритме выбор времени и места проведения занятия основан на обеспечении равномерности расписания по следующим параметрам:

- общему количеству занятий для двух различных недель расписания;

- количеству занятий каждой академической группы для двух различных ' недель расписания;

- количеству занятий каждой академической группы в каждый день для двух различных недель расписания.

В связи с этим, завершение преобразования каждого учебного поручения в занятие в зависимости от его вида сопровождается:

- увеличением текущего количества расставленных в расписании занятий группы в выбранный день на 1;

- переопределением текущего признака превалирования занятий одной из двух недель для группы в выбранный день;

- увеличением текущего количества расставленных в расписании занятий преподавателя на 1 и переопределением его приоритета занятости;

- увеличением текущего количества расставленных в расписании занятий группы на 1 и переопределением ее приоритета занятости;

- переопределением признака превалирования занятий для всего сформированного расписания.

Алгоритм реализован на базе реляционных операторов и операций над множествами.

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

Исходная информация для составления расписания может быть охарактеризована двумя группами критериев - внешних, количественных, дающих общее представление об информации, и детализированных, позволяющих качественную оценку. Любое занятие, относящееся к аудиторной учебной нагрузке, характеризуется тремя распределяемыми ресурса- » ми: студентами, преподавателями и аудиториями.

В общем случае, студенты характеризуются своей принадлежностью к академической группе специальности или направления (при отсутствии "

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

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

Исходя из тех же соображений, к внешним, количественным критериям аудиторий относятся их количества и их распределение по принадлежности к кафедрам и вместимости. Более значимыми являются количественные распределения аудиторий по вместимости.

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

Таблица 1

Количества групп специальностей, направлений и курсов_

Направление Направ 1 Направ 2 Направ 3 Направ 4

Специальность Спец 1 Спец 2 Спец 3 Спец 4 Спец 5

Групп курса 2 3 2 2 1

факультета 10 15 10 10 5

Для всех групп тестового задания недельная аудиторная нагрузка составляет 27 часов, из которых 14 - лекции, 5 и 8 соответственно лабораторные и практические занятия.

Для дисциплин тестового задания установлены следующие ограничения:

- дисциплины циклов гуманитарных и социально-экономических дисциплин (ГСЭ) приняты идентичными для всех пяти учебных планов;

- дисциплины циклов специальных дисциплин (СД) приняты различными для различных специальностей;

- дисциплины циклов математических и естественно-научных дисциплин (ЕН) и общепрофессиональных дисциплин (ОПД) приняты различными для различных направлений.

В результате на соответствующих курсах создаются два потока из пяти групп для чтения лекций цикла ГСЭ. Для дисциплин цикла СД на каждом курсе создаются 5 потоков из групп одной специальности (потоки из одной, двух и трех групп).' Для дисциплин циклов ЕН и ОПД на каждом курсе создаются четыре потока из групп одного направления (потоки из одной, двух, трех и четырех групп).

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

нагрузки циклов дисциплин по семестрам (курсам), приняты одинаковыми (рис.6).

24

9 18

12

я

п м 6

9

а

§ 24

1 18

¡£ 12

6

гсэ

ОВД

у к*.

л Ск к

12 3 4 Курсы обучали

ЕН

к^

1 N к.

сд У

л у

у -X к"

2 3 4 Курсы обучения

Рис.6.Аудиторная нагрузка тестовых заданий для циклов и курсов

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

Все дисциплины учебных планов закреплены за кафедрами, преподаватели которых осуществляют их проведение. Лабораторные занятия проводятся в специальных лабораториях соответствующих кафедр.

Таблица 2

Распределение преподавателей, аудиторий и нагрузки в тестовом задании

Кафедра Количества преподавателей/лабораторий Аудиторная недельная нагрузка в часах

лекции практ. занятия лабор.занятия

ГСЭ 10/ 24 120

ЕН 22/3 60 70 140

Спец 1 15/2 43 42 72

Спец 2 20/3 43 63 108

Спец 3 14/2 32 44 68

Спец 4 14/2 32 40 76

Спец 5 9/1 43 21 36

Всего: 104/13 277 400 500

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

1 16 I 12 О е в- 8 о 8 4 а>

•

•

• •

| 4 8 12 16 20 м Часы аудиторной нагрузки в неделю

Рис.7.Распределение нагрузки между преподавателями:

— средни нагрузка преподавателей

В четвертой главе проанализированы полученные варианты расписаний, результаты вычислительных экспериментов.

В начальной стадии разработки данный алгоритм реализовы-вался для различных количеств аудиторий для лекционных и практических занятий. Минимальное количество таких аудиторий, для которых было сформировано расписание - 17. При этом количество аудиторий для лабораторных работ остается постоянным.

Для тестового задания был проведен ряд расчетов с различными количествами аудиторий для

лекционных и практических занятий в интервале от 17 до 27. Полученные данные позволяют оценить влияние количества лекционных аудиторий на основные распределяемые ресурсы (группы, преподавателей, аудитории).

На рис.8,а представлены характеристики учебных дней групп. Увеличение количества аудиторий приводит к значительному уменьшению количества дней, в которые группы занимаются 1 или 4 «пары» и увеличению дней с 2 «парами».

Рис.8, б показывает, что с увеличением количества лекционных аудиторий количество групп, занимающихся на второй «паре», растет, тогда как на первой «паре» это количество меняется незначительно. Количество групп, занимающихся на 3-й и 4-й «парах», снижается, но с увеличением количества аудиторий более 20 практически не меняется. На рис.8, виг представлены характеристики распределения групп по разности и сумме количества «пар» в день разных недель соответственно.

Следует отметить, что количество дней с одинаковым количеством «пар» равномерно увеличивается с увеличением количества лекционных аудиторий, количество дней с разностью в 1 «пару» растет с увеличением количества аудиторий до 20, затем снижается при увеличении аудиторий до 24 и далее практически не изменяется. Количество дней с разностью в 2 пары равномерно снижается, а с разностью в 3 пары практически не изменяется.

Количество дней занятий за 2 недели с суммарным количеством «пар» в день разных недель 4 и 5 равномерно увеличивается с ростом количества лекционных аудиторий, количество дней с суммарными значениями тех же параметров, равных 2,3,6,7,8, снижается.

1

1

1

1

т

1

1 . 1 1

?

18 20 22 24 26

2 "тары" Г

& эд

3 "пары"

1 12

1 "пара." 4 "пары" 6)

'2-я "пара" '1-я "пара" '3-я "пара"

■I 4-я "пара"

20 22 24 26

18 20

22

24 26

±2 ±3

вч Количество аудиторий для лекций и практических занятий

:

8 18 20 22 24 26 Количество аудиторий для лекций г' и практических занятий

З+б 2+7+8

Рис.8.Распределение ресурса "ГРУППЫ": а - по учебным дням; б - по "парам"; в и г - по разности и сумме количества "пар" в день разных недель

Увеличение количества аудиторий приводит к увеличению количества дней с суммарным количеством «пар» в день равным 4 и 5 (за обе недели), и разностью в «парах» 0 и 1 , т.е. увеличению количества дней с 2-3 «парами» в день. И уменьшению дней со слишком маленьким или, наоборот, большим количеством «пар» у групп.

В заключении сформулированы основные результаты и выводы

диссертационной работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Предложена математическая модель расписания занятий в составе общей модели управления учебным процессом вуза.

2. Разработан метод составления начального расписания занятий вуза на основе многокритериальной выборки с использованием переопределяемых критериев загруженности основных ресурсов и многокритериальной оценки для выбора места и времени проведения занятий.

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

4. Разработаны средства генерации тестовых заданий.

5. Проанализированы характеристики разработанных методов и алгоритмов.

Основные публикации по теме диссертации

1- Макарцова Е.А. Информационно-управляющая система учебным процессом вуза/ H.H. Клеванский, Е.А. Макарцова // Новые информационные технологии. Разработка и аспекты применения: сб тез. 2-й Всерос науч. конф. мол. уч. и асп. /Таганрог, гос. радиотехн. ун-т. Таганрог, 1999. С. 23-24.

2. Макарцова Е.А. Информационная поддержка управления учебной деятельностью вуза/ H.H. Клеванский, Е.А. Макарцова // Информационные технологии в образовании: сб. материалов, межвуз. науч.-метод. конф./ Сарат. гос. техн. ун-т. Саратов, 2000. С. 4- 5.

3. Макарцова Е.А. Формирование расписания с использованием динамических критериев загруженности/ H.H. Клеванский, Е.А. Макарцова // Информационные технологии в образовании: XI Междунар. конф-выставка. Ч. IV. М.: МИФИ, 2001. С. 139-140.

4. Макарцова Е.А. Использование графического представления в планировании расписания занятий/ H.H. Клеванский, Е.А. Макарцова, Д.И. Ду-дин // Совершенствование подготовки учащихся и студентов в области графики, конструирования и стандартизации: межвуз. научн.-метод, сб. Саратов: СГТУ, 2002. С. 113-114.

5. Макарцова Е.А. Анализ результатов автоматического формирования расписания занятий вуза/ H.H. Клеванский, Е.А. Макарцова // Информационные технологии в образовании: XII Междунар. конф.-выставка. Ч. IV. М.: МИФИ, 2002. С. 193.

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

7. Макарцова Е.А. Критерии оценки расписания занятий вуза и автоматизация его корректирбвки/ H.H. Клеванский, Е.А. Макарцова, С.А.Костин // Информационные технологии в образовании: XIII Междунар. конф.-выставка Ч. IV. М.: МИФИ, 2003. С 199-201.

8. Макарцова Е.А. Формирование первоначального расписания занятий вуза с использованием многокритериальной выборки/ H.H. Клеванский, Е.А. Макарцова, С.С. Кашин // Информационные технологии в образовании: XV Междунар. конф.-выставка. Ч. IV. М.: МИФИ, 2005. С. 157158.

Лицензия ИД № 06268 от 14.11.01

Подписано в печать 15. 03. Об Формат 60x84 1/16

Бум. тип. Усл. печ.л. 1,0 Уч.-изд.л. 1,0

Тираж 100 экз. Заказ 90 Бесплатно

Саратовский государственный технический университет

410054, Саратов, Политехническая ул., 77 Отпечатано в РИЦ СГТУ. 410054, Саратов, Политехническая ул., 77

s

i

I

I '1

J

СОДЕРЖАНИЕ.

ВВЕДЕНИЕ.

• 1. СОСТОЯНИЕ ВОПРОСА И ЗАДАЧИ ИССЛЕДОВАНИЙ.

Ч 1.1. Анализ работ в области решения задачи автоматизированного | формирования расписания занятий.

1.2.Основные подходы к формализации решения задачи составления расписания.

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

Эвристические методы генерации расписаний.

1.3.Многокритериальность задачи составления расписания.

• Основные понятия и определения.

Многокритериальность в задаче формирования начального расписания занятий.

1.4.Постановка задач исследования.

• 2. РАЗРАБОТКА МЕТОДА СОСТАВЛЕНИЯ НАЧАЛЬНОГО РАСПИСАНИЯ

ЗАНЯТИЙ ВУЗА.

2.1.Общая постановка задачи составления начального расписания занятий в составе интегрированной системы управления учебным процессом вуз.

2.2.Разработка математической модели начального расписания занятий.

2.3. Метод составления начального расписания занятий вуза на основе многокритериальной выборки с использованием переопределяемых критериев загруженности.

3. МОДЕЛИРОВАНИЕ ИНФОРМАЦИИ В ЗАДАЧЕ РАСПИСАНИЯ.

3.1.Разработка критериев исходной информации.

3.2.Формирование тестовых заданий.

3.3.Разработка критериев анализа начального расписания занятий.

4. ПРИМЕНЕНИЕ МЕТОДА СОСТАВЛЕНИЯ НАЧАЛЬНОГО РАСПИСАНИЯ ЗАНЯТИЙ ВУЗА.

4.1.Расчеты без использования мультипликативного критерия выборки.

4.2. Расчеты с использованием мультипликативного критерия выборки для четырех «пар».

4.3. Расчеты с использованием мультипликативного критерия выборки для трех «пар».

Информатизация процессов управления деятельностью высшего учебного заведения отнесена к одному из основных направлений «Концепции информатизации высшего образования РФ». Информационные системы различной степени интеграции созданы для управления учебным процессом. В большинстве случаев они представляют собой совокупность разрозненных подсистем, каждая из которых решает свою отдельную задачу, используя локальную базу данных (БД).

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

Составление расписания занятий, являясь итерационным процессом, состоит вместе с тем из двух основных этапов. На первом этапе формируется начальное расписание на основе исходных данных об аудиторной нагрузке преподавателей. Основная проблема здесь связана со стратегией включения в расписание всей нагрузки. Расписание должно быть непротиворечивым и, по возможности, оптимальным. Непротиворечивость связана с соблюдением обязательных ограничений: у академической группы или преподавателя в одно и то же время может быть только одно занятие, отсутствие «окон» в занятиях студентов и др. Оптимальность расписания обеспечивается соблюдением желательных ограничений. Например, минимизация количества «окон» у преподавателей и/или равномерность распределения занятий студентов по дням недели и др. Всё это определяет сложность формирования начального расписания, а также его существенную значимость для следующего этапа. На втором этапе производится глобальная корректировка расписания с целью его оптимизации. Методы глобальной корректировки расписания рассмотрены в диссертации Костина С.А. «Модели и методы многокритериальной оптимизации начального расписания занятий» [58].

Основное отличие между этапами заключается в характере входных данных и способах их обработки. Входные данные первого этапа как объекта формализации являются неупорядоченным множеством элементов, отдельные атрибуты которых представляют три распределяемых ресурса - учащихся, преподавателей и учебные аудитории. Входные данные второго этапа являются упорядоченным во времени множеством тех же элементов. Задача первого этапа заключается в упорядочении неупорядоченного множества, тогда как задача второго этапа связана с обработкой уже упорядоченного множества. Следует также отметить идентичность обязательных ограничений для задач обоих этапов и различие в наборах желательных ограничений. Решение задач второго этапа существенно зависит от эффективности решения задач первого этапа.

В составлении начального расписания занятий используются два подхода. В первом первоначально распределяются два ресурса - контингент учащихся и учебные аудитории, то есть формируется «сетка» занятий, заполняемая затем занятиями конкретных преподавателей. Во втором подходе начальное расписание формируется на основе одновременного распределения всех трех ресурсов (учащиеся, преподаватели, аудитории).

Уменьшение числа распределяемых ресурсов в первом подходе (работы Ерунова В.П., Морковина И.Н.) [25] упрощает алгоритмы решения, кроме того, возможны минимизация количества требуемых учебных аудиторий и обеспечение равномерности загрузки академических групп. Оптимизация работы преподавателей при этом затруднена.

Второй подход (работы Давыдова С.В., Лагоша Б.А., Петропавловской A.B., Пантелеева Е.Р.) [61, 81] требует более сложных и трудоемких в вычислительном плане алгоритмов, но позволяет оптимизировать загруженность трех основных ресурсов, благодаря чему он был принят к использованию в данной работе.

Практически не исследованными при составлении начального расписания занятий являются:

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

- подходы с использованием рассчитываемых на каждой итерации приоритетов не включенных в расписание элементов входного множества, благодаря чему возможно автоматическое управление выбором элементов с наиболее загруженными ресурсами и их включением в формируемое расписание;

- вопросы создания средств генерации тестовых заданий для задач составления расписания занятий. Использование этих средств обеспечит отладку и анализ процессов составления начального расписания занятий.

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

К основным задачам работы, обеспечивающим достижение указанной цели, отнесены:

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

- реализация алгоритмов составления начального расписания занятий вуза;

- разработка средств генерации тестовых заданий;

- исследование характеристик разработанных методов и алгоритмов.

Объект исследования - теория расписаний.

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

Методологическая и теоретическая основа исследования - в диссертационной работе использован математический аппарат теории множеств, исследования операций, теории графов и целочисленного линейного программирования, а также общей теории расписаний.

В работе использованы методы системного анализа, статистики, оптимизации, компьютерной графики.

Научная новизна исследования состоит в следующем:

- разработана модель расписания занятий на основе учебных поручений в составе общей модели управления учебным процессом вуза;

- предложен метод решения задачи формирования начального расписания занятий, отличающийся от известных решений:

- возможностью реализации в интегрированных системах управления учебным процессом вуза;

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

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

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

Апробация результатов исследования - предложенные в диссертации модели, методы и алгоритмы были использованы при разработке и практической реализации информационных систем управления учебным процессом вуза. Система прошла внедрение в Саратовском государственном техническом университете и Саратовской государственной академии права и продолжает совершенствоваться.

Основные результаты работы докладывались на 2-й Всероссийской научной конференции молодых ученых и аспирантов (г.Таганрог, 1999), XI, XII, XIII и XV международных конференциях-выставках: «Информационные технологии в образовании» (г. Москва, 2001,2002,2003 и 2005).

Публикации. По теме диссертации опубликовано 8 работ.

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

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

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

В четвертой главе проанализированы полученные варианты расписаний, результаты вычислительных экспериментов.

1. СОСТОЯНИЕ ВОПРОСА И ЗАДАЧИ ИССЛЕДОВАНИЙ

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

1.1 Анализ работ в области решения задачи автоматизированного формирования расписания занятий

В настоящем постиндустриальном обществе роль информационных технологий (ИТ) чрезвычайно важна, они занимают сегодня центральное место в процессе интеллектуализации общества, развития его системы образования и культуры . Система образования и наука являются одним из объектов процесса информатизации общества [57].

Концепция информатизации высшего образования РФ» была разработана РосНИИ информационных систем и утверждена Министерством образования Российской Федерации в 1993 году. В концепции было объявлено, что стратегическая цель информатизации образования состоит в глобальной рационализации интеллектуальной деятельности за счет использования информационных технологий, радикального повышения эффективности и качества подготовки специалистов до уровня, достигнутого в развитых странах, т.е. за счет подготовки кадров с новым типом мышления, соответствующим требованиям постиндустриального общества.

В рамках данной концепции были выделены основные направления информатизации национальной системы образования. Одним из основных направлений развития информатизации национальной системы образования является информатизация процессов управления деятельностью высшего учебного заведения. Основным видом деятельности является учебный процесс [17,57].

В системе образования, как и в других сферах человеческой деятельности, создается программное обеспечение (ПО) для поддержки учебного процесса. Это могут быть базы данных (БД), информационно-справочные системы, хранилища информации любого вида, компьютерные обучающие программы, а также программы, позволяющие осуществлять администрирование учебного процесса.

Подразделения, связанные с управлением учебным процессом, такие как учебно-методическое управление (УМУ), деканаты, кафедры, имеют большой объем рутинной работы, связанной с решением ряда задач [53]: расчет штатного расписания кафедр; расчет годовой нагрузки кафедр; подготовка учебных и экзаменационных расписаний; распределение индивидуальной нагрузки между преподавателями, а также с подготовкой соответствующих документов: учебных поручений; зачетных и экзаменационных ведомостей; рабочих программ дисциплин и т.д.

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

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

Расписание учебных занятий - это документ, регламентирующий работу студентов, преподавателей, всего учебного заведения, распределяющий содержание учебного плана и рабочих программ по календарным дням учебного года и обеспечивающий их реализацию. Оптимально составленное расписание учебных занятий не должно изменяться в течение семестра или учебного цикла, чтобы не нарушить учтенные в расписании межпредметные связи и выполненные требования [25].

На составление расписания учебных занятий на семестр всей учебной части вуза может требоваться до одного месяца работы [85]. Расписание должно удовлетворять многочисленным требованиям организационного и методического характера, имеющим различные степени обязательности, часто взаимно противоречивым или даже взаимоисюпочаемым [25, 91]. Это затрудняет построение даже допустимых расписаний, не говоря уже об оптимальных. Во многих отечественных [25, 91] и зарубежных [98, 100, 128] работах указывается ряд требований и ограничений к расписанию занятий ВУЗ'а с разделением их на обязательные (hard constraint) и желательные (soft constraint). В таблицах табл. 1.1 и табл. 1.2 приводятся все выявленные требования и ограничения с разделением на соответствующие группы, а также их оценка.

Таблица 1.1

Методические требования к расписанию занятий ВУЗ'а

Требования и ограничения Оценка

Обязательные

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

Поддержка объединения групп в потоки и разбиения их на подгруппы для занятий по определенным дисциплинам.

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

Желательные (в порядке приоритета)

Требования и ограничения Оценка

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

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

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

Планирование занятий, требующих большого физического или нервного напряжения, на последние пары расписания занятий студенческой группы или на пары, предшествующие длительному перерыву между занятиями. Необходимо для восстановления сил. (В условиях ВУЗа к таким предметам относится фактически только физическое воспитание, но, поскольку часть анализируемого ПО предназначена для средних специальных заведений, этому требованию уделяется большое внимание).

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

12

Требования и ограничения Оценка

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

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

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

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

Равномерное распределение в течение недели сложных и трудоемких видов учебной работы Требование спорное по тем же причинам, что и предыдущее.

Таблица 1.2 Организационные требования к расписанию занятий ВУЗ'а

Требования и ограничения Оценка

Обязательные

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

Обеспечение всех видов занятий учебными помещениями, подходящими как по назначению, так и по количеству мест.

Требования и ограничения Оценка

Отсутствие «окон» в расписании студенческих групп.

Желательные (в порядке приоритета)

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

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

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

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

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

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

Задача автоматизированного составления расписаний учебных занятий выделяется руководителями учебных заведений как наиболее актуальная в планировании работы вуза, так как расписания приходится существенно изменять от семестра к семестру, в отличие от учебных планов и учебных программ. Интерес администрации учебных заведений к этой задаче вызвал большое количество исследований и разработок, как автономных программных систем, так и подсистем АСУ учебными заведениями. Первые работы по рассматриваемой тематике выполнялись в начале 60-х годов, когда в вузах появились ЭВМ массовых моделей. Для систем составления расписаний занятий в целом характерна сильная зависимость от специфики конкретных учебных заведений уже на уровне математических моделей и представления данных, что затрудняет использование типовых систем. Многие исследователи считают, что эффективно могут применяться только системы, спроектированные и реализованные от начала до конца для конкретных учебных заведений [25, 101].

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

В 1982 г. вышла публикация, касающаяся разработки и эксплуатации комплекса задач АСУ Пензенского политехнического института, ныне Пензенский государственный технический университет (ПГТУ) [15]. В составе системы на тот момент эксплуатировалось или находилось на стадии опытной эксплуатации 7 подсистем. Среди них подсистемы учебного процесса (учет абитуриентов, учет студентов, учет выпускников, учет успеваемости, семестровое расписание) и подсистемы НИС (расчет заработной платы НИС, учет и планирование НИР). Большинство систем было запрограммировано на базе ОС/ЕС и в качестве основного языка программирования использован ПЛ/1. Подсистемы имели общую организационную структуру, единую информационную базу, что облегчало процесс расширения и модернизации разработанных систем, а так же обеспечивало преемственность в развитии информации. Например, массив абитуриентов модернизировался: абитуриент-студент-выпускник.

Информационная система Владимирского государственного университета [72] автоматизирует получение следующих документов: академические справки и приложения к диплому, личные карточки студентов по результатам экзаменационных сессий, отчеты об успеваемости по факультету. То есть, решаются задачи, связанные с деятельностью деканата в рамках одного факультета. Примерно такой же круг задач решается информационными системами Российского химико-технологического университета им. Д.И. Менделеева [87], где объединена вся информация об абитуриентах и студентах в рамках института. Более широкий охват разных сторон учебного процесса представлен информационной системой [87], разработанной в г. Новочеркасске, Ростовской области для работы в рамках локальной учебной структуры типа филиала института, учебно-инженерного центра и тому подобных структур связанных с заочной формой обучения. По мнению разработчиков этой системы, она может решать следующие задачи: расчет общей нагрузки по кафедрам, расчет учебной нагрузки для специальностей, расчет аудиторных занятий. В нашем университете функционирует несколько разрозненных информационных систем, связанных с: учетом студентов и преподавателей на уровне отдела кадров и бухгалтерии, оформлением абитуриентов перед вступительными экзаменами, подготовкой информации по результатам сессий, подготовкой учебных поручений, формированием расписания занятий для всего университета и т.д.

В Тамбовском государственном университете функционирует автоматизированная система, созданная с целью автоматизации планирования и сопровождения процессов принятия решений в ТГУ им. Державина [20]. Функциональная структура системы включает в себя следующие подсистемы: «Студент», «Деканат», «Учебный отдел», «Рейтинг». Каждая подсистема работает с отдельной базой данных. Подсистемы «Деканат» и «Учебный отдел» связаны сетью, а информация по сети поступает в виде отчетов из деканатов в учебный отдел и накапливается в БД учебного отдела, это свидетельствует о том, что возможность из подсистемы «Учебный отдел», обратится к базе данных подсистемы «Деканат» отсутствует.

Подобные информационные системы, несомненно имеющие ряд своих особенностей функциональной и организационной структуры, реализованные с помощью различных программных средств, имеющие свои специальные возможности были разработаны в 90-е годы в таких вузах, как Таганрогский государственный радиотехнический университет, Воронежским государственный педагогический университет (ВГГГУ), Новосибирский государственном технический университет (НГТУ), Комсомольский- на Амуре государственный технический университет, Пермский государственный техническом университет, Санкт-Петербургский государственный университет (система электронного документооборота ЬатЮосБ), прототип автоматизированной информационной подсистемы с элементами искусственного интеллекта для поддержки обучения и управления учебным процессом был разработан в МГТУ им. Баумана [67] и т.д.

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

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

В Санкт-Петербургском государственном университете ведется активная работа по информатизации университета. Разработаны система управления персоналом, включающая программные комплексы отдел кадров и штатное расписание. В настоящий момент разрабатываются следующие продукты: Абитуриент; Студент; Стипендия; Бард-Студент; Аспирант; АИС БТИ;

На всероссийском форуме "Современная образовательная среда-2004" в Москве на ВВЦ НИИ ИТ СПбГУ представлял также новую свою разработку - программную систему "Бард-Студент". Информационная система "Бард-Студент" была разработана специально для Смольного института свободных искусств и наук. Система "Бард-Студент" поддерживает такие особенности обучения, как: индивидуальный учебный план, междисциплинарный подход в преподавании, кредитная система обучения, российская и американская система оценок, получение двух дипломов о высшем образовании.

Существует ряд известных систем для автоматизации процесса составления расписания занятий учебного заведения. Среди них: система формирования школьного расписания «Пенал» [11], разработчик ВП «ТетраПлюс», г. Минск; система управления учебным процессом «Методист» [11, 20], в состав который входит модуль формирования расписания занятий; система «Расписание 2000» [28, 33, 34, 35]; система «Мечта» [55, 56]; система «ХроноГраф», ООО «Хронобус» и др. [72, 87, 88]. Все они находятся в постоянном развитии, появляются новые возможности. Рассмотрим некоторые из них и другие системы более подробно.

Известная система "Автоматизированное рабочее место администратора школы для составления школьного расписания занятий (АРМ)" [69] была разработана институтом общего образования Министерства образования России. Система ориентирована на применение в школах различного профиля, различных систем обучения и вариантов учебного плана. В качестве основного источника исходных данных принят учебный план школы, на основе которого создается учебный план каждого класса. Недельная нагрузка классов и учителей определяется программой автоматически. Входные данные проверяются программой; выявленные при этом ошибки и рекомендации по их устранению выдаются оператору. Выдается также разнообразная аналитическая информация, используемая для контроля исходных данных и разрешения конфликтных ситуаций. Расписание может составляться в различных режимах с различными приоритетами (при заданных ограничениях на дни и часы занятий классов, при заданных требованиях к графику работы учителей, при заданном (ограниченном) числе кабинетов. Решение задачи осуществляется автоматически до нахождения оптимального, с точки зрения системы, варианта решения; если автоматическое решение затруднено, оператору выдаются рекомендации по изменению исходных данных для успешного решения. Предусмотрено директивное размещение некоторых занятий в определенные дни и часы (Например, специализация или практика на предприятиях, занятий с учителями совместителями) .

Система "Мечта" для составления расписаний школьных занятий, была разработана в Санкт-Петербургском государственном университете [55, 56]. Данная система хорошо известна среди подобных систем. Система включает ряд подсистем: ввода-корректировки исходных данных, настройки на особенности школы и тестирования на непротиворечивость исходных данных, вычислений (автоматического построения расписания), автоматизированной корректировки варианта расписания, оптимизации распределения аудиторий, печати расписания. Модель включает следующие основные объекты: преподаватель, класс, аудиторный фонд. Кроме этих объектов имеется ряд вспомогательных: совместные преподаватели; совместные классы; стратегия поведения и т.д. Вспомогательные объекты предназначены для сокращения перебора в процессе составления расписания. В системе предусмотрена возможность вмешательства в процесс автоматического составления расписания.

ТОО "ИНТЕГПРОГ" при НИВЦ Московского государственного университета им. М.В. Ломоносова (МГУ), разработала "Информационную систему для автоматизации составления расписаний занятий в ВУЗ'е" [14], которая предназначена для автоматизации работ по составлению расписаний учебных занятий. В данной системе процесс составления расписаний занятий разделен на два уровня: уровень учебной части, на котором составляется сетка часов для всех кафедр в соответствии с учебным планом занятий по факультетам, курсам, потокам и имеющимися аудиториями, уровень кафедр, на котором происходит расстановка в уже построенную сетку часов учебных групп, предметов, преподавателей, типов и продолжительностей занятий в соответствии с почасовой нагрузкой, ограничениями и т.д. В соответствии с этим система состоит из двух частей: подсистема учебной части "У-Часть", подсистема кафедральных расписаний "Ка-Рас". Подсистема "У-Часть" обеспечивает следующие функциональные возможности: автоматизацию составления сетей часов занятий по всем кафедрам, печать сетки часов занятий и других расчетных документов, формирование данных для работы и полную совместимость с подсистемой "Ка-Рас". Подсистема "Ка-Рас" обеспечивает следующие функциональные возможности: автоматизацию составления расписаний занятий учебных групп по отдельной кафедре, расчет нагрузки преподавателей, автоматизацию составления замен преподавателей кафедры, печать расписаний занятий учебных групп, преподавателей и кафедры в целом.

Система «Методист» [11, 20] позволяет составлять и корректировать расписание как для школ, так и для вузов. Система также помогает в решении следующих задач: распределение и контроль учебной нагрузки, учет методических рекомендаций и личных пожеланий преподавателей (окна, методические дни и т.д.), учет объединения групп (классов) в потоки и/или разбиение их на подгруппы, закрепление специальных аудиторий (компьютерные классы, лингафонные кабинеты и т.д.), возможность введения приоритетов преподавателей и т.д. Система состоит из трех модулей: «Учебная часть»

- является центральной координирующей частью комплекса. Здесь вводятся исходные данные, также проводится просмотр и печать расписания; «Кафедральные заявки» - предназначен для заполнения заявок кафедр (преподавателей) на проведение занятий. Заявка составляется для каждой дисциплины, каждой учебной группы (класса). В заявке указываются конкретные преподаватели, что и в какой группе они проводят, желаемые аудитории, пожелания к составлению расписания; «Формирование расписания»- позволяет задавать время решения задачи, изменять степень влияния различных учитываемых факторов, изменять готовое расписание.

Разработкой системы формирования расписания для факультета занималось в 2001-2002 г СКБ «Токен», созданное при Уральском государственном горном университете [11]. Попытка создания системы автоматизированного составления расписания занятий была разработана в Днепропетровском национальном университете Украины в 2004 году. Авторы - В.В. Резник, Ю.С. Морозов, A.M. Кулабухов. В программе используются следующие базы данных: БД преподавателей, БД групп, учитывающую, БД аудиторий, БД заявок на расписание, которые составляются и подаются выпускающими и кафедрами. Каждая база данных (БД) имеет свою жесткую структуру, которая может при необходимости модернизироваться. Также, имеется возможность составлять новые базы данных [11,20].

Также следует отметить такие системы для автоматизации составления расписания как система «Хронограф» фирмы Хронобус, систему автоматиза-рованного составления расписания фирмы Exos (г. Москва), систему Аверс-распиание, разработанную информационно-внедренческим центром «Аверс» (г. Москва) [11].

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

Разработан метод составления начального расписания занятий вуза на основе многокритериальной выборки с использованием переопределяемых критериев загруженности основных ресурсов и многокритериальной оценки для выбора места и времени проведения занятий. Создан алгоритм составления начального расписания занятий вуза с откатом.

Разработаны средства генерации тестовых заданий. Проанализированы характеристики разработанных методов и алгоритмов.

96

1. Автоматизация научных исследований и обучения.- Саратов: Изд-во Сарат. ун-та, 1986- 154 с.

2. Ахо А. Построение и анализ вычислительных алгоритмов / А. Ахо , Д. Хопкрофт, Д. Ульман М.: Мир, 1979. - 536 с.

3. Ашианов С.А. Линейное программирование / С.А. Ашианов- М. Наука. Главная редакция физико-математической литературы, 1981. -340 с.

4. Бабич В.И. Модели и результаты автоматизированного решения задач расписаний учебного процесса/ В.И. Бабич, А.И Раецкий // Методы и системы технической диагностики.- Саратов: СГУ, 1991. С. 99 102.

5. Бандадым В.А. Составление расписаний учебных занятий с помощью ЭВМ/ В.А. Бандадым //Управляющие системы и машины,- Киев, 1991, №8. С. 119-126.

6. Баркан С.А. О построении расписаний учебных занятий/ С.А. Баркан, B.C. Танаев // Весщ акадэми навук БССР. Сэр. Ф1зшаматэматычных навук, 1970.-№1. С. 76-82.

7. Барраклоу Э. Применение электронных цифровых вычислительных машин для составления расписания учебных занятий/ Э. Барраклоу // Кибернетика и проблемы обучения М.: Прогресс, 1970. С. 323-349.

8. Белов В.В. Теория графов/ В.В. Белов, Е.М. Воробьев, В.Е. Шаталов -М.:Высш.шк., 1976. 392с.

9. Ю.Блох А.Ш. Граф-схемы и алгоритмы/ А.Ш. Блох.-Минск: Высшая школа, 1987-141 с.

10. Н.Бондаренко Н.В. Новые технологии в управлении учебным процессом / Н.В. Бондаренко, Д.Ю. Сладков, Г.Д. Толстых // Информатика и образование-М., 1996, №6. С. 99-104.

11. Васильев Ф.П. Численные методы решения экстремальных задач / Ф.П. Васильев// Учеб. пособие для вузов. 2-е изд., перераб. и доп. - М.: Наука. Гл. ред. физ.-мат. лит., 1988. С. 260-277.

12. Венцель Е.С. Исследование операций. Задач, принципы, методология / Е.С. Венцель-М.: Наука, 1980.- 177 с.

13. И.Возяков В.И., Картузов A.B., Леванов Ю.П., Смолов З.Ф. Компьютерная поддержка оптимизации учебно-методической деятельности ВУЗ'а // Компьютеры в учебном процессе. М., 1998, № 11.С. 3-7.

14. Вопросы разработки и эксплуатации комплекса задач АСУ-ППИ/ Л.И Кунцова., Л.К. Коблов, В.А. Побелян, В.Н. Степченкова.- В кн. Теория и практика построения информационно-вычислительных систем. Изд-во Саратовского университета, 1982, С.41.

15. Герман Э.И. Решение задачи распределенного аудиторного фонда в вузе/ Э.И. Герман, Л.В. Пак, В.Н. Чудинов // Автоматизированные системы управления в вузе Новосибирск: НГУ, 1978. С. 138-142.

16. Голубков A.C. Информационные технологии требуют государственной поддержки/ A.C. Голубков //Информационные технологии, 1996, №1, С.2-5.

17. Григоришин И.А. Инструментальная поддержка учебного процесса в условиях применения автоматизированных учебных курсов: автореф. дис. канд.тех.наук/ И.А. Григоришин.- Киев, 1984-18 с.

18. Грин Д. Математические методы анализа алгоритмов / Д. Грин, Д. Кнут-М.: Мир, 1987. С. 49-50

19. ГэриМ. Вычислительные машины и труднорешаемые задачи / М. Гэри , Д. Джонсон М.: Мир, 1982. С. 300-313.

20. Давыдов Э.Г. Исследование операций/ Э.Г. Давыдов -М: Высш.шк.,1990.-383 с.

21. Дейт К. Введение в системы баз данных / К. Дейт // 6-е издание: Пер. с англ. К.; М.; СПб.: Издательский дом «Вильяме», 2000. - 848 с.

22. Евтушенко Ю.Г. Численный метод поиска глобального экстремума функций (перебор на неравномерной сетке) / Ю.Г. Евтушенко // Журн. вычисл. матем. и метем, физики, 1971. Т. 11. №. 6.

23. Ерунов В.П. Формирование оптимального расписания учебных занятий в вузе / В.П. Ерунов , И.И. Морковин // Вестник ОГУ, 2001. № 3. С. 5563.

24. Заславская О.Ю. Практическое применение программы "Расписание 2.0"/ О.Ю. Заславская // Информатика и образование . -М., 1997. №2. С. 128.

25. Заславский A.A. Использование стратегии расслоения переменных в общих задачах целочисленного линейного программирования/ A.A. Заславский // Экономика и математические методы -М., 1997. Т.ЗЗ. Вып.2. С. 53-55.

26. Индюшкин В.Л. Принципы построения математического обеспечения АСУ ВШ / В.Л. Индюшкин, В.И. Лысенко, С.Б. Тарасов -М.: НИИВШ, 1977.-83 с.

27. Капустин Е.В. Ввод исходных данных для системы "Расписание 2.0"/ Е.В. Капустин // Информатика и образование -М., 1997. №5. С. 123128.

28. Капустин E.B. Новые разработки фирмы ЛИнТех/ Е.В. Капустин // Информатика и образование -М, 1997. №1. С. 118.

29. Капустин Е.В. Технология работы с системой "Расписание 2.0"/ Е.В. Капустин // Информатика и образование, 1997. №2. С. 121-127.

30. Карпов В.И. Оптимизация составления учебных планов вузов/ В.И. Карпов, O.K. Хабарова// Вестник МГТУ. Сер. Приборостроение, 1998. №2. С. 109-113.

31. Клеванский H.H. Анализ результатов автоматического формирования расписания занятий ВУЗ'а / H.H. Клеванский, Е.А. Макарцова // Информационные технологии в образовании: XII Междунар. конф.-выставка. Ч. IV.M.: МИФИ, 2002 С. 193.

32. Клеванский H.H. Анализ требований и ограничений в задаче составления расписаний / H.H. Клеванский , A.A. Пузанов , С.А. Костин // Образовательные технологии: межвуз. сб. науч. тр. Вып. 12. Воронеж: Центр.-Черноземн. книжн. изд-во, 2004. С. 164-168.

33. Клеванский H.H. К вопросу о задаче формирования расписания занятий вуза / H.H. Клеванский, A.A. Пузанов, С.А. Костин // Моделирование и управление в сложных информационных системах: сб. науч. ст. -Саратов: СГТУ, 2004. С. 20-28.

34. Клеванский H.H. Критерии оценки расписания занятий ВУЗ'а и автоматизация его корректировки / H.H. Клеванский, Е.А. Макарцова, С.А. Костин // Информационные технологии в образовании: XIII Меж-дунар. конф.- выставка Ч. V. М.: МИФИ, 2003.С 199-201

35. Клеванский H.H. Модели и алгоритмы глобальной оптимизации первоначального расписания занятий ВУЗ'а / H.H. Клеванский , С.А. Костин // Информационные технологии в образовании: XIV Междунар. конф.-выставкаЧ. IV. М.: МИФИ, 2004. С.30-31.

36. Клеванский H.H. Моделирование проектной деятельности при разработке учебных планов ВУЗ'а / H.H. Клеванский, C.B. Наумова, С.А. Костин // Информационные технологии в образовании: XIII Междунар. конф.- выставка 4.V. М.: МИФИ, 2003. С.202-203.

37. Клеванский H.H. Разработка математической модели глобальной оптимизации расписания занятий / H.H. Клеванский, С.А. Костин, A.A.

38. Пузанов //Сложные системы. Анализ, моделирование, управление -Саратов: ООО Издательство «Научная книга», 2005. С.39-42.

39. Клеванский H.H. Формирование оптимального расписания занятий ВУЗ'а и средства его визуализации / H.H. Клеванский , С.А. Костин // Применение новых технологий в образовании: сб. матер. XV Междунар. конф. Троицк: «Байтик», 2004. С.380-382.

40. Клеванский H.H. Формирование расписания с использованием динамических критериев загруженности/ H.H. Клеванский, Е.А. Макарцова // Информационные технологии в образовании. XI Междунар. конф-выставка. Ч. IV. М.: МИФИ, 2001. С.139-140.

41. Клеванский H.H. Информационная поддержка управления учебной деятельностью вуза/ H.H. Клеванский, Е.А. Макарцова // Информационные технологии в образовании: сб. материалов, межвуз. науч.-метод. конф./ Сарат. гос. техн. ун-т. Саратов, 2000. С. 4- 5.

42. Клюев В.В. Компьютер помогает в составлении школьного расписания/

43. B.В. Клюев // Информатика и образование- М., 1998, №7. С. 108-117.

44. Клюев В.В. Может ли компьютер помочь в составлении школьного расписания?/ В.В. Клюев // Информатика и образование- М., 1996, №3.1. C. 115-120.

45. Колин К.К. Информационные технологии катализатор процесса развития современного общества/ К.К. Колин// Информационные технологии -М.: Новые технологии, 1995, №3, С.10-15.

46. Костин С.А. Модели и методы многокритериальной оптимизации начального расписания занятий: дис. канд. техн. наук: 05.13.18: защищена 27.12.05/ С.А. Костин.- Саратов, 2005.- 125 с.

47. Костюк В.И. Использование алгоритмов последовательной обработки для составления расписаний/ В.И. Костюк, Х.О. Мартинес, В.В.Зорин// Вопр. Создания АСУ ВУЗ-М.: НИИВШ, 1976. С. 3-5.

48. Кулагина М.М. Применение ЦВМ при составлении расписаний/ М.М Кулагина.// ЭВМ в учебном процессе и управлении вузами. -Рига: РПИ, 1974.С.116-122.

49. Лагоша Б.А. Комплекс моделей и методов оптимизации расписания занятий в вузе/ Б.А. Лагоша, A.B. Петропавловская // Экономика и математические методы.-М., 1993. Т.29. Вып.4.С. 76-85.

50. Ламан К. Применение UML и шаблонов проектирования / К. Ламан //

51. Пер. с англ.: Уч. Пос. М.: Издательский дом «Вильяме», 2001. С. 395399.

52. Лебедев С.С. О методе упорядочивающей индексации целочисленного линейного программирования/ С.С. Лебедев // Экономика и математические методы. -М., 1997. Т.ЗЗ. Вып.2.С. 56-58.

53. Лебедев С.С. Модифицированный метод пометок для задач булева программирования/ С.С. Лебедев, A.A. Заславский // Экономика и математические методы.-М., 1998. Т.34. Вып.4. С. 23-26.

54. Липский В. Комбинаторика для программистов / В. Липский // Пер. спольск. М.: Мир, 1988. - 213 с.

55. Мамаев A.A. Прототип автоматизированной информационной системы поддержки рейтинговой технологии и управления учебным процессом./

56. A.A. Мамаев, A.B. Кайдоров// Ежегодная научно-технической конференции студентов и аспирантов электротехнического факультета Пермского Государственного Технического Университета: сб. тез. докл. -Пермь, ПГТУ, 1997. С. 21-22.

57. Марков A.C. Автоматизированная информационная подсистема с элементами искусственного интеллекта для поддержки обучения и управления учебным процессом/ A.C. Марков, Н.В. Медведев, A.C. Черников // Вестник МГТУ. Сер. Приборостроение, 1995, №2. С. 44-49.

58. Матросов A.B. MS Office ХР: разработка приложений / A.B. Матросов ,

59. Ф.А. Новиков, Г.Е. Усаров , И.А. Харитонова /Под ред. Ф.А. Новикова СПб.: БХВ - Санкт-Петербург, 2003. - 944 с.

60. Матусевич O.JI. Новый пакет программ для составления расписания занятий в школе/ O.JI. Матусевич // Информатика и образование,1997,№3. С. 123-124.

61. Мейер Д. Теория реляционных баз данных/ Д. Мейер- М.: Мир, 1987.213 с.

62. Моделирование и оптимизация вычислительных систем и процессов: сб. науч. тр.- Ярославль: Ярославский государственный университет, 1988- 159с.

63. Моргунов И.Б. Основы дискретной оптимизации некоторых задач упорядочения (на примере учебного процесса)/ И.Б. Моргунов- М.: Исследовательский центр проблем качества подготовки специалистов. 1994.215 с.

64. Мухачева Э.А. Точный алгоритм составления расписания для одностадийной системы с независимыми параллельными машинами / Э.А. Му-хачева Э.Ю. Орехов //Информационные технологии, -М.: Новые технологии, 2004,№2. С. 16-27.

65. Наумова C.B. Разработка и применение средств моделирования в автоматизированных системах ситеза учебных планов высшего образования: дис. канд. техн. наук: 05.13.18, 05.11.16: защищена 14.10.05/ C.B. Наумова. Саратов, 2005.- 125 с.

66. Ногин В.Д. Логическое обоснование принципа Эджворта-Парето / В.Д. Ногин // Ж. вычисл. матем. и матем. физ. 2002. Т. 42. № 7. С. 951-957.

67. Ногин В.Д. Основы теории оптимизации / В.Д. Ногин И.О. Протодьяконов, И.И. Евлампиев-М.: Высшая школа, 1986. -146с.

68. Овчинников A.A. Сетевые методы планирования и организации учебного процесса/ A.A. Овчинников, B.C. Путинский, Г.Ф. Петров -М.: Высш.шк., 1972.-156 с.

69. Орлов В.Н. Анализ автоматизированных систем по составлению расписаний учебных занятий/ В.Н. Орлов // АСУ-высшая школа.- Чебоксары: ЧТУ, 1976.С. 68-74.

70. Пантелеев Е.Р. Метамодель распределения ресурсов в задаче проектирования учебного расписания вуза/ Е.Р. Пантелеев// Информационные технологии- М., 1999. №7. С. 45-49.

71. Пилюгин В.В. Машинная графика и автоматизация научных исследований / В.В. Пилюгин, Л.Н. Сумароков, К.В. Фролов // Вестн. АН СССР. -М.,1985, № 10. С. 50-58.

72. Подиновский В.В. Парето-оптимальные решения многокритериальных задач / В.В. Подиновский , В.Д. Ногин М.: Наука, 1982- 125с.

73. Савельев А.Я. Автоматизация управления вузом/ А.Я. Савельев, Ю.Б. Зубарев, В.Е. Коваленко, Т.А. Колоскова.- М. Радио и связь, 1984. 176 с.

74. Самофалов К.Г. Автоматизация составления расписания в вузе/ К.Г. Самофалов, В.П. Симоненко -Киев: КПИ, 1972.-144 с.

75. Свами М. Графы, сети и алгоритмы/ М. Свами, К. Тхуласираман.-М.: Мир, 1984.- 404 с.

76. Создание автоматизированной системы управления в Московском институте электронной техники. Подсистема «Расписание».-М.: НИИВШ, 1973.-32 с.

77. Танаев B.C. Введение в теорию расписаний/ B.C. Танаев, В.В. Шкурба -М.: Наука, 1975.-354с.

78. Теория расписаний и вычислительные машины: Пер с англ.-М.:Наука, 1984.-334с.

79. Федотов А.Ф. Учебно-организационная работа в вузе / А.Ф. Федотов, Н.Н. Трунов-Л.: ЛПИ, 1980. 112 с.

80. Фишберн П. Теория полезности для принятия решений / П. Фишберн -М.: Наука, 1978.

81. Харитонова И.А. Microsoft ACCESS 2000: разработка приложений / А.В. Харитонова, В.Д. Михеева / СПб.: БХВ Санкт-Петербург, 2000. - 832 с.

82. Ху Т. Целочисленное программирование и потоки в сетях/ Т. Ху. -М.: Мир, 1979.-318 с.

83. AggounA. Extending CHIP in order to solve complex scheduling and placement problems. / Aggoun A., Beldiceanu N. // Math. Comput. Modelling. 1993. V. 17, N. 7. P. 57-73.

84. Akkoyunly E.A. A Linear Algorithm for Computing the Optimum University Timetable / Akkoyunly E.A. // The Computer Journal. 1973. V. 16, N. 4. P. 347-350.

85. AH M. Stochastic Global Optimization: Problem, Classes and Solution Techniques / Ali M., Torn A., Viitanen S. // J. of Global Optimization. 1999. V. 14. P. 437-447.

86. Beldiceanu N. Introducing global constraints in CHIP / Beldiceanu N., Cont-jean E. // Mathematical and Computer Modelling. 1994. V. 20, N. 12. P. 97123.

87. Berge C. Isomorphism problems for hypergraphs / Berge C. // Lecture Notes in Mahtematics. Spring-Verlag. 1974, P. 1-12.

88. Burke E. A Genetic Algorithm for university timetabling / Burke E., Elli-man D., and Weare R. // In AISB Workshop on Evolutionary Computing. University of Leeds, UK. 1994.

89. Burke E. Automated University Timetabling: The State of the Art / Burke E., Jackson K., Kingston J., Weare R.// Computer Journal. 1997. V. 40. P. 565571.

90. Burke E.K. Applications in Timetabling / Burke E.K., de Werra D., Kingston J. section 5.6 of the Handbook of Graph Theory (eds. J. Yellen and J. Grossman), to be published by Chapman Hall/CRC Press, 2003.

91. Burke E.K. A university timetabling system based on graph colouring and constraint manipulation / Burke E.K., Elliman D.G., and Weare R.F.// Journal of Research on Computing in Education. 1994. V. 27. P. 1-18.

92. Carter M.W. A Survey of Practical Applications of Examination Timetabling / Carter M.W. // Operations Research. 1986. V 34. P. 193-202.

93. Chahal N. An Interactive System for Constructing Timetables on a PC / Chahal N., de Werra D. // Eur. J. Oper. Res. 1989. V. 40. P. 32-37.

94. Cole R. On edge coloring bipartite graphs / Cole R., Hopcroft J. // SI AM J. Comput. 1982. V. 11, N. 3. P. 540-546.

95. Colorni A. Genetic Algorithms: A New Approach to the Time-Table Problem / Colorni A., Dorigo M., Maniezzo V. // Lecture Notes in Computer Science NATO ASI Series, V. F82, Combinatorial Optimization, Springer Verlag, 1990. P. 235-239.

96. D. de Werra. An Introduction to Timetabling / D. de Werra // European Journal of Operational Research. 1985. V. 19. P. 151-162.

97. Davis L. Schedule optimization with probabilistic search / Davis L., Rutter L. // Proceedings of the 3rd IEEE Conference on Artificial Intelligence Applications (Orlando, Florida, USA, Feb. 1987), IEEE1987,1987. P. 231-236.

98. Dixon L.C.W. Towards Global Optimization 2 / Dixon L.C.W., Szego G.P. //North-Holland, 1978.

99. Even S. On the complex of timetable and multicommodity flow problems / Even S., Itai A., Shamir A. // SIAM J. Comput. 1975. V. 5, N. 4. P. 691-703.

100. Feldman R. Optimization algorithms for student scheduling via constraint satiability / Feldman R., Golumbic M.C. // The Computer Journal. 1990. V. 33, N. 4.

101. Gotlieb C.C. The construction of class-teacher time-tables / Gotlieb C.C. // Inform. Proc. 1962. Proc. IFIP Congr. 62. Amsterdam: North-Holland, 1963. P. 73-77.

102. Horst R. Handbook of Global Optimization / Horst R., Pardalos P.M. -Dordrecht, Kluwer, 1995.

103. Koulmas C. A survey of simulated annealing applications to operations research problems / Koulmas C., Antony S.R., Jaen R. // Omega International Journal of Management Science. 1994. V. 22. P. 41-56.

104. Mehta N. The Application of a Graph Coloring Method to an Examination Scheduling Problem / Mehta N. // Interfaces. 1981. V. 11. P. 57-64.

105. Messmer B.T. Efficient graph matching algorithms for preprocessed model graph, PhD thesis, University of Bern, Switzerland, 1995.

106. Moccus J. Application of Bayesian Approach to Numerical Methods of Global and Stochastic Optimization / Moccus J. // J. Global Optimization. 1994. V. 4, N. 4. P. 347-356.

107. Noghin V.D. Relative importance of criteria: a quantitative approach / Noghin V.D. // J. Multi-Criteria Dec. Analys. 1997. V. 6. P. 355-363.

108. Rinnoy Kan A.H.G. Stochastic Global Optimization Methods / Rinnoy Kan A.H.G., Timmer G.T. //Mathematical programming. 1987. V. 39. P. 27-78.

109. Rudova H. University Course Timetabling with Soft Constraints / Rudova H., Murray K. // in: Edmund Burke and Patrick De Causmaecker: Practice And Theory of Automated Timetabling IV. Springer-Verlag LNCS 2740, 2003. P. 310-328.

110. Sakkout H.E. Wallace M. Probe Backtrack Search for Minimal Perturbation in Dynamic Scheduling / Sakkout H.E., Wallace M. // Constraints. Kluwer Academic Publishers. 2000. V. 4, N. 5. P. 359-388.

111. Tripathy A. A lagrangean relaxation approach to course timetabling / Tri-pathy A. //Journal of Operational Research Society. 1980. V. 31. P. 599-603.

112. Tripathy A. School timetabling a case in large binary integer linear programming / Tripathy A. //Manag. Sci. 1984. V. 30, N. 12. P. 1473-1489.

113. Yoshikawa M. A Constraint-Based Approach to High-School TimeTabling Problems: A Case Study / Yoshikawa M., Kaneko K., Nomura Y., Watanabe M. // Proceedings of the Twelfth National Conference on Artificial Intelligence AAAI-94, Seattle, 1994.

114. BO.Zavriev S.K. On the Global Optimization Properties of Finite-difference Local Descent Algorithms / Zavriev S.K. // J. of Global Optimization. 1993. V. 3. P. 63-78.