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

Галузин Константин Станиславович

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ОПТИМАЛЬНОГО УЧЕБНОГО РАСПИСАНИЯ С УЧЕТОМ НЕЧЕТКИХ ПРЕДПОЧТЕНИЙ

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

программ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Галузин Константин Станиславович

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ОПТИМАЛЬНОГО УЧЕБНОГО РАСПИСАНИЯ С УЧЕТОМ НЕЧЕТКИХ ПРЕДПОЧТЕНИЙ

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

программ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

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

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

профессор Столбов В. Ю.

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

профессор Русаков Сергей Владимирович

кандидат физико-математических наук, доцент Деменев Алексей Геннадьевич

Ведущая организация: Пермский областной институт повышения

квалификации работников образования

Защита состоится 19 октября 2004 года в УУ ч. 00 мин. на заседании Диссертационного совета ДР 212.188.04 в Пермском государственном техническом университете по адресу: 614000, г. Пермь, Комсомольский проспект 29.

С диссертацией можно ознакомиться в библиотеке ПГТУ. Автореферат разослан «^У» сентября 2004 года.

Ученый секретарь диссертационного совета, доктор технических наук, профессор

Аношкин А.Н.

з

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность работы. В своей повседневной деятельности образовательные учреждения сталкиваются с необходимостью решения задачи составления оптимального расписания. На период 2001-2010 года правительством РФ принята Концепция модернизации российского образования, главной задачей которой является обеспечение современного качества образования. Согласно принятой Концепции в сфере образования проводятся изменения, усложняющие учебный распорядок образовательных учреждений и устанавливающие более жесткие требования к расписанию. Расписание должно учитывать большее количество ограничений различного вида, что связано с введением системы профильного обучения, учитывающей потребности рынка труда и цели заказчиков, планируемой оптимизацией учебной, психологической и физической нагрузки учащихся, внедрением интегрированных программ обучения. В связи с отмеченными изменениями составление качественного расписания вручную становится задачей неразрешимой, поэтому возникает необходимость применения подходов, основанных на современных методах математического моделирования и информационных технологиях. Большой вклад в теорию расписаний внесен В.С.Танаевым, Ю.Н.Сотсковым, ВАСтрусевич. Хорошо известны работы по составлению расписания таких отечественных авторов, как А.В.Куренков, Ю.С.Быков, Г.Б.Рубальский и др. Среди зарубежных ученых можно отметить труды P. Ross, E. Burke, R. Dechter, M. Marte, H. Rudova, M. Hofe, S. Petrovic. Существующие отечественные разработки по составлению учебного расписания («Мечта», «Пенал 3.10», «НИКА», «АСТРА», «АСПРУЗ», «АВТОР-2+» и другие) не всегда учитывают последние изменения в сфере образования и обычно не предусматривают возможностей оптимизации расписания, или не позволяют задавать критерий оптимальности произвольного вида с учетом специфики конкретного образовательного учреждения. За рубежом разработаны библиотеки алгоритмов комбинаторной оптимизации (ILOG Solver, CLAIRE Schedule) и большое количество программ (gp-Untis, Lantiv Timetabler 5.0, OROLOGIO 11, SPM 3.1, TABULEX 6.0, Turbo-Planer). Однако применение перечисленных библиотек для составления учебного расписания ограничено заложенными в них методами распространения ограничений, а готовые программные продукты ориентированы на западную систему образования и не способны учесть имеющуюся российскую специфику. Задача составления учебных расписаний отличается разнообразием ограничений и критериев оптимальности, поэтому алгоритм, решающий задачу в одном образовательном учреждении, может не работать в условиях другого. На практике востребована такая методика, которая, с одной стороны, является достаточно универсальной, а с другой - позволяет строить оптимальные расписания для конкретного учреждения. Из опыта решения задач составления расписаний известно, что такие задачи эффективно решаются при использовании экспертных знаний в процессе решения, что невозможно без применения современных математических методов. Поэтому создание

РОС. ЦАЦИОНЛЛиИАЯ

«МБЛНОТЕКА

ОЭ tw/f£T£

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

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

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

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

3) Реализация данной методики в виде модуля единой информационной системы «Школа».

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

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

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

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

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

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

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

