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

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

003167644

Рубцов Олег Геннадиевич

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ФОРМИРОВАНИЯ РАСПИСАНИЯ ЭКЗАМЕНОВ ВУЗА

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

АВТОРЕФЕРАТ

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

Саратов 2008

003167644

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

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

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

Официальные оппоненты - доктор технических наук, профессор

Кушников Вадим Алексеевич

- доктор физико-математических наук, профессор

Железовский Борис Емельянович

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

- ООО «Информационные бизнес-системы» (г Москва)

Защита диссертации состоится 12 марта 2008 г на заседании диссертационного совета Д 212.242 08 при ГОУ ВПО «Саратовский государственный технический университет» по адресу: 410054, г Саратов, ул Политехническая, 77, корп. 1,ауд 319

С диссертацией можно ознакомиться в научно-технической библиотеке ГОУ ВПО «Саратовский государственный технический университет»

Автореферат разослан «И» февраля 2008 года

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

А А Терентьев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Под математической моделью теории расписании понимается математическое описание некоторою управляемого производственного, организационного техноло1 ического процесса, в котором определено множество допустимых управлений (расписаний) эгого процесса Основным критерием оптимальности для задач теории расписаний является протяженность во времени некоторого дискретного процесса Целью решения большинства задач теории расписаний является минимизация времени выполнения данного процесса Классическими для теории расписаний задачами являются задачи сетевого планирования и календарного (В С Тагтев, В С Гордон, Я М Шафранский, Д Конвей, С Максвелл, К Миллер)

К задачам формирования расписаний относятся задачи на формирование временных таблиц (timetabhng-задачи) и задачи распределения пакетов информации в информационных сетях (Packet routmg-задачи) К timetablmg-задачам относят задачи формирования расписаний вузов, транспортные расписания и т д Существенным отличием timetablmg-задач от классических задач теории расписания является фиксированная величина интервала времени, в котором необходимо распределив процессы

Timetabhng-задачи, как правило, не могут бьпь решены точными методами Для решения таких задач используются различные эвристические алгоритмы (Е Burke, Y Bykov и др)

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

Получаемое на каждом этапе расписание экзаменов должно быть непротиворечивым, т е. соответствовать обязательным ограничениям, и учитывать требования к качеству, те соответсшовап, желательным ограничениям Количество и качество желательных ограничений влияют на возможность и трудоемкость получения решения В соответствии с работами ряда авторов (И И Морковин, Э А Мухачева, А А Овчинников, Е Zitzler, Y Bykov) будем рассматривать проблему формирования расписания экзаменов как многокритериальную

Задача формирования расписания экзаменов имеет существенные отличия по сравнению с задачами формирования расписания занятий, рассмотренными в диссер1 анионных работах Е А Макарцовой и С А Костина

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

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

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

В соответствии с целью в диссертации поставлены следующие задачи.

1) разработка математической модели и методов формирования и оптимизации расписания экзаменов вуза с использованием критериев загруженности ресурсов и критериев равномерности,

2) разработка метода визуального моделирования информации в задаче формирования расписания экзаменов,

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

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

Объект исследования - расписание экзаменов вуза Предмет исследования — формирование начального расписания экзаменов вуза и е1 о многокритериальная оптимизация

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

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

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

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

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

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

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

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

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

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

- программное обеспечение, формирующее расписание экзаменов вуза

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

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

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

Основные результаты работы докладывались на XVI и XVII Международных конференциях «Информационные технологии в образовании» в 2006 и 2007 ir

Публикации. Г1о геме диссертации опубликовано 7 работ, в том числе одна в издании, рекомендованном ВАК РФ

Структура и объем работы. Диссертационная работа состоит из введения, трех глав и заключения, изложенных на 105 страницах, в том числе 18 рисунков, списка использованной литературы, включающего 83 наименования

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

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

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

На основе выполненного в первой главе анализа были сделаны следующие выводы

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

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

3 Недостаточно исследованы решения задачи формирования расписания экзаменов в составе интегрированной системы управления учебным процессом вуза на основе централизованной базы данных

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

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

Входные данные. К основным элементам входных данных для формирования расписания экзаменов относятся следующие

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

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

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

3. Аудитории - множество доступных для приема экзаменов аудиторий.

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

- время, т.е. таймслот;

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

В формализованном виде эти элементы представлены соответствующими множествами:

В — = Л-"5«^} - множество дисциплин.

— множество преподавателей, принимающих экзамены

- множество групп сдающих экзамены.

