Aplicación de algoritmos meméticos en la programación de horarios de clases

Abstract

The objective of this research is to solve a scheduling problem using memetic algorithms which solve problems with a large number of variables and constraints. This method can be applied to different scheduling problems in which they must share resources, such as scheduling clients for certain services, resource allocation, etc. The problem to be solved in this research is the assignment of the best possible schedule for professors of the Department of Mathematical Sciences, at University of Puerto Rico at Mayaguez, which offers over 180 sections in 13 regular classrooms, two labs and two amphitheatres . It is a difficult process scheduling courses classes at set times due to physical constraints, variation in the number of course credits, fulfill orders of teachers, among others. The problem can be stated using integer linear programming that is closely related to an assignment problem, but its real-time solution to the problem of assigning professors to classes is computationally infeasible because the variables considered in the problem are binary. It has been shown that the problem of optimizing a scheduling problem is NP-hard, as an alternative is to develop heuristics as an alternative to the solution of this problem whose goal is to determine the best schedule of classes that satisfy as much of preferences of professors, including the satisfaction of requested classes, block scheduling and rooms to obtain the best solution in a reasonable time. Memetic algorithms that were used are heuristics that solve the scheduling problem in a reasonable time and generate the best possible schedule that satisfies the requests of teachers in terms of classes, time and lounges.

El trabajo de esta investigación tiene como objetivo principal resolver un problema de programación de horarios usando algoritmos memeticos los cuales resuelven problemas con una gran cantidad de variables y restricciones. Este método puede ser aplicado a diferentes problemas de programación de horarios en los cuales se deben compartir recursos, tales como programación de clientes para ciertos servicios, asignación de recursos, etc. El problema que se trata de resolver en esta investigación es el de asignar el mejor horario posible a los profesores considerando los cursos en los horarios establecidos debido a las limitaciones físicas, variación en la cantidad de créditos de los cursos, satisfacer los pedidos de los profesores, entre otros. El problema se puede plantear usando programación lineal entera que está muy relacionado a un problema de asignación, sin embargo su solución en tiempo real para el problema de asignar las clases a los profesores es computacionalmente imposible debido a que las variables que se consideran en el problema son binarias. Se ha demostrado que el problema de optimizar una programación de horarios es un problema NP-Completo, por lo que se consideró como una alternativa a la solución a este problema desarrollar heurísticas cuyo objetivo es determinar el mejor horario de clases que satisfaga la mayor cantidad de preferencias de profesores, que incluya la satisfacción de clases solicitadas, bloques de horario y salones que permitan obtener la mejor solución en un tiempo razonable. Se utilizaron algoritmos meméticos que son heurísticas que resuelven el problema de programación de horarios en un tiempo razonable y generan el mejor horario posible que satisface las peticiones de los profesores en cuanto a clases, tiempo y salones. Como aplicación se condideró las condiciones definidad por el Departamento de Ciencias Matemáticas de la Universidad de Puerto Rico, Recinto de Mayagüez, el cual ofrece alrededor de 180 eventos distribuidas en 13 salones regulares, dos laboratorios y dos anfiteatros y un salón para eventos graduados.