Апробация работы. Отдельные этапы работы докладывались и обсуждались на международной научно-методической конференции «Проблемы непрерывного образования в системе обучения школа-вуз» (Пермь, 1999); научно-практической конференции «Управление качеством образования на муниципальном уровне» (Пермь, 1999); IV Сибирском конгрессе по прикладной и индустриальной математике (Новосибирск, 2000); X и XIII международных конференциях «Информационные технологии в образовании» (Москва, 2000,2003); VI международной летней школе-семинаре «Современные информационные технологии» (г. Браслав, Беларусь, 2003); городском научном семинаре «Компьютерное моделирование и прикладная математика» (Пермь, 2004). Работа докладывалась и обсуждалась в целом на расширенном семинаре кафедры математического моделирования систем и процессов Пермского государственного технического университета.

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

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы (114 наименований). В работе приводится 35 рисунков и 7 таблиц. Общий объем диссертации составляет 105 страниц.

Благодарности. Автор сердечно благодарит Петра Валентиновича Трусова за ценные рекомендации в ходе работы, Нину Валентиновну Волкову за живое участие и помощь при внедрении разработки в Лицее № 1, Анатолия Борисовича Беланкова за передачу личного опыта по разработке коммуникации по протоколу TCP/IP в параллельной версии алгоритма оптимизации.

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

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

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

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

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

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

Во второй главе дана математическая постановка задачи составления оптимального учебного расписания с учетом предпочтений. Имеющиеся ресурсы задаются в виде множеств О = {^,'1 = Я = =

Т= {1к!к = 1,Ыт} для групп, аудиторий и преподавателей, соответственно. Здесь Ыс- общее число учебных групп, обучающихся в образовательном учреждении, а соответствуют числу имеющихся аудиторий и

количеству ведущих занятия преподавателей. Обозначим количество учащихся в 1-ой группе - *£,(; вместимость ,)-ой аудитории - В

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

описывающего часовую сетку учебного расписания. Ячейки этой сетки пронумерованы (1-номер ячейки от начала часовой сетки), а с помощью задается время начала занятия, расставленного в 1-ую ячейку. Все занятия, которые нужно расставить в часовую сетку расписания, входят в учебный план = I = 1,Н0,р = 1,1^}, где общее число занятий у ¡-ой группы (за одну или две недели, в зависимости от длительности учебного расписания). С связана также информация о конкретном предмете и виде занятия (лекция, практика). С помощью N = в задаче обозначается общее число занятий всех учебных

групп по учебному плану Ь. Кроме того, ресурсы могут быть недоступны в течение одного или нескольких моментов времени, заданных часовой сеткой расписания Б, поэтому для каждого вида ресурсов вводится календарь доступности, например, (}* =||35|] = 1,Нц,1 = 1,м| - календарь аудиторий:

=1, если ]-ая аудитория доступна для занятий в 1- ый урок недели, и О,

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

<2Т =фи|к = ПЯ7,1 = Пм) И <2° = {(5°¡1 = 1ТЩ, 1 = Гм). Для учета сложного

распорядка учебного процесса (деление учебных групп на подгруппы, поточные лекции и т.д.) вводятся понятия обобщенных преподавателей, групп и аудиторий. Например, если занятия по иностранному языку у трех подгрупп одновременно ведут три преподавателя, то этих преподавателей можно считать одним обобщенным преподавателем, который проводит занятие с одной обобщенной группой, состоящей из трех подгрупп. Реальные ресурсы объединяются в обобщенные согласно распорядку учебного процесса, принятому в образовательном учреждении, и заданному распределению учебной нагрузки преподавателей по учебным группам. Поэтому способ объединения считается известным заранее. Принятый способ объелинения учитывается в задаче с помотттью множеств обобщенных групп 0 = {(}[ £0|1 = 1,РС}, а у д и преподавателей

при этом с помощью обозначим число

реальных ресурсов, входящих в соответствующий обобщенный ресурс, а с помощью РС,РК1РТ. - число обобщенных ресурсов соответствующего вида. Следует отметить, что - могут существовать такие индексы к!е[1,Рт]и что пересечение обобщенных преподавателей не пусто: Тм Л тк2 * 0. Подобное справедливо и для обобщенных групп, то есть могут существовать . На практике диспетчеры

часто используют так называемый последовательный метод составления расписания, когда сначала в сетку расписания расставляются, например, занятия по одному предмету, затем занятия по другому предмету. И хотя в некоторых задачах составления учебного расписания, например, в задаче составления экзаменов, затруднительно выделить этапы составления расписания (так как в этом случае обычно назначение аудиторий ведется одновременно с расстановкой экзаменов по времени), будем считать, что справедлива декомпозиция задачи составления оптимального учебного расписания на две подзадачи: расстановки занятий, из учебного плана в ячейки часовой сетки расписания и распределения аудиторий по занятиям в составленном расписании. В связи с принятой декомпозицией, для обобщенных аудиторий, в отличие от обобщенных групп и преподавателей, считается выполненным условие: УДе[1,Рц], ]2е[1,Рк]:

¿1^2 =>11^ П^2=0- Введем вектор параметров задачи х = (х1,х2,...,хм), каждой компоненте которого взаимно однозначно соответствует

одно занятие из учебного плана Ь Значение, которое принимает параметр х,, отвечает за время начала соответствующего занятия. Если занятие х, начинается в момент времени <1|,1€[1,М], то Х,=<1|. Таким образом, значения всех компонент вектора х однозначным образом задают вариант учебного расписания. Согласно принятой постановке задачи, в одном

занятии х, задействуются следующие ресурсы: один обобщенный преподаватель У, =Тк,8б[1,Ы],ке[1>Рт], где (У, - число реальных преподавателей, «входящих в обобщенного»; одна обобщенная 1руппа 2, =0^бе[1,Ы], 1 б[1,Р0]. Количество реальных аудиторий, требуемое для проведения занятий, задается множеством В = {Ь|,Ь2,...ЬМ}, элемент которого Ь^е^.Ы] задает число аудиторий, требуемое для проведения занятия х,. Реальные аудитории, требуемые для проведения занятия х(, выбираются только из соответствующей данному занятию обобщенной аудитории = ^, в е [1, N1} е [1, Ёц ]. Сформулируем жесткие требования непротиворечивости расписания:

1. В каждый момент времени преподаватель или группа могут быть заняты только в одном занятии (пример ограничения для группы):

УЗег.Укег^кг^-Хк)*«), 2 = {гб[1,К]8,е21},1=1,Кс. (1)