^ = \У/\п ~ Л—?-^} - множество подгрупп сдающих экзамены. В ряде случаев группы разбивают на подгруппы для сдачи экзаменов. Это, в первую очередь, может быть связано со спецификой дисциплины или спецификой организации учебного процесса

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

7. — X ^ У 2 = {г0 | о = 1,..., О} . студенческий контингент.

Т ~ №р I Р ~ 1>-*-» Р} — множество таймслотов

Л - {ак\к — 1,...,К] -множество учебных аудиторий.

Е — {е,|г = Д...,/) - множество учебных поручений.

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

при условии, чго ^ е ^ , го е . Р/ е Р

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

а1=а{е1^р,ак) = 0.{4],г0,р1,ак^р). (1)

Ограничения, накладываемые на задачу.

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

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

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

Уг0 е 2, Уск е Т, Щ е Д Мс1] е П

2 Ни один преподавагель не может принимать более одного экзамена одновременно

Мр1 е P,^ftk е Т,Щ е ДУ<1] е О

3 Ни в одной аудитории не может приниматься более одного экзамена одновременно

Чар е А,Ък е ТУс1, еДУ^еО, (<*, Ф ¿у) о Ф П(с1гё,р,ар,1к)

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

К обязательным ограничениям отнесено также требование

4 Ни один преподаватель не может принимать более одного экзамена в день

При формировании начального расписания экзаменов учитываются следующие желательные ограничения (в зарубежной литературе - бой-сош1тат1з) при определении таймслота и аудитории для экзамена

1 Обеспечение равномерное!и распределения экзаменов каждой группы в период сессии

2 Обеспечение равномерности распределения экзаменов в таймслотах сессии

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

Кртерий загруженности учебного поручения.

Каждое из множества учебных поручений Е ~ \etl = мож-

но оцеишь, 1 е поставить ему в соответс1Вие критерий зафуженности.

v1 - Кх xKr хК, хКу, ^

О <KX,KP,K^ £1,

где частные критерии загруженности группы, преподавате-

ля и аудитории, рассчитываемые следующим образом.

