Automation of technological and business processes

ISSN-print: 2312-3125
ISSN-online: 2312-931X
ISO: 26324:2012
Архiви

Використання генетичного алгоритму для вирішення задачі формування розкладу навчальних занять

##plugins.themes.bootstrap3.article.main##

O. Sakaliuk
F. Trishyn

Анотація

Формування розкладу занять є вкрай важкою, трудомісткою задачею і зазвичай займає багато часу. У багатьох закладах освіти розклад занять розробляється вручну. Теорія розкладу включає проблеми, які насправді є менш складними, ніж проблеми на практиці, але теоретичний аналіз дає фундаментальне розуміння складності розкладу. Логічним результатом є те, що розклад на практиці дуже важко побудувати внаслідок багатьох різних обмежень [1].


Складання розкладу навчальних занять є проблемою планування. У 1996 році проблему розкладу було описано як розміщення деяких ресурсів з обмеженнями на обмежену кількість часових інтервалів і при цьому максимально задовільнити набір заявлених цілей [2]. Це загальне твердження і є загальноприйнятим описом проблеми формування розкладу навчальних занять. Розклад навчальних занять є важливою адміністративною діяльністю у більшості закладів освіти. Проблема розкладу полягає у розподілі занять по наявним аудиторіям та часовим інтервалам з урахуванням обмежень. Зазвичай ми розрізняємо два типи обмежень: жорсткі та м'які. Жорсткі обмеження обов’язково виконуються закладом освіти. Рішення, що не порушують жорстких обмежень, називаються можливими рішеннями.


З розвитком загальної теорії розкладу змінювалися і підходи до формалізації та вирішення задачі формування розкладу занять у закладах освіти. В даний час проблема автоматизації формування розкладу навчальних занять залишається відкритою. Актуальність завдання визначається зростанням вимог до якості навчання, планування роботи студентів, раціонального використання аудиторного фонду, а також урахуванням додаткових параметрів оптимізації. Завдання знаходження оптимального розкладу занять в більшості випадків відноситься до класу складних завдань. Якщо враховувати реальні умови, то завдання ще більш ускладнюється, оскільки шукані рішення повинні задовольняти великій кількості обмежень виробничого, організаційного та психофізіологічного характеру, які суперечать один одному. Генетичний алгоритм допомагає проводити ефективний пошук оптимальних розв’язків у просторах з дуже великою розмірністю.

Ключові слова:
автоматизація, генетичний алгоритм, кросинговер, мутація, оптимізація, планування, система автоматизованого керування

##plugins.themes.bootstrap3.article.details##

Як цитувати
Sakaliuk, O., & Trishyn, F. (2021). Використання генетичного алгоритму для вирішення задачі формування розкладу навчальних занять. Automation of Technological and Business Processes, 13(2), 22-28. https://doi.org/10.15673/atbp.v13i2.2053
Розділ
АВТОМАТИЧНІ І АВТОМАТИЗОВАНІ СИСТЕМИ УПРАВЛІННЯ ТЕХНОЛОГІЧНИМИ ПРОЦЕСАМИ

Посилання