2. В каждый момент времени число занятых аудиторий не превышает числа доступных аудиторий: £С}и,8 = {5е[1,м]х, =(1,,>У, =1^},

КБ кеК

К = М^ДгкекД1 = 17М,] = Щ (2)

3. Группа помещается в аудиторию полностью:

е € W,: (гу|-0,8 = . (3)

4. Нагрузка учебной группы не превышает числа учебных часов в неделю: Ь|<МЛ = 1,Ы0. (4)

5. При проведении занятия число реальных преподавателей равно числу реальных аудиторий: 1 У,' = Ь,, в = 1, N. (5)

6. Каждый преподаватель или группа могут быть временно недоступны (пример ограничения для преподавателя).

V]е {х ееУг},Ур [1,М] <£ = 0}=> (х, -<1р)* 0,1 = 1,НТ. (6)

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

Фр(х)= шах(х])%Н-гшп(х;)%Н,£ = {гь[1,ы] I, еУД1е[1.ЫТ], (7)

где ¡-номер преподавателя, ре[1,МР]-номер нежесткого ограничения (ЫР-общее количество таких ограничений в задаче), <рр(х)-скалярная функция, отражающая смысл нежесткого ограничения, а %-операция целочисленного

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

Функция принадлежности нечеткого множества Цр(Ур.)1УреУр задается преподавателем, например, так, как показано на рис. 1.

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

и,(У,)

I \

04 \

02 •{ \

0 1 - - - - — » ■ « ♦ «

0 1 2 3 4 5 « у,

Рис. 1. Функция принадлежности цДур)

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

ограничения требуется задать норму и

относительную степень важности данного нежесткого ограничения е {"совсем_не_важно",,,не_важно","нейтрально","важно","очень важно"} Общий вид предпочтений в задаче составления учебного расписания записывается следующим образом:

С;=(с;,ар,8р)=(фр(х),цр(ур}ар,5ДуреУр,Ур = |срр(х)Ух^ре[1,ЫР] (8)

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

ф = (<РрМ.Ир(Урк.*ДуР е УР'УР = к (х^4р 6 М,], (9)

где = -группа частных критериев, описывающих интересы

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

где N2- число таких критериев. Обозначим множество всех оцениваемых вариантов расписаний с помощью X*. Результатом оценки какого-либо варианта расписания хеХ*по группам частных критериев р1 = Щ", р2 = являются два вектора, Г(,)(х) и Г(2)(х), соответственно, для интересов учащихся и преподавателей:

Г«(х)=(ц,(ф1(х))>И2(ф2(х));...,Цт(фМ1(х))). ^ (10)

Результатом оценки всех элементов множества X* являются два множества векторов ^ = |^'(х)|хеХ*} и = {^2'(х)хеХ*}, каждое из

которых соответствует одному обобщенному критерию. Упорядочим их лексикографически, то есть расписания упорядочиваются путем сравнения значений критериев, начиная с самого важного, и пронумеруем варианты расписаний натуральными числами П и ,¡1: ¡1 > ¡1, если

Теперь в качестве первого обобщенного критерия I, для заданного заранее варианта расписания х может быть принят, например, его номер в лексикографическом упорядочивании, который определяется по значению Г»>(х): 11(х<п>)=П>51б(1,Н,)х = х<">, (12)

где Ы*- общее число расписаний в X*. Аналогично определяется и второй обобщенный критерий 12(х). Введем множество допустимых расписаний Х0такое, что любой хеХ0 удовлетворяет жестким требованиям (1)-(6) и предпочтениям (8). С помощью введенных обобщенных критериев из множества допустимых расписаний Х0 можно выбрать подмножество ХР с Хп расписаний, оптимальных по Парето, которые составляют множество решений задачи. Таким образом, в качестве искомого оптимального решения X 6 X в данной работе понимается любой вектор х е ХР. Далее, считая, что ХР * 0 (такое предположение можно сделать, так как обычно имеется хотя бы один вариант расписания, составленный вручную, то есть Хо*0), требуется выбрать конкретное решение из нескольких. Выбор можно поручить диспетчеру, а можно сделать автоматически с помощью дополнительного критерия оптимальности. Например, в качестве дополнительного критерия можно выбрать следующий:

*еХР :1Ч*)=2>,1,(*) = тах(Г(х)), (13)

»1 ,еХр

где и Я.2 - веса, задающие важность каждого обобщенного критерия.

В третьей главе представлен алгоритм решения задачи. Поставленная задача (1)-( 13) является многокритериальной многофакторной задачей большой размерности. Решение поставленной задачи в полном объеме в значительной мере зависит от размерности задачи и ограничений и может занимать очень большое время даже на современных компьютерах. В связи с NP-трудностью задачи использовать алгоритм полного перебора не

представляется возможным. Поэтому для решения задачи будем пользоваться методами неполного перебора, опирающимися на экспертные знания (эвристические методы). В данной работе специфика конкретной задачи учитывается при построении критерия оптимальности, что позволяет использовать расчетный алгоритм для широкого круга задач составления учебного расписания. Для решения первой подзадачи (согласно декомпозиции) будем рассматривать вариант расписания х как точку в пространстве RN, и обозначим X** множество всех точек х, удовлетворяющих (1)-(6): X** = б RN,j = l,NMj, где N''-мощность конечного множества R**. Разработанный алгоритм состоит в следующем:

1. Задаем N** - требуемое число точек из X**. Здесь N** является параметром алгоритма. Как показали исследования, в зависимости от конкретной задачи значение может изменяться от двух до десяти тысяч, что позволяет найти точку, близкую к глобальному экстремуму.

2. С помощью подпрограммы поиска, основанной на методах распространения ограничений, находим N точек хеХ , разбросанных в пространстве RN (N-число компонент в векторе неизвестных) случайным образом. Подпрограмма позволяет равномерно распределить точки по указанному пространству, и эти точки являются начальным приближением для поиска х е XD.

3. Для отыскания решений применяется эвристический метод стохастического поиска, известный в зарубежной литературе под названием simulated annealing. Суть его заключается в следующем: точка х е X*" берется в качестве базисной, вокруг нее строится окрестность, в которой ищутся принадлежащие X** точки, где предпочтения (8) выполняются лучше, чем в базисной точке. Если хотя бы одна такая точка окрестности найдена, то вокруг нее снова строится окрестность, и проводится дальнейший поиск.

4. Все найденные т о в которых выполняется условие

составляют множество

5. Одновременно с этим все точки X€XD исследуются на Парето-оптимальность, и из них строится оптимальное по Парето множество

»

Рис.2. Образы множеств XD и ХР в пространстве критериев

решений ХР. По образам в пространстве критериев I(Xd) и 1(Хр), изображенным на рис. 2., легко восстанавливаются искомые множества.

6. По критерию(13), задавая X¡,i = l>2, выбираем единственное расписание*. Рис.2. Образы множеств XD и ХР в пространстве критериев

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

В четвертой главе описана реализация алгоритмов решения поставленной задачи. В качестве технологии реализации системы была выбрана модель сервера реляционной базы данных. Для реализации алгоритмов использован язык Visual C++. Устойчивость численной схемы гарантируется тем фактом, что большинство расчетов - целочисленные, и проверкой получаемых расписаний на допустимость. Поблочная отладка алгоритма на наборе тестовых задач способствует стабильной работе алгоритма. Дополнительно устойчивость численной схемы проверялась компиляцией на разных компиляторах (MS Visual C++, Gnu C++) и сравнением результатов расчетов при увеличении точности переменных. Сходимость алгоритма по вероятности к Парето-оптимальному множеству доказана математически. Устойчивость алгоритма по точке начального приближения объясняется природой стохастического поиска. Применение методов распространения ограничений для получения начального приближения улучшает работу алгоритма оптимизации, так как получаемые допустимые расписания по некоторым критериям оптимальности существенно превосходят расписания, которые могут быть получены случайно. Схематично принцип работы с разработанным программным обеспечением представлен на Рис.3

Рис.3. Схема работы модуля «Расписание».

Анализ результатов решения тестовых задач проведен на примере составления учебного расписания для Лицея №1 при ПГТУ. Данный алгоритм был реализован в виде модуля "Расписание" единой информационной системы "Школа" и протестирован на задаче составления

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

Рис.4. Оптимальность решений на различных этапах дискретной оптимизации

Точки группы 1 показывают оптимальность расписаний, полученных с помощью методов распространения ограничений, начиная со случайной точки. Точка, помеченная словом «Действующее», отражает степень оптимальности действующего в Лицее 1 расписания, составленного вручную. Точки группы 3 - расписания, полученные при оптимизации, начиная со случайных расписаний (Ряд 1). В четвертой группе показаны результаты оптимизации, где в качестве начального приближения было выбрано расписание, составленное вручную. Из рисунка видно, что составленное вручную расписание удалось оптимизировать как по критерию 1|(х), отражающему интересы учащихся (состоящему из четырех частных критериев), так и по критерию 1г(х), отражающему интересы преподавателей. В итоге критерий удалось улучшить более чем в два раза при

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

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

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

2) Разработан алгоритм решения задачи с возможностью автоматического ослабления ограничений и включения эвристик,

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

3) Методика составления оптимальных учебных расписаний реализована в виде модуля единой информационной системы «Школа», что облетает накопление и обработку большого количества информации, необходимого для составления оптимального расписания.

4) Проведено сравнение с другими методами и показана эффективность предлагаемого подхода.