г _ а{ ~а2 (6) ' Г I '

а -а2

где а\ - количество запланированных ресурсу экзаменов на период сессии,

а2 - количество включенных в расписание экзаменов ресурса; Т

@ ~ количество гаймслотов сессии

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

1. Учебные поручения с требуемыми аудиториями, например, дисплейные классы для приема экзаменов по программированию Для них критерий загруженности аудитории определяется выражением (6).

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

„null „null Knull _ <Ц А ~ null null'

а -а2 (7)

1де а"и11~ количество учебных поручений без требуемых аудиторий;

а™^- количество включенных в расписание учебных поручений без требуемых аудиторий,

аш11 - количество таймслотов всех доступных аудиторий.

Частный критерий учета экзаменов подгрупп К у

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

- количество подгрупп группы

Таким образом, кри1ерий загруженное ги учебною поручения является мультипликативным обобщенным критерием, включающим частые критерии загруженности группы, преподавателя и аудитории Значение обобщенного критерия переопределяется по мере включения экзаменов в расписание (рис 1)

Формирование начальною расписания экзаменов в предлагаемом методе заключается в последовательном выборе наиболее загруженною учебного поручения, нахождении для него наиболее подходящих гаймсло-та и аудитории с учетом обязательных (2)-(4) и желательных ограничений и переопределении критериев за1 руженности (5) оставшихся учебных поручений

Соблюдается следующая последовательность действий

1 Рассчитываются кри герии загруженности всех необработанных учебных поручений

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

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

4 Поручение включается в расписание экзаменов

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

При включении в расписание первого экзамена каждой группы выполняются следующие действия

1 Определяется наименее загруженный, удовлетворяющий обязательным ограничениям таймслог

2. Исходя из запланированного количества экзаменов 1руппы определяются предположительные таймслот ы для оставшихся экзаменов.

3. Относительно таймслота каждого существующего и предполагаемых экзаменов формируется поддиапазон допустимых таймслотов (рис 2) Данные поддиапазоны использую 1ся также в методе оптимизации начального расписания

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

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

Результаш формирования начальною расписания для одного из тес-ювых задании представлены на рис 4,а

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

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

допустимые тайме лоты для начального расписания

Рис.2. Определение диапазонов допустимых гаймслотов для экзаменов группы

Используемая в работе концепция равномерности распределения экзаменов позволяет оценить качество расписания с помощью критериев равномерности. В представляемой работе равномерность оценивается двумя критериями: критерием равномерности распределения экзаменов для групп в период сессии и критерием равномерности распределения экзаменов в таймслотах сессии.

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

Критерий равномерности экзамена группы определяется как:

К, = -15 Г, 51, (9)

2* А Р

где 2,е+1, Ье_1 - интервалы между текущим и ближайшими экзаменами группы.

где £ - средний интервал между экзаменами для группы

I - количество экзаменов группы

Критерий К^ является относительной величиной, а его знак указывает

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

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

кгпЛ \к{\,

'=1 (11) где N - количество экзаменов групп в расписании

Равномерность распределения экзаменов но таймслотам определяется количествами экзаменов в таймслотах расписания, т е количествами экзаменов, принимаемых одновременно

Ыср-Ыт

Кг

Кср ' (12)

где №р- среднее количество экзаменов в таймслоте;

ЫТ - текущее количество экзаменов в таймслоте.

Критерий К2 является относительной величиной, а ее знак указывает на необходимость добавления/исключения экзамена в таймслоте Значение этого критерия присваивается всем экзаменам таймслога

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

КГ=Ькг\*(.*Г'У. (13)

»-1

В работе представлен метод оптимизации начального расписания экзаменов, использующий введенные критерии равномерности для экзамена (9) и (12) и расписания (11) и (13).

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

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

Обобщенный мультипликативный критерий экзамена рассматривается как произведение абсолютного значения кршерия равномерности экзамена группы (9) и критерия равномерности экзамена в тймслотс (12)

Кжз

Обобщенный аддитивный критерий экзамена рассматривается как сумма абсолютного значения критерия равномерности экзамена группы (9) и критерия равномерности распределения экзаменов в таймслоте (12)

Км =| К\ I 1 (15)

Обобщенный аддитивный критерий расписания рассмафивается как сумма абсолютного значения частных критериев равномерности экзаменов групп (11) и равномерности распределения экзаменов в таймслотах (13).

Красп=\К{асп\ + \КГасп\ (16)

Начальное расписание экзаменов необходимо оптимизировать при отличной от нуля величине обобщенного критерия расписания (16) Целью оптимизации является получение расписания с наименьшим возможным значением обобщенного критерия расписания Красп. Получение расписания с Крас" -0 практически невозможно, т к невозможно достичь идеальной равномерности распределения экзаменов групп в период сессии (например, в случае нечетного количества экзаменов группы в сессии с четным количеством таймслотов)

На каждой итерации (рис 3)

1) производится определение обобщенных критериев равномерности каждого экзамена и всего расписания,

2) выбирается наименее равномерно распределенный экзамен, т е. экзамен с максимальным обобщенным критерием,

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

4) если вариант перестановки найден, то полученный вариант включается в расписание, переопределяются частные и обобщенные критерии экзаменов и расписания и происходит возврат к пункту 1;

5) если вариант перестановки для данного экзамена не найден, то осущес гвляется переход к пункту 2.

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

Рис. 3. Алгоритм оптимизации начального расписания экзаменов

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

Это позволяет осуществить решение второй задачи работы

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

Для анализа работы разработанного алгоритма формирования начального расписания экзаменов были сформированы тестовые задания.

Данные тестового задания содержат информацию об учебных поручениях для приема экзаменов в 50 группах пяш курсов факульгега дневного отделения Общее количество учебных поручении сосгавило 250 Продолжительность экзаменационной сессии при пята равной 21 дшо. Каждый день сессии включает две смены сдачи экзаменов, вследс!вие чсю расчетное количество таймслотов сессии составило 42.

В одном из рассчитанных первоначальных расписаний (рис 4,а) получено, что частные критерии равномерности расписания составляю г /С,'""" = 85,23 и к{""' = 58,672 Многокритериальная оптимизация позволила существенно улучшить равномерность расписания Значения критериев равномерности расписания для найденного Парето-оптималыюго варианта составили а"/"*" =22,857 к?"' =3,52 (рис, 4,6) Для указанного тестового задания наибольшее возможное значение критериев составило соответственно j^pacn~\62 и ^осл=1850

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

Разработанное программное обеспечение было использовано в Саратовской государственной академии права (СГАП) Исходные данные дая формирования расписания сессии дневного отделения включали 629 учебных поручений Частные критерии равномерности начального расписания, полученного в результате расчета, составили Kfac" -7SM и К^ас" =41 87.

