Resumen

En un estudio reciente (YAMASHITA; MORABITO, 2007a), se propuso un algoritmo exacto para resolver problemas de programación de proyectos con restricciones de recursos y costes de disponibilidad de recursos bajo múltiples modos de ejecución. Dicho algoritmo es una adaptación de otro algoritmo exacto registrado en la literatura para el caso particular en el que sólo existe un único modo de ejecución de las tareas. En el presente estudio, proponemos un nuevo algoritmo exacto basado en el método branch and bound para tratar el problema de múltiples modos de ejecución. Dado que el problema es NP-difícil, el algoritmo es computacionalmente viable sólo para problemas de tamaño moderado. Se han realizado numerosas pruebas computacionales utilizando el generador ProGen para comparar el rendimiento del algoritmo propuesto con el algoritmo anterior y con el software CPLEX. Los resultados muestran que la versión propuesta del algoritmo es competitiva con los otros métodos y animan a seguir investigando para el desarrollo de versiones más elaboradas de este algoritmo.

1. INTRODUCCIÓN

Los problemas de programación de proyectos consisten en planificar en el tiempo actividades que requieren recursos para su realización. Esta programación también debe tener en cuenta las restricciones de precedencia entre las actividades, es decir, ciertas actividades sólo pueden iniciarse después de que otras se hayan completado. Ejemplos de problemas de programación de proyectos aparecen en diversas áreas (MODER et al., 1983; POLLACK-JOHNSON; LIBERATORE, 1998), como la construcción civil (TAKAMOTO et al., 1995), la fabricación (NEUMANN et al., 2002), las telecomunicaciones, el desarrollo de software/ordenadores, el mantenimiento de aeronaves (GEMMILL; EDWARDS, 1999), entre otros. Por ejemplo, en la construcción de un puente, la adquisición de material, la contratación de mano de obra y las diversas etapas que componen la construcción, como la preparación del terreno, la cimentación, las estructuras de pilares, las vigas y losas, la pavimentación, son algunas de las actividades del proyecto. Estas actividades tienen una duración prevista en función de los recursos asignados y, para poder llevarse a cabo, también están sujetas a relaciones de precedencia. La ejecución de las actividades consume diferentes recursos como máquinas, mano de obra, dinero, etc.

Algunos problemas de programación de proyectos permiten que las actividades se ejecuten de formas alternativas (múltiples modos de ejecución). Por ejemplo, una actividad que requiere 10 periodos de tiempo para ser ejecutada por 1 trabajador, podría realizarse alternativamente en 4 periodos de tiempo utilizando 2 trabajadores.

• Materias:Programación de la producción Análisis de valores (Control de costos) Algoritmo de control
• Subjects:Production scheduling Value analysis (Cost control) Control algorithm
• Palabras claves:Programación de proyectos; Múltiples modos de ejecución; Costo de disponibilidad de recursos; Algoritmo de ramificación y acotamiento
• Keywords:Project scheduling; Multiple modes of execution; Resource availability cost; Branch and bound algorithm