СПИСОКОПУБЛИКОВАННЫХРАБОТ

1. Галузин К.С., Кулеш М.А Использование информационной системы «Школа» для составления учебного расписания образовательных учреждений.//Проблемы непрерывного образования в системе обучения школа-вуз: Труды международной научно-методической конференции. Пермь, 1999. С. 117-124.

2. Столбов В.Ю., Гитман М.Б., Галузин К.С. Информационная система «Школа» и ее возможности при оценке качества образования на муниципальном уровне//Управление качеством образования на муниципальном уровне: Материалы научно-практической конференции. Пермь, 1999. С.54-58.

3. Галузин К.С.,Клюев А.В., Столбов В.Ю., Трусов П.В. Информационная система управления муниципальным образовательным учреж-дением//Тезисы IV Сибирского конгресса по прикладной и индустриальной математике. Новосибирск,2000,ч.Г^ с. 124-125.

4. Галузин К.С. Информационная система управления муниципальным образовательным учреждением//Информационные технологии в образовании: Сборник трудов X международной конференции. Москва, 2000,4.^,0.11.

5. Галузин К.С, Столбов В.Ю. Разработка модуля для автоматизации составления оптимального учебного расписания в рамках единой информационной системы образовательного учреждения//Известия Белорусской инженерной академии,- 2003.-№1(15)/2.-С.90-92

