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

• Галузин, Константин Станиславович
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Галузин, Константин Станиславович

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) и с помощью данного модуля решена задача составления оптимального учебного расписания с учетом нечетких предпочтений в данном образовательном учреждении.

Список литературы диссертационного исследования кандидат физико-математических наук Галузин, Константин Станиславович, 2004 год

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