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

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

КОСТИН Станислав Анатольевич

МОДЕЛИ И МЕТОДЫ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ НАЧАЛЬНОГО РАСПИСАНИЯ ЗАНЯТИЙ

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

АВТОРЕФЕРАТ

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

Саратов 2005

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

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

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

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

доктор технических наук, профессор Кузнецов Вадим Викторович доктор физико-математических наук, профессор Дудов Сергей Иванович

Саратовский государственный социально-экономический университет

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

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

Автореферат разослан «г/ » ноября 2005 года.

Ученый секретарь Jk^ZI

диссертационного совета А. А. Большаков

¿253530

3

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

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

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

Получаемое на каждом этапе расписание занятий должно быть непротиворечивым, то есть соответствовать обязательным ограничениям (академическая группа может находиться только на одном занятии в одно и то же время; преподаватель не может проводить более одного занятия одновременно и др.) и желательным ограничениям (например, отсутствие у группы дней с одной «парой» занятий, недопустимость возникновения «окон» в расписании групп и т.п.). Количество и качество этих ограничений существенно влияет на возможность и трудоемкость получения решения. Ряд авторов (В.П. Ерунов, В.А. Костенко, Э.А. Мухачева, Е.Р. Пантелеев, Е.К. Витке и др.) рассматривают указанные ограничения в виде набора критериев оптимальности, приводя тем самым проблему составления расписания занятий к задаче многокритериальной оптимизации. При этом, как правило, учитываемым критериям придаются статические неизменные веса, что приводит в ряде случаев к приемлемым вариантам расписаний.

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

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

расписания занятий вуза;

- реализация алгоритма оптимизации расписания;

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

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

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

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

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

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

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

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

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

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

- применен градиентный подход для предложенного метода многокритериальной оптимизации;

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

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

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

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

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

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

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

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

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

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

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

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

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

Основные результаты работы докладывались на XV Международной конференции «Применение новых технологий в образовании» (г. Москва, 2004), ХЩ, XTV и XV Международных конференциях-выставках: «Информационные технологии в образовании» (г. Москва, 2003, 2004, 2005).

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

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

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

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

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

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

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

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

- не выявлены исследования по созданию тестовых заданий для задачи составления расписания занятий вуза.

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

Пусть р - преподаватель, g - учебная группа и О - множество всех групп. Обозначим через *л>к количество занятий группы (согласно учебному плану) за две недели. Лекционные занятия проводятся в потоках. Введем множество потоков К, состоящее из всех потоков расписания г. Для проведения лабораторных занятий студенты каждой группы делятся на подгруппы <1. Обозначим множество О, состоящее из всех подгрупп ¿/е£>. Аш - множество аудиторий для лекций и практических занятий, АтБ -множество аудиторий для лабораторных занятий, а е Аш и А^ - обозначение аудитории, а | Ат | +1А^ | - количество аудиторий в вузе. Занятия проводятся в учебные дни в полуторачасовые интервалы, которые будем называть «парами». 1деТд- рабочий день недели, еТп - номер «пары»,

Тч = , ^} - множество признаков недели (четность недели). Введем множество таймслотов Т = ТдхТпхТч, элементы которого однозначно определяют четность, день недели и номер «пары».

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

Введем булево обозначение учебной «пары» $ е5:

где -вид занятия.

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

2

/ t

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

5> + 5>:ге<?} + (2)

ггеЯ $ г.геО

В каждом таймслоте преподаватель р может вести не более одного занятия по одной дисциплине на одном потоке, в одной группе или подгруппе: ЫУр + + (3)

гзеЯ g г:ге£>

В любом таймслоте в аудитории не может проходить более одного занятия:

$ глей

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

V/ 2> + 2>:"<3}*ки7|. (5)

ггеЯ в * '

V* (6)

Наконец, расписание занятий для каждой группы не должно содержать «окон». Обозначим через jml¡1L номер последнего занятия группы g в день <,з недели /ч:

^ = тах{г„: 5 = 1}.

Аналогично определим номер первого занятия :

Vg,Víд,Ví1( Упид = тт{<„ : я = 1}.

Узнаем количество «пар» занятий у группы g в день гд недели ?ч:

Vg,V/afV^1 У», 2« Л}+ ^---.

т ~

Тогда искомое ограничение примет следующий вид:

Vg, ,1V/, ]шх - у'пип - )С01 = 0 (7)

Желательные ограничения.

Минимизация количества занятий для заданного номера «пары» 1'п е Тп:

\*\ЗС„еТп 2> + 2>:*е<7}+ 2>-ишп[. (8)

( ггеЛ g ггеО ]

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

2>

Т,

• тш У. (9)

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

—> min

(10)

Постановка задачи многокритериальной оптимизации расписания занятий вуза: в заданном расписании НРАСП, учитывая желательные критерии оптимальности (8 - 10) и не нарушая ограничения (1 - 7), произвести такие изменения, чтобы полученное решение Н'РАСП в любом случае улучшало качество расписания НРАСП по Парето.

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

Рис. 1. Метод многокритериальной оптимизации расписания занятий

Положим, что имеется I критериев оптимальности, причем каждый из них характеризуется числовым значением К,, /б[1,/]. Пусть значения критериев для каждого занятия приведены к безразмерному типу при помощи линейной функции нормированных показателей качества:

Ff

■К?

где К*- текущее значение г-го критерия для оцениваемого занятия; А'1тах~ максимально возможное значение г-го критерия; С"- минимально возможное значение г-го критерия; К™* ¿К? ¿К™;

(П)

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

, (12)

I

где е,,1е [0,7] - весовые коэффициенты, =1.

I

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

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

"-й- (,3>

I

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

Интегральная оценка расписания, показывающая разницу между текущим и «идеальным» расписанием занятий, определяется следующим выражением:

04)

3 г

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

При нормировании критерия К1 принимается, что: /Г1та*=1, если в

выбранном таймслоте ^ е Тп есть занятие, и К1ШШ = 0 - если занятия нет. Следовательно, для этого критерия выражение (11) примет следующий вид:

1 1-0 1 1, если в таймслоте есть занятие на выбранной «паре»;

где к; = ,

0, в противном случае Оптимальное количество занятий группы в день уеУ (критерий К2) вычисляется делением общего количества занятий группы на количество учебных дней для обеих недель расписания.

Г =

{У\}: У] =¿77 01V \Тд|, если ¿-1-Мой |ГД| = 0;

Ы |Л|' \ТЧ

где |5| - число занятий группы за обе недели расписания;

{У\,Уг)-Ух = й |ГД I" Л = * + есш ЙМо(* 1ГДI>0'

Иу| КУ!

\ТД I - количество учебных дней недели; ¡7^1- количество недель расписания;

О/у - оператор, определяющий целочисленное частное от деления двух чисел; Мой - оператор, определяющий целочисленный остаток от деления двух чисел.

В этом случае К™п принимается равным 0, а максимальное и текущее значение вычисляется как:

КГ = тах{|Гл| - тах{>< е У},тш{>< еУ}- тах{0,|5| + \ТП\- |Г|}}, О, если Эу е У х = у; х - тах{.у е У}, если х > так{у е У}; тш{.уе У}-*, если х < пип{>,е У},

где х- количество «пар» дня недели оцениваемого занятия; ¡Г|- количество всех таймслотов в расписании группы; \Т„\- максимальное количество «пар» расписания в день.

Оптимальное количество занятий группы на одной неделе расписания уеУ (критерий К3) вычисляется делением общего количества занятий группы на количество недель расписания.

{.у,}: ух = |S| Drv \ТЧ |, если |5| Mod \ТЧ | = 0; {УиУ2}-У1 =\S\Div\T4\u у2 = yl +l,eaiu\S\Mod\ТЧ\> 0. В этом случае ЛГ^™ принимается равным 0, а максимальное и текущее значение вычисляется как:

VV1D1

КГ - max{min{|i,|5|} - maх{у е Y},nm{y е У} - max{0,|S| - J1}},

къ =

0,если3уе¥ х = у;

x-maxfj' е У}, если х > тах{уе У};

min(>» е Y}-x, если х <min{y е У},

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

В данной работе представлен и исследован эвристический алгоритм преобразования начального расписания НРАСП в расписание Н'РАСП, оптимальное по Парето и имеющее минимальное значение интегральной оценки расписания (14).

Введем соответствующие операции преобразования расписания НРАСП в НрАСП

1 0\($,а) - операция изменения у занятия 5 е 5 учебной аудитории аъАт. Отметим, что эта операция изменяет аудитории только у лекционных и практических занятий.