6. Галузин К.С., Столбов В.Ю. Гибридный алгоритм решения задачи составления оптимального учебного расписания//Информационные технологии в образовании: Сборник трудов XIII международной конференции-выставки. Москва, 2003. с. 130-131.

7. Галузин К.С, Столбов В.Ю. Методика составления оптимального учебного расписания с учетом предпочтений//Теоретические и прикладные аспекты информационных технологий: Сб.науч.тр. /ГосНИИУМС Вып. 53. - Пермь, 2004. - С 43-50.

8. Галузин К.С,Волкова Н.В.,Столбов В.Ю.Автоматизированное составление оптимального учебного расписания в МОУ «Лицей №1» с учетом предпочтений учащихся и преподавателей//Социокультурная многомерность лицейского образования: Сб.науч.тр./МОУ «Лицей №1». -Пермь, 2004, -С.97-110.

Сдано в печать 10.09.04. Формат 60x84/16. Объём 1,0 п.л. Тираж 100. Заказ 1289.

Печатная мастерская ротапринта ПГТУ.

Р16644

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

1.1. Обзор существующих систем автоматизированного составления учебного расписания и классификация задач учебного расписания.

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

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

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

2.1. Декомпозиция задачи и выбор параметров оптимизации.

2.2. Ограничения в задаче оптимального учебного расписания для школ.