[1]. Irving van Heuven van Staereling, "School Timetabling in Theory and Practice", pp. 1-42, 2012. [Online]. Available: https://beta.vu.nl/nl/Images/werkstuk-heuvenvanstaerelingvan_tcm235-317648.pdf. [Accessed: Aug. 03. 2020].
[2]. S. Petrovic and E. Burke, "(PDF) University timetabling", ResearchGate, 2004. [Online]. Available: https://www.researchgate.net/publication/235439172_University_timetabling. [Accessed: Aug. 06. 2020].
[3]. O. Sakaliuk and F. Trishyn, "ANALYSIS OF PROCESS CREATION OF THE COURSES TIMETABLING", Automation of technological and business-processes, vol. 11, no. 2, pp. 30-35, 2019. DOI:10.15673/atbp.v11i2.1370.
[4]. "Genetic Algorithm", IUPAC Compendium of Chemical Terminology. DOI:10.1351/goldbook.gt06961.
[5]. S. Al-Yakoob and H. Sherali, "Mathematical programming models and algorithms for a class–faculty assignment problem", European Journal of Operational Research, vol. 173, no. 2, pp. 488-507, 2006. DOI:10.1016/j.ejor.2005.01.052.
[6]. S. MirHassani, "A computational approach to enhancing course timetabling with integer programming", Applied Mathematics and Computation, vol. 175, no. 1, pp. 814-822, 2006. DOI:10.1016/j.amc.2005.07.039.
[7]. K. Zervoudakis and P. Stamatopoulos, "A Generic Object-Oriented Constraint-Based Model for University Course Timetabling", Lecture Notes in Computer Science, pp. 28-47, 2001. DOI:10.1007/3-540-44629-x_3.
[8]. J. Lions, "Matrix reduction using the Hungarian method for the generation of school timetables", Communications of the ACM, vol. 9, no. 5, pp. 349-354, 1966. DOI:10.1145/355592.365637.
[9]. A. Dandashi and M. Al-Mouhamed, "Graph Coloring for class scheduling", ACS/IEEE International Conference on Computer Systems and Applications - AICCSA 2010, 2010. DOI:10.1109/aiccsa.2010.5586963.
[10]. Y. Wang, Y. Cheng, T. Chang and S. Jen, "On the application of data mining technique and genetic algorithm to an automatic course scheduling system", 2008 IEEE Conference on Cybernetics and Intelligent Systems, 2008. DOI:10.1109/iccis.2008.4670852.
[11]. T. Islam, Z. Shahriar, M. Perves and M. Hasan, "University Timetable Generator Using Tabu Search", Journal of Computer and Communications, vol. 04, no. 16, pp. 28-37, 2016. DOI:10.4236/jcc.2016.416003.
[12]. D. Li, J. Shen, H. Dong, Y. Su and Z. Zhang, "Application of Genetic Algorithm and Simulated Annealing Algorithm for Course Scheduling Problem", Proceedings of the 2019 International Conference on Modeling, Analysis, Simulation Technologies and Applications (MASTA 2019), 2019. DOI:10.2991/masta-19.2019.69.
[13]. M. Basu, "Hopfield neural networks for optimal scheduling of fixed head hydrothermal power systems", Electric Power Systems Research, vol. 64, no. 1, pp. 11-15, 2003. DOI:10.1016/s0378-7796(02)00118-9.
[14]. M. Aldasht, M. Alsaheb, S. Adi and M. Qopita, "University Course Scheduling Using Evolutionary Algorithms", 2009 Fourth International Multi-Conference on Computing in the Global Information Technology, 2009. DOI:10.1109/iccgi.2009.15.
[15]. O.M. Boiko, "Evoliutsiina tekhnolohiia rozv’yazuvannia zadachi skladannia rozkladiv navchalnykh zaniat", Yskusstvennyy yntellekt, № 3, s. 341-348, 2006. [Elektronnyi resurs]. Rezhym dostupu: http://iai.dn.ua/public/JournalAI_2006_3/Razdel5/01_Boyko.pdf. [Data zvernennia: Kvi. 25. 2021].
[16]. V.A. Turchyna, D.O. Tanasiienko, "Zastosuvannia henetychnoho alhorytmu do zadachi skladannia navchalnoho rozkladu", Pytannia prykladnoi matematyky ta matematychnoho modeliuvannia, t. 18, s. 196-201, 2018. DOI:10.15421/321820.
[17]. A. Colorni, M. Dorigo, V. Maniezzo, "Colorni, Alberto, Marco Dorigo, and Vittorio Maniezzo. "A genetic algorithm to solve the timetable problem", Politecnico di Milano, s. 1-24, 1992. DOI:10.15421/321820. [Online]. Available: https://www.academia.edu/download/33105221/download.pdf. [Accessed: Apr. 25. 2021].