Модели и методы многокритериальной оптимизации начального расписания занятий тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Костин, Станислав Анатольевич

• Костин, Станислав Анатольевич
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Костин, Станислав Анатольевич

СОДЕРЖАНИЕ.

ВВЕДЕНИЕ.

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 печатных листа.

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

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

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Костин, Станислав Анатольевич

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Костин, Станислав Анатольевич, 2005 год

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.