2.3. Построение обобщенных критериев оптимальности.

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

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

3.1. Обзор и классификация методов составления учебного расписания.

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

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

4. Реализация алгоритма в виде модуля информационной системы и решение тестовых задач.

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

4.2. Эвристические алгоритмы ослабления ограничений в модуле «Расписание» информационной системы «Школа».

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

4.4. Решение задачи составления оптимального учебного расписания школы с учетом нечетких предпочтений на примере МОУ «Лицей №1».

ограниченного набора периодов времени, может колебаться от пятисот для небольшой школы до трех тысяч для большого университета[27]. Известно, что задачи с большим числом ограничений являются очень сложными для решения вручную, поэтому в ВУЗах расписанием обычно занимаются диспетчерские службы (бюро расписаний), которые ведут деятельность по составлению и модификации расписания непрерывно в течение рабочей недели. Составлением расписания в школе обычно занимается отдельный диспетчер или завуч, выполняющий обязанности диспетчера. Процесс составления расписания длится от нескольких недель (для школ) до нескольких месяцев (для крупного ВУЗа). Кроме этого, к обязанностям диспетчера или диспетчерской службы относится составление расписания «замен», то есть внесение корректив в действуюш,ее расписание в случае ремонта аудиторий, временной нетрудоспособности преподавателей и иных причин. Следует отметить, что на период 2001-2010 года правительством РФ принята Концепция модернизации российского образования, главной целью которой является обеспечение современного качества образования. Согласно принятой Концепции учебный в сфере образования проводятся изменения, и усложняющие распорядок образовательных учреждений устанавливающие более жесткие требования к расписанию. Расписание должно учитывать большее количество ограничений различного вида, что связано с введением системы профильного обучения, учитывающей потребности рынка труда и цели заказчиков, планируемой оптимизацией учебной, психологической и физической нагрузки учащихся, внедрением интегрированных программ обучения. В частности, это выражается в потребности учитывать действующие нормы СаНПИН [10], деление учебных групп на подгруппы по профилю (в школе), наличие преподавателейсовместителей (преподающих профильные предметы в школе и имеющие основное место работы в ВУЗе). При составлении расписания диспетчеру необходимо учитывать дидактические требования по организации учебного процесса, указания администрации по распределению аудиторного фонда (и иных ресурсов, необходимых для реализации учебного процесса), а также личные пожелания преподавателей и учебных групп к составлению расписания. Помимо этого, специфика конкретного образовательного учреждения отражается в задаче составления расписания в виде специфичных целей и ограничений. В результате всего вышеизложенного, задача составления расписания становится очень сложной для решения вручную. В настояш;ее время при актуальности вопроса качества образовательных услуг и требований экономии ресурсов на практике востребовано не только составление некоторого «чернового» варианта расписания, но и получение оптимального (с точки зрения введенных критериев и имеющихся ограничений) либо близкого к оптимальному (по некоторой мере) расписания. И если составление расписания вручную является трудной и затратной по времени задачей, то решение задачи оптимизации учебного расписания вручную практически не реализуемо по следующим причинам: при составлении расписания вручную возможности перебора вариантов ограничены, а размерность вектора неизвестных в задаче велика; как указано в [50], даже опытный диспетчер единовременно не способен оценивать расписание более чем по 12 критериям, хотя в реальных задачах может быть востребован учет до 40 и более различных критериев оптимальности; в работе [24] отмечено, что реальные задачи составления расписания являются перегруженными ограничениями, поэтому диспетчер «отбрасывает» некоторые ограничения в ходе решения задачи, полагаясь на свой опыт и предпочтения, поэтому может действовать субъективно; для проверки оптимальности либо суб-оптимальности полученного расписания диспетчер не имеет никакого формального аппарата либо инструмента для исследования множества решений задачи;

Основные результаты работы заключаются в следующем:

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

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

