Обзор и анализ существующих методов составления расписания занятий
151 182
Ключевые слова:
UCTP, методы построения таблиц, мета-эвристика, гиперэвристика, комбинаторная оптимизация.Аннотация
Одним из важных шагов в организации эффективности использования качественного и научно-педагогического потенциала учебного процесса в образовательных учреждениях является задача формирования качественного расписания занятий. Качественно составленное расписание занятий должно обеспечивать равномерную загрузку студенческих групп и преподавательского состава.
Проблема планирования университетских курсов (UCTP) – это конкретная проблема планирования курсов в университете при одновременном использовании таких ресурсов, как студенты, преподаватели и классы. Эти задачи считаются задачами неполиномиального времени (NP) и комбинаторной оптимизации (COP), что означает, что их можно решить с помощью алгоритмов оптимизации для получения необходимой таблицы. В университетах для решения проблем с расписанием использовалось несколько методов, и многие из них используют методы оптимизации.
В данной статье рассмотрены шесть способов решения задач расписания занятий в университетах: последовательный метод, кластеризация, ограничивающие методы, метаэвристика, обобщенный поиск, гибридные эволюционные алгоритмы, многомерные подходы, аргументация на конкретных примерах, гиперевристика, адаптивные подходы. Цель этой статьи – всесторонний обзор подходов к оптимизации для решения задач построения расписание занятий в университетах. Кроме того, при решении таких задач указываются принятые алгоритмы метаэвристической оптимизации. Кроме того, были разработаны методы анализа и измерения производительности решения путем представления часто используемых наборов контрольных данных.
Библиографические ссылки
REFERENCES
A. Bashab, A.O. Ibrahim, E.E. Abedelgabar, M.A. Ismail, A. Elsafi, etc., «A systematic mapping study on solving university timetabling problems using meta-heuristic algorithms», Neural Computing and Applications, vol.32, no.23, P. 17397–17432. – 2020.
J.S. Tan, S.L. Goh, G. Kendall and N.R. Sabar, «A survey of the state-of-the-art of optimization methodologies in school timetabling problems», Expert Systems with Applications, vol.165, Article no. 113943, – 2021.
M.C. Chen, S.L. Goh, N.R. Sabar and G. Kendall «A survey of university course timetabling problem: perspectives, trends, and opportunities», IEEE Access, vol. 9, P. 106515–106529. – 2021.
S. Mir Hassani and F. Habibi «Solution approaches to the course timetabling problem» Artificial Intelligence Review, vol. 39, no.2, P. 133–149. – 2013.
T. Arbaoui, «Modeling and solving university timetabling», PhD. Dissertation, the University of Technology Compienge. – 2014.
B.A. Aldeeb, N.M. Norwawi, M.A. Al-Betar and M.Z.B. Jali, «Solving university examination timetabling problem using intelligent water drops algorithm», in Int. Conf. on Swarm, Evolutionary, and Memetic Computing, Cham, Springer, P. 187–200. – 2014.
C.W. Fong, H. Asmuni, B. McCollum, P. McMullan and S. Omatu «A new hybrid imperialist swarm-based optimization algorithm for university timetabling problems» Information Sciences, vol. 283, P. 1–21. – 2014.
S. Kristiansen and T.R. Stidsen «A comprehensive study of educational timetabling-A survey», Department of Management Engineering, Technical University of Denmark, DTU Management Engineering Report, no.8, – 2013.
T. Muller «Real-life examination timetabling» Journal of Scheduling, vol. 19, no.3, P. 257–270. – 2016.
K. Kalita, R.K. Ghadai and S. Chakraborty «A comparative study on the metaheuristic-based optimization of skew composite laminates», Engineering with Computers, vol.38, P. 3549–3566. – 2022.
J. Henry Obit, «Developing novel meta-heuristic, hyper-heuristic and cooperative search for course timetabling problems», PhD Dissertation, University of Nottingham, Nottingham NG8 1BB, UK. – 2010.
E.A. Abdelhalim and G.A. El Khayat «A utilization-based genetic algorithm for solving the university timetabling problem» Alexandria Engineering Journal, vol. 55, no.2, P. 1395–1409. – 2016.
X.S. Yang «Swarm intelligence based algorithms: A critical analysis», Evolutionary Intelligence, vol.7, no. 1, P. 17–28. – 2014.
S.N. Tung, J.B. Jaafar, I.A. Aziz, H.G. Nguyen and A.N. Bui «Genetic algorithm for solving multi-objective optimization in examination timetabling problem», International Journal of Emerging Technologies in Learning, vol.16, no.11, P. 4–24. – 2021.
