Asignación óptima de expertos a puestos de trabajo en base a expresiones regulares y el uso de recocido simulado

Abstract

La realización de ciertas tareas o actividades exige la disponibilidad de profesionales cada vez más cualificados. Teniendo en cuenta que el coste de estos trabajadores es elevado y que el número de recursos suele ser limitado, está claro que se necesita realizar una buena asignación de recursos y personal. Existen varios tipos de modelos de programación matemática que tratan sobre este tipo de problemas, como los problemas de asignación y de secuenciación de tareas, o los denominados problemas timetabling, que incluyen un conjunto de restricciones más complejo. En esta Tesis Fin de Máster afrontamos la resolución de una clase concreta de problemas de timetabling. Dichos problemas tienen naturaleza combinatoria, cuya complejidad es exponencial, es decir, que el número de soluciones a analizar crece de forma exponencial con la dimensión del problema a resolver. Esto implica que en problemas de mediana o gran dimensión, la resolución de este tipo de problemas no sea abordable mediante la utilización de métodos exactos o de heurísticas, ya que el tiempo que tardarían en resolverse sería excesivo. Por ello, se propone una técnica de solución basada en una metaheurística, el recocido o enfriamiento simulado. El recocido o enfriamiento simulado puede resolver el problema de forma eficiente, siendo necesaria la evaluación de un subconjunto muy reducido de las posibles soluciones del problema, y evitando que el proceso de búsqueda pueda quedarse atrapado en óptimos locales (inconveniente normalmente asociado al uso de heurísticas) mediante el movimiento hacia soluciones peores que la actual. En el método de solución, en una primera fase, se propone un algoritmo para la obtención de un conjunto de soluciones iniciales factibles. A partir de cada una de ellas (algoritmo de multicomienzo), se aplica el recocido simulado para la búsqueda de la solución óptima del problema. Para analizar la factibilidad de las soluciones que se van generando en el proceso de búsqueda se utilizan expresiones regulares, que hacen que dicha tarea se puede realizar de una forma rápida, haciendo más eficiente el método de solución. Por último, se muestra un ejemplo que ilustra la técnica de solución propuesta, y para el que describe cómo se han ajustado los parámetros del modelo y los tiempos de computación alcanzados, así como la calidad de la solución encontrada.---ABSTRACT---Performing certain tasks or activities requires the availability of increasingly skilled professionals. Given that the cost of these workers is high and that the number of resources is often limited, it is clear that performing a good allocation of resources and personnel is necessary. Different types of mathematical programming models that address such problem can be found in the literature, such as the assignment problem and task scheduling problem; or so-called timetabling problems, including a more complex constraint set. This Master’s Final Project deals with the resolution of a particular class of timetabling problems. These problems are combinatorial nature, whose complexity is exponential, i.e., the number of solutions to analyze grows exponentially with the size of the problem to be solved. This implies that the resolution of medium or large size problems is not affordable by using exact methods or heuristics, since the time it would take to solve them would be excessive. Therefore, we propose a solution technique based on the simulated annealing metaheuristic. Simulated annealing can efficiently solve the problem, since the evaluation of only a very small number of feasible solutions to the problem is required. It also avoids trapping in local optima (drawback normally associated with the use of heuristics) by accepting worse movements in its iterations. In the solution method, in a first stage, an algorithm for deriving an initial set of feasible solutions is proposed. Then, simulated annealing is applied to search for the optimal solution from each initial solution (multi-start algorithm). Regular expressions are used to analyze the feasibility of the solutions generated in the search process, which allows this task to be carried out quickly and makes the solution method more efficient. Finally, an example is used to illustrate the solution technique proposed and for describing how model parameters are fixed, computation times associated to its execution and the quality of the solution reached.