Некоторые экзамены были фиксированы в расписании в связи с учетом требований преподавателей и руководства кафедр После оптимизации частные критерии равномерности расписания составили соответственно j^pacn _45 j g и ¡^Расп =27 52 Наибольшее возможное значение критериев

равномерности для данного расписания составило ^ржи=189 и

красп~2230

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

Рис 4. Результаты формирования расписания экзаменов:

а - начальное расписание; б - оптимальное расписание

раем

х+

х+

*)-

хь

*

XX

XXI-

XX ж +

ж - -в-

X +

жх +

Х++ ХХ+

хж-н-

X +

X +

ЖХХ/Р"

X +

ХЖХ XX +

ж» +

X +

хххххххх -нн-нн+н-

ЖХХХ +4+НЖ-

К1ИПН МИ 1 11'

Красп

1

+ оптимизация по мультипликативному критерию экзаменов х оптимизация по аддитивному критерию экзаменов Рис. 5. Изменение критериев равномерности

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

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

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

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

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

5 Разработанное и внедренное в Саратовской государственной академии права и Московской медицинской академии им И М Сеченова программное обеспечение позволяет полностью автоматизировать процесс формирования расписания экзаменов в составе интегрированной системы управления учебным процессом вуза

6 Разработан метод визуального представления информации в задаче формирования расписания экзаменов в виде круговой диаграммы

7 Проведен анализ разработанных методов с использованием мультипликативных и аддитивных критериев равномерности, показавший эквивалентность применения обоих критериев

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

В издании, рекомендуемом ВАК РФ 1 Рубцов О Г Модели и методы многокритериальной оптимизации расписаний вуза/ Н Н Клеванский, А А Пузанов, О Г Рубцов // Вестник Саратовского государственного технического университета 2006 № 4 (17). Вып. 2. С.76 - 82.

В других изданиях

2 Рубцов О Г Тестовые задания и алгоритмы составления расписания экзаменов / Н Н Клеванский, А В Свиридов, О Г Рубцов //Математические методы в технике и технологиях сб трудов XIX Междунар науч конф Воронеж ВГТА, 2006. С 112 - 114

3 Рубцов О Г Использование визуального моделирования в задачах расписания вуза / Н Н Клеванский, О Г Рубцов // ИКТ в управлении образованием XVI Междунар конф «Информационные технологии в образовании» («ИТО-2006») в 6 ч М МИФИ, 2006 Ч V С 39

4 Рубцов О Г Использование многокритериальных подходов в задачах управления учебным процессом вуза / Н Н Клеванский, С С Кашин, О Г Рубцов // ИКТ в управлении образованием XVI Междунар конф «Информационные технологии в образовании» («ИТО-2006») в 6 ч М МИФИ, 2006 Ч V С 37-38

5 Рубцов О Г Тестовые задания для расписания экзаменов вуза / Н Н Клеванский, О Г Рубцов // Техническая кибернетика, радиоэлектроника и системы управления VIII Всерос науч конф студентов и аспирантов Таганрог ТГРТУ, 2006 С 81 - 82

6 Рубцов О Г Формирование начальных расписаний экзаменов / Н Н. Клеванский, О Г Рубцов // ИКТ в управлении образованием XVII Междунар конф «Информационные технологии в образовании» («ИТО-2007») в6ч М МИФИ,2007 4VC47

7 Рубцов О Г Оптимизация начальных расписаний экзаменов / Н Н Клеванский, О Г Рубцов // ИКТ в управлении образованием XVII Междунар конф «Информационные технологии в образовании» («ИТО-2007») в 6 ч М МИФИ, 2007 Ч V С 48

Подписано в печать 08 02 08 Формат 60x84 1/16

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

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

Саратовский государственный технический университет 410054, Саратов, Политехническая ул, 77

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

ВВЕДЕНИЕ.

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

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

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

1.3 Математйческие основы многокритериальной оптимизации.

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

Глава 2: ФОРМИРОВАНИЕ И ОПТИМИЗАЦИЯ

НАЧАЛЬНГО РАСПИСАНИЯ ЭКЗАМЕНОВ.

2.1 Общая постановка задачи.

2.2 Множественно-графовая модель расписания экзаменов.

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

2.3.1 Ограничения, накладываемые на задачу.

2.3.2. Критерии загруженности учебного поручения.

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

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

2.4 визуализация информации в задаче формирования расписания экзаменов.

2.5 Оптимизация начального расписания экзаменов.

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

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

2.5.3 метод оптимизации начального расписания экзаменов.