2. 02(5, г) - операция изменения таймслота * б Т у занятия 5 е 5.

В множественно-графовой интерпретации операция О1 заменяет вершину а в ребре на вершину а'. Аналогично в операции 02 происходит

замена вершины г в ребре на вершину

Каждому переставляемому занятию с в соответствии с его идентификатором присваивается битовое значение следующим образом: I -занятие изменено к данному моменту времени, 0 - занятие осталось без изменения, и обозначим Н° общее состояние расписания после изменения занятия с, Н° =НРАСП.

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

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

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

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

На этапе 2 для выбранного занятия с алгоритм находит все корректные варианты его изменения, используя систему операций О = {01,02}.

Множество возможных решений является множеством вариантов изменения занятия с, которое можно назначить из текущего состояния с — 1

расписания Я . Далее, из множества возможных вариантов изменения

занятия выделяется подмножество Vе, которое состоит из вариантов

изменения занятия с удовлетворяющих аксиоме Парето. Каждый конкретный

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

назначаемых вариантов изменения занятия. Каждое следующее состояние расписания получается из предыдущего исходя из соотношения:

Я^-и^Я*-1).

с—1

Например, имеем вариант расписания Я и некоторое занятие с, которое необходимо оптимизировать. Пусть интегральная оценка расписания с—1

Я будет равной 131,1 (номер 4 в табл. 1).

Выделим подмножество Парето-оптимальных вариантов изменения занятия с : Vе - {1,2}. Отметим, что первый вариант имеет меньшую интегральную оценку расписания.

Таблица 1

Значения критериев оптимальности возможных решений

Варианты изменения занятия с Значения критериев оптимальности Интегральная оценка расписания

Кг Къ

1 67 27,5 33,6 128,1

2 67 26,5 35,1 128,6

3 67 26,5 36,6 130,1

4 68 26,5 36,6 131,1

5 68 28,5 36,6 133,1

6 68 26,5 35,1 129,6

После второго этапа оптимизации расписания имеем подмножество вариантов изменения занятия 17е. Каждому варианту соответствует расписание

Н^ и некоторое значение приращения оптимальности интегральной оценки расписания:

На 3 этапе Парето-оптимальное подмножество Vе упорядочивается так,

чтобы значение приращения оптимальности АЕ^ было максимальным.

Следовательно, выбираемому наилучшему варианту изменения занятия будет

соответствовать расписание Н^. Остальные варианты изменения занятия

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

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

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

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

Эвристика частного случая метода условного градиента оптимизирует расписание занятий с полиномиальной эффективностью, так как реализована на основе алгоритмов сортировки и поиска.

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

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

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

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

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

- одна группа - один преподаватель;

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

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

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

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

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

. 1' • '

Рис 3 Множество выбираемых решений при использовании динамичных весов

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

Результаты серии оптимизаций одного и того же начального расписания с использованием статичных и динамичных весов приведены в табл 2 Начальное расписание имело интегральную оценку 137,8 (значение критерия АТ, - 69, Кг - 30,5, Къ - 38,3).

Таблица 2

Серия оптимизаций

Варианты полученных расписаний Значения критериев оптимальности Интегральная оценка расписания Весовые коэффициенты

к, к2 К3

1 40 3 1,5 44,5 динамические

2 40 3,5 1,5 45 статичные (0,8; 0,1; 0,1)

3 41 2 3 46 статичные (0,1; 0,8; 0,1)

4 43 3 0 46 статичные (0,1; 0,1; 0,8)

Рис. 4. Множество решений

На рис. 4 показаны значения критериев оптимальности полученных вариантов расписания. Множество Парето-оптимальных решений состоит из 1, 3 и 4 вариантов расписания. Отметим, что вариант 1, полученный с

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

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

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

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

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

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

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

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

6. Проведен ряд экспериментов с определением экстремальных состояний расписания по выбранным критериям оптимальности.

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

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

2. Костин С.А. Использование геометрических критериев при моделировании и разработке учебных планов ВУЗ'а / H.H. Клеванский, C.B. Наумова,

С.А. Костин // Прикладные проблемы образовательной деятельности' межвуз. сб. науч. тр. Воронеж: ВГПУ, 2003. - С.74-78.

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

