Algoritmo metaheurístico para la formación de equipos dentro del aula: aplicación y análisis de GRASP

Abstract

[ES] En el mundo laboral, el trabajo en equipo es fundamental para abordar proyectos de manera eficaz. Esto se debe a que, por lo general, una sola persona no es suficiente para manejar todas las facetas de un proyecto y, en consecuencia, la ejecución del mismo sería menos efectiva que la que se lograría con un grupo de personas trabajando juntas. Por ello, con el fin de adaptar a los estudiantes a las tendencias del mundo laboral en la resolución de problemas, muchas titulaciones de educación superior promueven la realización de actividades o proyectos grupales para desarrollar las competencias colaborativas necesarias en los alumnos. Sin embargo, para fomentar el desarrollo adecuado de estas competencias, lo ideal sería agrupar a los estudiantes de forma estratégica, siguiendo ciertos criterios (p.ej., la teoría de roles de Belbin, la diversidad de géneros, etc.) que aumenten la probabilidad de que los equipos funcionen bien y permitan que una experiencia colaborativa fructífera favorezca la adquisición de dichas competencias. Esto no quita que formar equipos sea una tarea compleja de realizar manualmente, debido a la gran cantidad de combinaciones posibles que habría que analizar para identificar los mejores equipos. De hecho, incluso desde un punto de vista algorítmico, la resolución del problema también puede ser computacionalmente costosa si no se emplean algoritmos eficientes. Por esta razón, en este trabajo se exploran alternativas como las metaheurísticas, que suelen ser métodos algorítmicos más rápidos a la hora de generar respuestas. Entre las metaheurísticas estudiadas se encuentran un algoritmo genético y GRASP, siendo esta última un método poco utilizado hasta ahora para abordar el problema. Además, parece haber una falta de estudios comparativos sobre el rendimiento de ambas metaheurísticas en la formación de equipos, por lo que en este trabajo se realiza dicha comparación. Para evaluar el rendimiento de estas metaheurísticas en la formación de equipos, se emplean distintos tipos de instancias (i.e., tamaños de aula) con el objetivo de extraer conclusiones adecuadas sobre la calidad de las soluciones que son capaces de generar, así como sobre su escalabilidad temporal. Tras analizar su rendimiento, los resultados demuestran que ambos algoritmos generan soluciones igualmente satisfactorias en menos de un minuto, siendo GRASP la que las produce prácticamente de forma instantánea (i.e., alrededor de cinco segundos), superando de manera significativa al algoritmo genético en términos de eficiencia.

[EN] In the world of work, teamwork is essential for dealing with projects effectively. This is because one person is usually not sufficient to handle all facets of a project and, as a result, project delivery would be less effective than would be achieved with a group of people working together. Therefore, in order to adapt students to the problem-solving trends of the world of work, many higher education degrees promote group activities or projects to develop the necessary collaborative competences in students. However, to foster the proper development of these competences, students should ideally be grouped strategically, following certain criteria (e.g. Belbin's role theory, gender diversity, etc.) that increase the likelihood of well-functioning teams and allow for a successful collaborative experience to foster the acquisition of these competences. This does not detract from the fact that team formation is a complex task to perform manually, due to the large number of possible combinations that would need to be analysed in order to identify the best teams. In fact, even from an algorithmic point of view, solving the problem can also be computationally expensive if efficient algorithms are not used. For this reason, this paper explores alternatives such as metaheuristics, which tend to be faster algorithmic methods for generating answers. Among the metaheuristics studied are a genetic algorithm and GRASP, the latter being a method little used so far to address the problem. Moreover, there seems to be a lack of comparative studies on the performance of both metaheuristics in team formation, so this paper makes such a comparison. To evaluate the performance of these metaheuristics in team formation, different types of instances (i.e., classroom sizes) are used in order to draw appropriate conclusions about the quality of the solutions they are able to generate, as well as their temporal scalability. After analysing their performance, the results show that both algorithms generate equally satisfactory solutions in less than a minute, with GRASP producing them practically instantaneously (i.e., around five seconds), significantly outperforming the genetic algorithm in terms of efficiency.