| Journal: | Nova scientia |
| Database: | PERIÓDICA |
| System number: | 000412969 |
| ISSN: | 2007-0705 |
| Authors: | Sánchez Partida, Diana1 Baquela, Enrique Gabriel2 Mora Vargas, Jaime1 Smith, Neale R1 |
| Institutions: | 1Instituto Tecnológico y de Estudios Superiores de Monterrey, Escuela de Ingeniería y Ciencias, Monterrey, Nuevo León. México 2Furgens Research, Buenos Aires. Argentina |
| Year: | 2016 |
| Volumen: | 8 |
| Number: | 17 |
| Pages: | 340-360 |
| Country: | México |
| Language: | Inglés |
| Document type: | Artículo |
| Approach: | Experimental, aplicado |
| Spanish abstract | En ocasiones, los problemas de Optimización Combinatoria (COP), tal como el Problema de Calendarización de horarios (CTTP), se puede resolver utilizando técnicas Investigación Operativa (IO); sin embargo, cuando el problema aumenta de tamaño, la búsqueda de una solución se vuelve más compleja. Este tipo de problema es NP-duro por lo que requiere de procedimientos como métodos metaheurísticos con el fin de resolver el problema. Este trabajo aborda un Problema real en una Institución de Educación Superior Mexicana acerca de la Calendarización de horarios basada en la Curricula (CB-CTT). Cada institución tiene sus propias reglas operacionales, por lo tanto la modelación del problema es único ya que conserva sus propias características. Primero como parte de la aportación a la solución del problema, se elaboró un Software de Mediación (MS) con el fin de organizar los datos en bruto y eliminar la restricción dura en relación con los planes de estudio. Posteriormente, el problema se dividió en cinco instancias, de acuerdo a los cursos que comparten el mismo espacio físico, los cuales fueron resueltos mediante el algoritmo tradicional de Recocido Simulado (SA).El problema fue resuelto de manera satisfactoria, obteniendo la asignación de 9620 sesiones en 174.5 horas aproximadamente, aportando una solución sin particionar el problema en dos subproblemas, impactando positivamente la reducción del tiempo de elaboración de los horarios, proporcionando un horario factible y sin errores para toda la universidad. MÉTODO: El Algoritmo de Recocido Simulado, cristalización simulada o enfriamiento simulado, es un algoritmo de búsqueda metaheurística para problemas de optimización; el objetivo general de este tipo de algoritmos es encontrar una buena aproximación al valor óptimo de una función en un espacio de búsqueda grande. A este valor se lo denomina "óptimo local u óptimo global". El nombre |
| English abstract | On occasions, Combinatorial Optimization Problems (COP), like the University Course Timetabling Problem (CTTP), can be solved using Operational Research (OR) techniques; however, when the problem increases in size, finding a solution becomes more complex. This type of problem is NP-hard, requiring procedures like metaheuristic methods in order to solve the problem. This paper confronts a real world situation in Mexico concerning the Curriculum-Based Timetabling Problem (CB-CTT). Each institution have their own operationals rules due to the modeling of the problema is unique because preserve their own characteristics. First, as part of the contribution to the solution of the problem, it was implemented a Mediation Software (MS) in order to organize the raw data and eliminate a hard constraint related to curricula. Subsequently, the problem handle here was split into five instances in accordance to the courses that share the same physical space, which was solved using a typical Simulated Annealing (SA) metaheuristic. In addition, The problem was satisfactorily solved, assigning 9620 lectures in 174.5 hours approximatly, providing a solution without partitioning the problem into two subproblems, impacting positivly reducing the labor time, and providing a feasible and without errors educational timetable to the whole university. METHOD: The Simulated Annealing (SA) algorithm is a meta-heuristic search for global optimization problems; the overall objective of such algorithms is to find a good approximation to the optimal value of a function in a large search space. This value is called "global or local optimum".The name and inspiration comes from the process of annealing the steel and ceramics, a technique that involves heating and then slowly cooling the material to vary its physical properties. The heat causes the atoms increase their energy and can thus move from their initial (a local minimum energy) positions; slo |
| Disciplines: | Ciencias de la computación, Educación |
| Keyword: | Planeación educativa, Software, Horario escolar, Optimización combinatoria, Recocido simulado, Metaheurísticas |
| Keyword: | Computer science, Education, Educational planning, Software, School schedule, Combinatorial optimization, Simulated annealing, Metaheuristics |
| Full text: | Texto completo (Ver HTML) |