Глава 3 ПРИМЕНЕНИЕ МЕТОДОВ ФОРМИРОВАНИЯ

И ОПТИМИЗАЦИИ РАСПИСАНИЯ ЭКЗАМЕНОВ ВУЗ'А.

3.1. Анализ формирования начальных расписаний экзаменов.

3.2. Анализ работы алгоритма оптимизации.

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

Под математической моделью теории расписаний понимается математическое описание некоторого управляемого производственного, организационного технологического процесса, в котором определено множество допустимых управлений (расписаний) этого процесса. Основным критерием оптимальности для задач теории расписаний является протяженность во времени некоторого дискретного процесса. Целью решения большинства задач теории расписаний является минимизация времени выполнения данного процесса. Классическими для теории расписаний задачами являются задачи сетевого планирования и календарного (B.C. Танаев, B.C. Гордон, Я.М. Шафранский, Д. Конвей, С. Максвелл, К. Миллер).

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

Timetabling-задачи, как правило, не могут быть решены точными методами. Для решения таких задач используются различные эвристические алгоритмы (E.Burke, Y. Bykov и др.).

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

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

Автоматизированное составление расписания на любом этапе формирования расписания является многофазным процессом, включающим:

-формализацию задачи формирования расписания и определение ограничений;

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

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

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

Для оценки качества формируемого расписания, уже на этапе формирования начального расписания к обязательным ограничениям добавляется ряд непротиворечивых, желательных (soft) ограничений. Ограничения именуются «желательными» потому, что расписание может не отвечать данным ограничениям, отвечать частично или полностью. Оценка качества проводится по соответствию расписания желательным ограничениям. Количество и качество этих ограничений существенно влияет на возможность и трудоемкость получения решения. В соответствии с работами ряда авторов (И.И. Морковин, Э.А. Мухачева, А.А. Овчинников, Е. Zitzler, Y. Bykov) будем рассматривать проблему формирования расписания экзаменов как многокритериальную

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

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

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

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

К принципиальным отличиям относятся: использование обязательных ограничений принципиально отличных от ограничений, используемых при формировании расписания занятий. Например, в расписании экзаменов необходимо обязательное включение «пауз» между экзаменами группы таким образом, чтобы студенты имели время на подготовку, тогда как при формировании расписаний занятий отсутствие «окон» между занятиями являются одним из видов желательных ограничений. повышение в полтора-два раза количества расставляемых в расписании событий по сравнению с задачей формирования расписания учебных занятий. Например, в описанном ниже примере расписания экзаменов, необходимо расставить 610 экзаменов. Необходимо наличие интервала между экзаменами каждой отдельной группы не менее 3 суток, причем каждые сутки содержат две смены для проведения экзаменов. Требуется выдержать интервал именно в календарных сутках, поэтому минимальное количество пропускаемых смен для группы варьируется от пяти до семи. Таким образом, каждый расставляемый в расписание экзамен группы связан с множеством расставляемых для него пропусков, которые так же рассматриваются как расставляемые события, увеличивая первоначальное количество расставляемых событий, по крайней мере, в пять раз. Количество расставляемых занятий этой же формы обучения составило около двух тысяч.

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

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

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

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

1) разработка математической модели и методов формирования и оптимизации расписания экзаменов вуза с использованием критериев загруженности ресурсов и критериев равномерности;

2) разработка метода визуального представления информации в задаче формирования расписания экзаменов;

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

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

Объект исследования - расписание экзаменов вуза.

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

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

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

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

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

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

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

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

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

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

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

- программное обеспечение, формирующее расписание экзаменов вуза.

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

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

Основные результаты работы докладывались на XVI и XVII Международных конференциях «Информационные технологии в образовании» в 2006 и 2007 гг.

Публикации. По теме диссертации опубликовано 7 работ, в том числе одна в издании, рекомендованном в ВАК РФ.

Структура и объем работы. Диссертационная работа состоит из введения, трех глав и заключения, изложенных на 105 страницах, в том числе 18 рисунков, списка использованной литературы, включающего 83 наименования.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

5. Разработанное и внедренное в Саратовской государственной академии права и Московской медицинской академии им. И.М. Сеченова программное обеспечение позволяет полностью автоматизировать процесс формирования расписания экзаменов в составе интегрированной системы управления учебным процессом вуза.

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

7. Проведен анализ разработанных методов с использованием мультипликативных и аддитивных критериев равномерности, показавший эквивалентность применения обоих критериев.

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

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

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

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

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

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

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

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

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

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

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

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