4. Костин С.А. Анализ геометрических критериев для моделирования и разработки учебных планов вуза / H H. Клеванский, C.B. Наумова, С.А. Костин // Совершенствование подготовки учащихся и студентов в области графики, конструирования и стандартизации: межвуз. науч.-метод сб. Саратов: СГТУ, 2003. - C.I25-130.

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

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

7. Костин С.А. Разработка средств визуального моделирования расписания занятий / H.H. Клеванский, С.А. Костин, A.A. Пузанов // Информационные технологии в науке, образовании и производстве (ИТНОП): материалы Международной научно-технической конференции. - Орел: ОрелГТУ, 2004. Т.4. - С.88-90.

8. Костин С.А. Генерация тестовых заданий для систем автоматизированной подготовки расписания занятий ВУЗ'а / H.H. Клеванский, С.А. Костин, A.A. Пузанов И Образовательные технологии: межвуз. сб. науч. тр. Воронеж: ВГПУ,2004.-С. 161-164.

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

Ю.Костин С.А. Использование когнитивной компьютерной графики при моделировании расписания занятий / H.H. Клеванский, С.А. Костин, A.A. Пузанов // Пути повышения эффективности учебно-воспитательного процесса: материалы межрегиональной научно-практической конференции.-Шадринск, 2004. - С.72-76.

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

12.Костин С.А. Модели и алгоритмы глобальной оптимизации первоначального расписания занятий ВУЗ'а / H.H. Клеванский, С.А. Костин //

Информационные технологии в образовании: материалы XIV Международной конференции. - М.: МИФИ, 2004. Ч. IV - С.30-31.

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

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

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

Подписано в печать 18.11 05 Формат 60x841/16

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

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

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

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

Ks 2 5 4 3 7:

РНБ Русский фонд

2006-4 28067

СОДЕРЖАНИЕ.

ВВЕДЕНИЕ.

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

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

Общая характеристика задачи.

Подходы к формализации и точные методы генерации расписаний .14 Эвристические методы генерации расписаний.

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

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

Особенности решения задач оптимизации расписания.

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

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

Векторные критерии оптимальности.

Принцип Эджворта-Парето.

Методы свертывания векторного критерия.

Способы назначения весовых коэффициентов.

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

2. РАЗРАБОТКА МЕТОДА ОПТИМИЗАЦИИ РАСПИСАНИЯ ЗАНЯТИЙ

ВУЗ'А И МОДЕЛИРОВАНИЕ ХАРАКТЕРИСТИК УЧЕБНЫХ ПЛАНОВ.

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

Интегральная оценка расписания.

Метод решения поставленной задачи.

2.2. Аналитическое исследование характеристик учебных планов.

Источник статистической информации.

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

2.3 Формирование тестовых заданий и их визуализация.

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

Графическая визуализация формирования расписания занятий.

3. ПРИМЕНЕНИЕ МЕТОДА МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ РАСПИСАНИЯ ЗАНЯТИЙ ВУЗ'А.

3.1. Оценка качества начальных расписаний.

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

3.3. Анализ многокритериальной оптимизации расписания.

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

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

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

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

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

- оценку полученного множества решений и выбор наиболее приемлемого.

Получаемое на каждом этапе расписание занятий должно быть непротиворечивым, то есть соответствовать обязательным (hard) ограничениям:

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

- ни один преподаватель не может проводить более одного занятия одновременно;

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

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

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

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

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

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

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

- разработка метода многокритериальной оптимизации начального расписания занятий ВУЗ'а;

- реализация алгоритма оптимизации расписания;

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

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

Объект исследования - расписание занятий ВУЗ'а. Предмет исследования - многокритериальная оптимизация начального расписания занятий ВУЗ'а.

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

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

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

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

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

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

- применен градиентный подход для предложенного метода многокритериальной оптимизации;

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

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

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

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

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

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

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

Основные результаты работы докладывались на XV Международной конференции «Применение новых технологий в образовании» (г. Москва, 2004), XIII, XIV и XV Международных конференциях-выставках: «Информационные технологии в образовании» (г. Москва, 2003, 2004, 2005).

Публикации. По теме диссертации опубликовано 14 работ общим объемом 2 печатных листа.

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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. С. 55-63.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

51. Dimopoulou M. Implementation of a university course and examination timetabling system / Dimopoulou M., Miliotis P. // European Journal of Operational Research. 2001. V. 130, N. 1. P. 202-213.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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