APPLICATION OF METAHEURISTICS TO THE PROBLEM OF SCHOOL SCHEDULE SCHEDULING

The present work investigates the application of metaheuristic techniques in solving the School Schedule Scheduling Problem, a classic combinatorial optimization challenge, classified as NP-difficult. Considering the multiple constraints inherent to the problem, it is proposed to use the Iterated Local Search (ILS), Variable Neighborhood Search (VNS) and Iterated Taboo Search (ITS) approaches, based on initial solutions generated by a Random Constructive Heuristic with a repair mechanism. The formulation contemplates strong and weak constraints, incorporated into an objective function with weighted penalties. The experiments were carried out with real data from four academic periods of a federal educational institution, and indicate that all the solutions obtained were viable. Among the methods evaluated, ITS presented the best average results in terms of solution quality. The findings confirm the effectiveness of the proposed metaheuristics in the generation of consistent solutions with low computational cost.