13. Жданова Е.Г. Теория расписаний / Жданова Е.Г. — М.: МГУ, 1999. С. 11-16.

14. Зарубицкая Т.Ф. О подсистеме автоматизированного составления распи-саний учебных занятий / Зарубицкая Т.Ф., Самойленко А.Т. // Опыт разработки и внедрения АСУ ВШ в Киевском государственном университе-те. — М.: НИИВШ, 1976. С. 35-40.

15. Зенкин А.А. Когнитивная компьютерная графика / Зенкин А.А. // Под ред. Д.А.,Поспелова. М.: Наука, Гл. ред. физ.-мат. лит., 1991. - С. 23-24.

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

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

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

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

20. Рубцов О.Г. Модели и методы многокритериальной оптимизации распи-саний вуза/ Н. Н. Клеванский, А. А. Пузанов, О.Г. Рубцов // «Вестник Саратовского государственного технического университета». 2006. № 4 (17) вып. 2, С.76 82.

21. Рубцов О. Г. Тестовые задания и алгоритмы составления расписания экзаменов / Н. Н. Клеванский, А. В. Свиридов, О. Г. Рубцов //Математические методы в технике и технологиях: сб. трудов XIX

22. Междунар. науч. копф. Воронеж: ВГТА, 2006. С.112 114.

23. Рубцов О.Г. Тестовые задания для расписания экзаменов вуза./ Н.Н. Клеванский, О.Г. Рубцов // Техническая кибернетика, радиоэлектроника и системы управления: VIII Всерос. науч. конф. студентов и аспирантов Таганрог: ТГРТУ, 2006. С.81 82.

24. Рубцов О.Г. Формирование начальных расписаний экзаменов / Н.Н. Клеванский, О.Г. Рубцов // ИКТ в управлении образованием: XVII Меж-дунар. конф. «Информационные технологии в образовании» («ИТО-2007»): в 6 ч. — М.: МИФИ, 2007. 4.V. С.47.

25. Рубцов О.Г. Оптимизация начальных расписаний экзаменов / Н.Н. Клеванский, О.Г. Рубцов // ИКТ в управлении образованием: XVII Междунар. конф. «Информационные технологии в образовании» («ИТО-2007»): в 6 ч. М.: МИФИ, 2007. 4.V. С.48.

26. Ламан К. Применение UML и шаблонов проектирования / Ламан К. // Пер. с англ.: Уч. Пос. М.: Издательский дом «Вильяме», 2001. - С. 395-399.

27. Ласло М. Вычислительная геометрия и компьютерная графика на С++ / Ласло М. //: Пер. с англ. М.: «Издательство БИНОМ», 1997. - С. 27-30.

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

29. Матросов А.В. MS Office ХР: разработка приложений / Матросов А.В., Новиков Ф.А., Усаров Г.Е., Харитонова И.А. / Под ред. Ф.А. Новикова. -СПб.: БХВ Санкт-Петербург, 2003. - 944 с.

30. Молибог А.Г. Методика составления расписания занятий на ЦВМ / Мо-либог А.Г., Медведский М.В., Неверов Г.С. -МВИРТУ, 1972.

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

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

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

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

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

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

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

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

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

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

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

42. 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.

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

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

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

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

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

48. 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.

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

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

51. 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.

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

53. 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.

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

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

56. Dimopoulou M. Implementation of a university course and examination time-tabling system / Dimopoulou M., Miliotis P. // European Journal of Opera-tional Research. 2001. V. 130, N. 1. P. 202-213.

57. Dixon L.C.W. Towards Global Optimization / Dixon L.C.W., Szego G.P.//North-Holland, 1975.

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

59. Elmohamed M.A.S. A Comparison of annealing techniques for academic course scheduling / Elmohamed M.A.S., Coddington P. Fox G. // in: E. Burke, M. Carter, The Practice and Theory of Automated Timetabling: Selected Pa-pers

60. РАТАТ '97). Lecture Notes in Computer Science, V. 1408, Springer-Verlag, Berlin Heidelberg, New York, 1998. P. 92-112.

61. 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. 691703.

62. Feldman R. Optimization algorithms for student scheduling via constraint sati-ability / Feldman R., Golumbic M.C. // The Computer Journal. 1990. V. 33, N. 4.

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

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

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

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

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

68. 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.

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

70. 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.

71. 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.

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

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

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

75. 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 A A AI-94, Seattle, 1994.

76. 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.