Генетичний алгоритм оптимізації задачі автоматизованого планування розкладу занять

Abstract

У тезах розглянуто проблему автоматизованого планування навчального розкладу як складну NP-складну комбінаторну задачу оптимізації. Обґрунтовано доцільність застосування генетичного алгоритму як ефективного евристичного методу пошуку наближених до оптимальних рішень в умовах великої кількості обмежень.

The theses address the problem of automated timetable scheduling as a complex NP-hard combinatorial optimization task. The feasibility of applying a genetic algorithm as an effective heuristic method for searching near-optimal solutions under numerous constraints is substantiated. Particular attention is paid to the formalization and implementation of the fitness function with consideration of soft constraints. A fitness evaluation algorithm is proposed based on the constraint requiring that classes of the same discipline, type, and group be scheduled consecutively in the same classroom. Mathematical expressions for penalty calculation in case of constraint violations are developed, and the data structure required for algorithm implementation is described. The obtained results can be applied in the development of intelligent automated timetable scheduling systems and extended by incorporating additional optimization criteria.