3. Разработан гибридный алгоритм решения поставленной задачи, сочетающий методы распространения ограничений для поиска допустимых расписаний, и метода стохастического поиска, улучшающего найденные допустимые расписания по введенным критериям. В основе метода лежит принцип декомпозиции задачи на две части: поиска расписаний по времени с учетом вида и количества требуемых для занятий аудиторий, с последующим назначением аудиторий в составленном расписании методом ветвей и границ. Базовые версии алгоритмов распространения ограничений и методов стохастического поиска доработаны с использованием оригинальных эвристических алгоритмов, позволяющих в некоторых случаях существенно увеличить скорость поиска решения с 5 часов до 10-12 минут при снижении исходных требований к оптимальности расписания на 20%. Нечеткие множества расширяют пространство поиска, улучшают стабильность работы алгоритма на задачах с разными ограничениями и критериями оптимальности, не снижая точности получаемых результатов. Показано что нечеткие ограничения эффективны в использовании, если функции принадлежности нечетких множеств являются убывающими функциями. Логически показано, что добавление эвристик не нарушает в целом свойства сходимости алгоритма к решению по некоторой вероятностной мере.

4. Методика решения задачи реализована в виде модуля «Расписание» информационной системы «Школа», что облегчает накопление и обработку большого количества информации, необходимого для составления оптимального расписания. Показана эффективность предлагаемого подхода на примере решения задачи Лицея №1 г. Перми.

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

6. Разработанный модуль «Расписание» внедрен в Лицее №1 г. Перми (см. приложение 3) и с помощью данного модуля решена задача составления оптимального учебного расписания с учетом нечетких предпочтений в данном образовательном учреждении.

1. Алтунин А.Е., Семухин MB. Модели и алгоритмы принятия решений в нечетких условиях: Монография. Тюмень: Изд-во ТГУ, 2000. -352 с.

2. Амосов и др. Вычислительные методы для инженеров. -М.:ВШ, 1994.

3. Брюс Шнайер. Прикладная криптография: Протоколы, алгоритмы, исходные тексты на языке Си. -М., Триумф, 2002.

4. Галузин К.С., Столбов В.Ю. Гибридный алгоритм решения задачи составления оптимального учебного расписания//Информационные технологии в образовании: Сб. трудов XIII международной конференции-выставки. -М., 2003. С. 130-131.

5. Галузин К.С., Столбов В.Ю. Методика составления оптимального учебного расписания с учетом предпочтений/ЛГеоретические и прикладные аспекты информационных технологий: Сб.науч.тр. /ГосНИИУМС. -Вып. 53. Пермь, 2004. С. 43-50.

6. Галузин К.С., Столбов В.Ю. Разработка модуля для автоматизации составления оптимального учебного расписания в рамках единой информационной системы образовательного учреждения//Известия Белорусской инженерной академии. 2003. -№1(15)/2. -С.90-92.

7. Галузин К.С.,Клюев А.В., Столбов В.Ю., Трусов П.В. Информационная система управления муниципальным образовательным учреждением/Лез. IV Сибирского конгресса по прикладной и индустриальной математике. -Новосибирск,2000, 4.IV. С. 124-125.

8. Ю.Гигиенические требования к условиям обучения и общеобразовательных учреждениях: Санитарно эпидемиологические правила: СанПиН 2.4.2.1178-02 // Практика административной работы в школе.- 2003.- № 8.- С.4-21.

9. П.Джордж Ф. Люгер. Искусственный интеллект: стратегии и методы решения сложных проблем. 4-е издание. М., Вильяме, 2003.

10. Корнеев В.Д. Параллельное программирование в MPI. Новосибирск: Из-во СО РАН, 2000.

11. Пенал. Документация к системе составления расписаний. -Минск, 1991.

12. С.А. Орловский. Проблемы принятия решений при нечеткой исходной информации. -М., Наука. Главная редакция физико-математической литературы, 1981. -208 с.

13. Сергей Крылков. Формально-технологический подход //Компьютерра. -2002. №27. -С.24-27.

14. Сигад И.Х., Иванова А.П. Введение в прикладное дискретное програмирование. -М:Ф.-м., 2002.

15. Танаев B.C., Гордон B.C., Шафранский Я.М. Теория расписаний. Одностадийные системы. -М.: Наука, 1984.

16. A. Elkhyari, С. Gueret, N. Jussien "New tools for solving dynamic timetabling problems" Proceedings of the 4th International Conference on the Practice and Theory of Automated Timetabling (PATAT2002), Gent, 2002.

17. A. Jaszkiewicz, Multiple objective metaheuristic algorithms for combinatorial optimisation, Habilitation Thesis, 360, Posnan University of Technology ,Poznan, 2001.

18. Alan Borning, Michael Maher, Amy Martindale, and Molly Wilson Constraint Hierarchies and Logic Programming Technical Report 88-11-10 Computer Science Department University of Washington November 1988.

