Optimización de programación de proyectos usando algoritmos genéticos

Abstract

En este trabajo se propone un modelo de solución a un caso general de programación de proyectos, el cual es un sistema complejo con múltiples variables y restricciones. El modelo incluye características para la asignación de horas a tareas como: el método de la ruta crítica (basada en las duraciones y relaciones de secuenciamiento de cada tarea), limitada disponibilidad de recursos con respecto del tiempo, tendencias respecto del tiempo en la asignación de horas en cada tarea, asignación de horas de distintos grupos de recursos a una tarea manteniendo proporciones similares de asignación en cada periodo, distintos costos y calidad de trabajo de los recursos, desviaciones de las variables, entre otras. Así mismo, se diseña un Algoritmo Genético para la búsqueda de una solución óptima en base al costo, duración y calidad. Se propone una representación como una matriz de tres dimensiones (tareas N, periodos T y recursos M), que representa los diferentes tipos variables y en donde se modelan las restricciones planteadas para este problema. Se utilizan los operadores tradicionales de los algoritmos genéticos como la iniciación, selección de padres, cruzamiento y selección de la próxima generación. Finalmente, se ha incorporado en el modelo operadores expertos con la finalidad de aprovechar el conocimiento experto que se tiene en la programación de proyectos (heurística).

This thesis presents a solution model for a general case of resource-constrained scheduling, which is a complex system with multiple variables and restrictions. This work includes different models and characteristics for the scheduling and resource allocation such as critical path method, limited availability of resources regards to the time, hours allocation trends with respect to the time in each task, hours allocation for different resources groups in a task which maintains similar proportions in each period, different costs and work quality for each resource, or variables deviations. In addition, this document presents a Genetic Algorithm designed to optimize three objectives that are cost, duration and quality. A direct representation is proposed as a three- dimensional array of integer numbers (tasks N, periods T, and resources M), which represents the different variables and where restrictions proposed for this problem are modeled. Traditional operators of genetic algorithms such as initialization, parents selection, crossover, mutation and selection of the next generation are used. Finally, expert operators have been incorporated in the model with the purpose of taking advantage of the expert knowledge that is available of the scheduling and resource allocation of projects