Obtaining the Global Optimum of an NP-Hard Problem: School Schedule through the Three-Stage Strategy

• DOI: https://doi.org/10.22533/at.ed.3174142429041

• Palavras-chave: NP-Duro, Horario escolar, Estrategia por etapas, Óptimo global.

• Keywords: NP-Hard, School schedule, Staged strategy, Global optimal.

• Abstract:

  The preparation of school schedules is a problem that occurs in many educational institutions around the world. From the mathematical approach, school schedules are considered NP-hard, since the computational time in searching for the solution can increase exponentially by increasing the number of variables, or by the complexity of the restrictions. Different strategies are reported in the literature to solve this problem; however, these do not guarantee finding the best solution or global optimum of the problem. This document establishes a validation of the three-stage assignment strategy that has been used in the solution of school schedules, whose results are characterized by obtaining good solutions in short times through the exact branching and bounding technique. Validation consists of demonstrating that the strategy reaches the global optimum in a school schedule problem.