19. Amnon Meisels, Jihad Ell-sana' and Ehud Gudes "Decomposing and Solving Timetabling Constraint Networks", Dept. of Mathematics and Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, 84-105, Israel

20. Andrea Schaerf, A Survey of Automated Timetabling,Centrum voor Wiskunde en Informatica (CWI) report CS-R9567, Amsterdam, The Netherlands.

21. Bartak, R., in T. Grant, C. Witteveen, On Modelling Planning and Scheduling Problems with Time and Resources : Proceedings of the 21th workshop of the UK Planning and Scheduling Special Interest Group (PLANSIG), 2002, pp. 87-98.

22. Beck, J.C. "A Schema for Constraint Relaxation with Instantiations for Partial Constraint Satisfaction and Schedule Optimization" M.Sc. Thesis, University of Toronto, 1994. (also released as a technical report EIT-94-3)

23. Burke E.K., Petrovic S. Recent Research Directions in Automated Timetabling, EJOR ,2002

24. Вигке, E.K., Landa Silva, J.D., Soubeiga E., Hyperheuristic Approaches for Multiobjective Optimisation. Proceedings of the Fifth Metaheuristics International Conference (MIC 2003) Kyoto Japan, August 25-28, 2003.

25. Carlsson, R.Fuller , Multiple Criteria Decision Making: The Case for Interdependence, Computers&Operations Research, 22(1995),pp.251-260

26. Didier Dubois, Philippe Fortemps, Computing improved optimal solutions to max-min flexible constraint satisfaction problems, Universit'e Paul Sabatier, 31062 Toulouse Cedex — France

27. Dragan Cvetkovi'c and Ian C. Parmee Preferences and their Application in Evolutionary Multiobjective Optimisation, Vrlag,2002

28. E.K. Burke, J. Newall and R.F. Weare. A Memetic Algorithm for University Exam Timetabling, The Practice and Theory of Automated Timetabling (eds EK Burke and P Ross), Lecture Notes in Computer Science Vol. 1153, Springer 1996, pp. 241-250.

29. F. Herrera, E. Herrera-Viedma, Aggregation Operators for Linguistic Weighted Information. Technical Report #DECSAI-95120. October, 1995, University of Granada, 18071 Granada, Spain

30. Hana Rudova, Constraint Satisfaction with Preferences . Ph.D. thesis, Faculty of Informatics, Masaryk University, 2001.

31. Harald Meyer aufm Hofe. Nurse rostering as constraint satisfaction with Fuzzy Constraints and Inferred Control Strategies, In DIMACS Series in Discrete Mathematics and theoretical computer science, 2000, pages 257272.

32. J. Landa Silva, E. Burke "A tutorial on multiobjective metaheuristics for scheduling and timetabling", University of Nottingham, 2002

33. M. Kambi, D. Gilbert "Timetabling in Constraint Logic Programming" Department of Computer Science, The City University,London,1996

34. Pearl Pu, Denis Labanne Human and Machine Collaboration in Creative Design, ECAI96. 12th European Conference on Artificial Intelligence Edited by W.Wahlster, Published by John Wiley&Sons, 1996

35. R. Bartak, Dynamic Global Constraints in Backtracking Based Environments, Annals of Operations Research (2003), no. 118, p. 101-119.

36. R. J. Wallace and E. C. Freuder. Stable solutions for dynamic constraint satisfaction problems. In CP-97 Workshop on Theory and Practice of Dynamic Constraint Satisfaction, pp. 73—80, 1997.

37. Ralph L. Keeney Value-Focused Thinking : A Path to Creative Decisionmaking,The University of Southern California, 1992.

38. S. Abdennadher, M. Marte. University course timetabling using Constraint Handling Rules. Computer Science Department, University of Munich, 2000

39. S. Badaloni, M. Giacomin "Fuzzy extension of interval-based temporal sub-algebras", Proc. of 9th Information Processing and Management of Uncertainty in Knowledge-Based System Conference (IPMU 2002), 11191126, Annecy, France, July 2002.

40. Tim B. Cooper and Jeffrey H. Kingston The Complexity of Timetable Construction Problems Basser Department of Computer Science The University of Sydney , Australia, 2000

41. Wolfgang Slany, Scheduling as a fuzzy multiple criteria optimization problem, Appeared in Fuzzy Sets and Systems, 78:197—222, March 1996.

42. Yaochu Jin, Markus Olhover, Bernhard Sendhoff, Dynamic weighted Aggregation for Evolutionary Multi-Obkective Optimisation: why Does it Work and How, Future Technology Research ,Honda R&D Europe GmbH