Математическое моделирование формирования расписания экзаменов вуза тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Рубцов, Олег Геннадиевич

• Рубцов, Олег Геннадиевич
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Рубцов, Олег Геннадиевич

ВВЕДЕНИЕ.

ГЛАВА 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. Проведен анализ разработанных методов с использованием мультипликативных и аддитивных критериев равномерности, показавший эквивалентность применения обоих критериев.

Список литературы диссертационного исследования кандидат технических наук Рубцов, Олег Геннадиевич, 2008 год

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.