Programação de Projetos com Restrição de Tempo

Vista previa del material en texto

PROGRAMACIÓN DE MULTIPLES PROYECTOS CON TIEMPO RESTRINGIDO 
MINIMIZANDO COSTOS DE RECURSOS 
 
 
 
 
 
 
ILMER ANDREY CAÑÓN DÍAZ 
 
 
DIRECTOR: 
JOSE FIDEL TORRES 
 
 
 
JURADOS: 
CARLOS EDUARDO MONTOYA CASAS 
DAVID ÁLVAREZ MARTÍNEZ 
 
 
 
 
 
 
UNIVERSIDAD DE LOS ANDES 
FACULTAD DE INGENIERÍA 
DEPARTAMENTO DE INGENIERÍA INDUSTRIAL 
JUNIO DE 2017 
PROGRAMACIÓN DE MULTIPLES PROYECTOS CON TIEMPO RESTRINGIDO 
MINIMIZANDO COSTOS DE RECURSOS 
Ilmer Andrey Cañón Díaz 
Departamento de Ingeniería Industrial, Universidad de los Andes, Bogotá, Colombia 
 
Resumen 
Este artículo presenta la propuesta de una variante del problema conocido como Resource 
Availability Cost Problem y la implementación de un algoritmo heurístico basado en redes de Petri 
y el algoritmo Beam A* Search. El objetivo es determinar un agendamiento de las actividades y la 
asignación de recursos que permita cumplir con la fecha límite de entrega del proyecto. Las 
actividades del proyecto requieren una cantidad de diferentes tipos de recurso y se deben respetar 
las relaciones de precedencia entre las actividades. La motivación de utilizar redes de Petri y el 
algoritmo Beam A* Search se da porque este enfoque ha sido utilizado con éxito en otro tipo de 
problemas de proyectos. El método propuesto se comparó con uno de los algoritmos heurísticos de 
mejor desempeño en la literatura sin que éste resultase competitivo en el grupo de instancias de 
prueba. Los resultados son reportados y se realizan recomendaciones para trabajo futuro. 
 
Aspectos Destacados y Principales Aportes 
Se realizó una revisión bibliográfica extensa en la que se determinó que no se encuentra una variante 
del problema RACP que comprendiera un ambiente de múltiples proyectos, así que se propone dicha 
variante en el presente trabajo. Se propuso un algoritmo basado en redes de Petri y el algoritmo 
Beam A* Search, lo cual no había sido utilizado para la solución del problema RACP. Experimentos 
computacionales fueron realizados para comprobar el desempeño del método propuesto. Se propone 
el modelo matemático para el problema RACP multi proyecto teniendo en cuenta las condiciones 
explicadas en la descripción del problema. Se tomaron instancias de la literatura para el RCPSP 
multi proyecto y se adaptaron a las condiciones del problema aquí propuesto. Adicionalmente se 
proponen instancias de elaboración propia. Utilizando el optimizador Gurobi, de las instancias 
propias como de las adaptadas de la literatura se cuenta con soluciones óptimas obtenidas de la 
implementación del modelo matemático. Esta información puede ser utilizada en futuras 
investigaciones. 
 
Palabras Clave: Red de Petri, Beam A* Search, Resource Availability Cost Problem (RACP). 
 
 
 
 
Tabla de contenido 
 
1. INTRODUCCIÓN ..................................................................................................................... 4 
2. DESCRIPCIÓN DEL PROBLEMA .......................................................................................... 5 
3. OBJETIVOS .............................................................................................................................. 8 
3.1. Objetivo General ................................................................................................................. 8 
3.2. Objetivos Específicos ......................................................................................................... 8 
4. MARCO TEÓRICO ................................................................................................................... 9 
4.1. Revisión Bibliográfica ........................................................................................................ 9 
5. METODOLOGÍA .................................................................................................................... 15 
5.1. Propuesta del Modelo Matemático Multiproyecto ........................................................... 15 
5.2. Modelamiento mediante Redes de Petri ........................................................................... 18 
5.3. Algoritmo Beam A* Search ............................................................................................. 19 
5.4. Estructura del Algoritmo de Solución Propuesto ............................................................. 21 
6. RESULTADOS ........................................................................................................................ 26 
6.1. Instancias de prueba .......................................................................................................... 26 
6.2. Comparación de Resultados para el RACP de un proyecto ............................................. 28 
6.3. Resultados en Instancias RACP Multiproyecto ................................................................ 32 
7. CONCLUSIONES ................................................................................................................... 36 
7.1. Conclusiones ..................................................................................................................... 36 
7.2. Recomendaciones para Trabajo Futuro ............................................................................ 37 
8. BIBLIOGRAFÍA ..................................................................................................................... 38 
 
 
 
 
 
 
 
 
1. INTRODUCCIÓN 
 
La programación de proyectos ha sido estudiada cada vez con mayor atención en los últimos 50 
años (Weglarz et. al. 2010) debido a sus diversas aplicaciones prácticas y al interés que han puesto 
en los diferentes problemas los investigadores dada su llamativa complejidad. Así pues, el desarrollo 
que ha mostrado el estudio de esta temática se ha dirigido tanto al modelamiento adecuado de 
condiciones más realistas en los problemas de proyectos como a generar más y mejores métodos de 
solución. 
La aplicación práctica de la programación de proyectos con tiempo restringido minimizando el costo 
de los recursos se dio desde la concepción del llamado Resource Availability Cost Problem (RACP) 
propuesto por Mohring, (1984) al enfrentarse a dicho problema real en la construcción de un puente, 
mientras otros autores señalan que su aplicabilidad se extiende no solo a proyectos de construcción 
sino a problemas de administración de personal (Jedrzejowicz y Ratajczak-Ropel, 2012), a 
proyectos de ingeniería de diseño de autopartes (Hsu y Kim, 2004) pero aún más importante, de 
acuerdo con Drexl & Kimms (2001), la solución de este problema sujeto a diferentes tiempos límite 
da una idea del balance de acuerdos que puedan pactarse en términos de costo y tiempo, por lo cual, 
este problema puede brindar información muy preciada dado que permite estimar el precio de 
negociación que tendrá un proyecto. 
Por otra parte, de acuerdo con diversas investigaciones, se ha establecido que las empresas 
normalmente no realizan un solo proyecto a la vez, sino que desarrollan un conjunto de proyectos 
al mismo tiempo. Según Payne (1995), el 90% de los proyectos se generan y desarrollan en 
contextos de múltiples proyectos. Los proyectos simultáneos pueden incluso (dependiendo de la 
situación) requerir diversos tipos de recursos en común, por lo cual, la toma de decisiones en cuanto 
a la asignación de recursos, el inicio de las actividades y el tiempo de ejecución de los proyectos se 
convierte en una tarea compleja. 
El problema de minimización del costo de los recursos (RACP), a pesar tener un objetivo distinto 
al tradicional, está estrechamente relacionado con éste (programación de proyectos en donde dadas 
las condiciones del problema en cuanto a recursos limitados y precedencias de actividades se busca 
minimizar el tiempo de ejecución total del proyecto). Aun así, con las similitudes existentes y con 
la aplicabilidad práctica que en la industria tiene el Resource Availability CostProblem, éste 
problema ha recibido poca atención y la literatura existente acerca de este problema es escasa (Zhu 
et. al, 2016). 
A este respecto se puede resumir la literatura más relevante acerca del RACP con la aplicación de 
cuatro algoritmos exactos: Mohring, 1984. Demeulesmeester, 1995. Rangaswamy, 1998. Rodriguez 
y Yamashita, 2010. El cálculo de cotas inferiores propuesto por Drexl & Kimms (2001) y el 
desarrollo de ocho algoritmos entre heurísticos y metaheurísticos: Yamashita & Armentano, 2006. 
Shadrokh & Kianfar, 2007. Ranjbar, Kianfar & Shadrokh, 2008. Peteghem & Vanhoucke, 2012 y 
2013. Hsu & Kim, 2005. Qi, Liu & Jiang, 2015. Zhu, Ruiz y demás: 2016. 
Cabe agregar que los mencionados autores han realizado sus trabajos para el problema RACP 
consistente de un único proyecto, además algunos contemplaron variantes como múltiples modos, 
tardanza permitida y escenarios estocásticos, sin embargo, ninguno de ellos ha estudiado la 
extensión del problema a múltiples proyectos. 
2. DESCRIPCIÓN DEL PROBLEMA 
 
En este trabajo se busca dar solución a través del desarrollo de un algoritmo heurístico, al problema 
de minimización del costo total de los diversos recursos renovables necesarios para la ejecución de 
múltiples proyectos en los cuales el tiempo es limitado, es decir, se cuenta con fecha límite de 
terminación o entrega de cada uno de los proyectos. 
El problema mencionado ha sido abordado sólo en contextos de un único proyecto y se conoce en 
la literatura como Resource Availability Cost Problem. Éste fue propuesto por Mohring (1984) 
inicialmente como Resource Investment Problem1. Mohring realizó una clasificación de los 
problemas de programación de proyectos definiendo las siguientes categorías: 
 
1. Problema de escasez de recursos: en el cual se tiene un límite en la cantidad de recursos 
disponibles para la realización de las actividades del proyecto y se pretende encontrar la 
duración mínima que tendría el proyecto dada la condición de recursos limitados. 
2. Problema de Tiempo Limitado: en este problema se tiene el supuesto de contar con 
cantidades ilimitadas de recursos pero un tiempo límite en el cual debe terminar la ejecución 
del proyecto, por lo cual se busca encontrar el mínimo costo total de recursos necesarios 
para ejecutar el proyecto en el tiempo límite. 
El problema de minimización de costos de los recursos (RACP) se ubica en la segunda categoría 
mencionada anteriormente y consiste2 en un proyecto el cual está compuesto de N+2 actividades (N 
actividades propias del proyecto y 2 actividades ficticias que son utilizadas para representar el inicio 
y la finalización del proyecto siendo éste último modelado mediante un grafo de actividades sobre 
nodos). Las actividades están sujetas a un conjunto de relaciones de precedencia, cada una de ellas 
tiene un tiempo de duración determinístico definido y requieren una cantidad fija de diversos 
recursos renovables a lo largo de su duración. Por último, como parámetro de entrada del problema 
se tiene un tiempo límite de terminación del proyecto (debe ser mayor o igual a la duración de la 
ruta crítica del proyecto). 
El objetivo en este problema es encontrar la programación de todas las actividades del proyecto de 
tal manera que se respeten las relaciones de precedencia de las actividades, el tiempo de ejecución 
del proyecto sea menor o igual a la fecha límite de entrega y se logre minimizar el costo total de los 
recursos necesarios para el desarrollo del proyecto. 
 
1 Hsu, C. Kim, D. A New Heuristic For The Multi-Mode Resource Investment Problem. Journal Of The Operational 
Research Society. P 406-413. 2005. 
2 Demeulemeester, E. Minimizing Resource Availability Costs In Time-Limited Project Networks. Management 
Scinence Vol. 41, No. 10. 1995. 
Entre los supuestos3 del problema se tienen: 
 No hay prelación o prioridad en la ejecución de las actividades y su desarrollo está sujeto 
únicamente a sus relaciones de precedencia. 
 Una vez una actividad inicia, ésta se ejecuta sin interrupción hasta ser terminada. 
 Los parámetros del problema, tales como los tiempos de ejecución y la cantidad de recurso 
de cada tipo requerido por cada actividad son valores determinísticos positivos que no 
varían en el tiempo. 
 Existe un único modo en que se realizará cada actividad (single-skill). 
 Se asume que el costo total de un recurso k (𝐶𝑘 ∗ 𝑎𝑘) depende de la disponibilidad 𝑎𝑘 de 
dicho recurso, sin considerar si el recurso es o no utilizado por las actividades, por lo tanto, 
el menor costo de disponibilidad de recurso 𝐶𝑘 ∗ 𝑎𝑘 es establecido por la disponibilidad para 
cada tipo de recurso k. Esto quiere decir que un recurso es asignado a un proyecto durante 
toda su duración (el recurso está disponible en toda la ejecución y ésta es la que genera 
costo), entonces se tendrá un costo total a nivel general que dependerá de la cantidad de 
recurso que se asigna al proyecto para toda su duración. 
La formulación del modelo matemático4y5 para el problema teniendo en cuenta un único proyecto 
con las condiciones y supuestos mencionados es la siguiente: 
𝑰𝒏𝒅𝒊𝒄𝒆𝒔 
j: actividades. j=0 y j=N+1 son actividades ficticias que representan la actividad inicial y la 
actividad final del proyecto respectivamente siendo N el número de actividades propias (reales) del 
proyecto. 
k: índice para el tipo de recurso. k = 1…K con K recursos totales. 
t: índice relacionado con el tiempo (unidad de tiempo depende del contexto del proyecto). t = 
0,1,2,3…T (tiempo límite). 
𝑷𝒂𝒓á𝒎𝒆𝒕𝒓𝒐𝒔 
T: fecha de entrega o tiempo límite de entrega/terminación del proyecto. 
Ck: costo unitario del recurso tipo k. 
dj: duración de la actividad j. 
rkj: cantidad de recurso tipo k requerido para la ejecución de la actividad j. 
 
3 Vanhoucke, M. Project Management With Dynamic Scheduling. Cap 8. Resource Constrained Scheduling 
Extensions. P 141-174. Springer-Verlag Berlin Heidelberg. 2012. 
4 Rodriguez, S. Yamashita, D. Exact Methods for the Resource Availablity Cost Problem. Handbook on Project 
Management and Scheduling. Vol 1. Cap 15. Springer International Publishing Switzerland. 2015. 
5 Hsu, C. Kim, D. A New Heuristic For The Multi-Mode Resource Investment Problem. Journal Of The Operational 
Research Society. P 406-413. 2005. 
Pj: conjunto de predecesores inmediatos de la actividad j. 
𝑽𝒂𝒓𝒊𝒂𝒃𝒍𝒆𝒔 𝒅𝒆 𝑫𝒆𝒄𝒊𝒔𝒊ó𝒏 
𝑋𝑗𝑡: variable binaria. Toma valor de 1 si la actividad j inicia en el tiempo t. 0 de lo contrario. 
𝑅𝑘: variable que indica la cantidad unidades de recurso tipo k requeridas en el proyecto (cantidad 
disponible de recurso tipo k que se debe asignar a lo largo del proyecto). 
 
𝑀𝑖𝑛 ∑ 𝐶𝑘𝑅𝑘
𝑘 𝑒𝑛 𝐾
 
Sujeto a: 
∑ 𝑋𝑗𝑡
𝑡∈{0..𝑇}
= 1 ∀ 𝑗 𝑒𝑛 𝐽 (1) 
∑ 𝑋𝑁𝑡 ∗ 𝑡
𝑡∈{0..𝑇}
≤ 𝑇 ∀ 𝑗 𝑒𝑛 𝐽 (2) 
∑ ∑ 𝑟𝑘𝑗 ∗ 𝑋𝑗𝑦
𝑡
𝑦=(𝑡−𝑑𝑗)
+𝑗 𝑒𝑛 𝐽
≤ 𝑅𝑘 ∀ 𝑗 𝑒𝑛 𝐽, 𝑡 𝑒𝑛 (0… 𝑇) | 𝑦 > 0 (3) 
∑ (𝑡 + 𝑑𝑖) ∗ 𝑋𝑖𝑡
𝑡∈{0..𝑇}
≤ ∑ 𝑡 ∗ 𝑋𝑗𝑡
𝑡∈{0..𝑇}
 ∀ 𝑗 𝑒𝑛 𝐽, 𝑖 ∈ 𝑃𝑗 (4) 
𝑋𝑗𝑡 ∈ {0, 1} ∀ 𝑗𝑒𝑛 𝐽, 𝑡 𝑒𝑛 (0…𝑇) (5) 
𝑅𝑘 ≥ 0 ∀ 𝑘 𝑒𝑛 𝐾 𝑐𝑜𝑛 𝑅𝑘 ∈ Ζ+ (6) 
La función objetivo del problema establece la minimización del costo total de los recursos asignados 
al proyecto. La restricción (1) refuerza la condición de que una actividad inicia y se realiza una sola 
vez. La restricción (2) determina que la última actividad del proyecto debe iniciar (y terminar puesto 
que su duración es cero) antes de la fecha límite de entrega del proyecto. La restricción (3) permite 
determinar la cantidad de recurso de cada tipo que debe ser asignada al proyecto (disponibilidad de 
recursos). La restricción (4) permite el cumplimiento de las relacionesde precedencia entre 
actividades. Las restricciones (5) y (6) respectivamente definen la naturaleza binaria de las variables 
de decisión relacionadas con tiempo de inicio de las actividades y la cantidad entera de recurso 
necesaria. 
A la luz de lo mencionado anteriormente con la descripción del problema en casos de un único 
proyecto, cabe mencionar que el trabajo a realizar en este proyecto es estudiar el problema de 
minimización de costos de recursos, extendido a un contexto de múltiples proyectos. 
 
 
Problema RACP Multiproyecto 
Se considera una situación hipotética en la que una empresa planea la realización de múltiples 
proyectos, para los cuales deberá asignar una cantidad de diferentes tipos de recursos comunes a 
utilizar en todos los proyectos. Cada uno de los proyectos cuenta con una fecha límite de entrega y 
está obligada a demostrar la gestión de cada proyecto iniciando máximo cada proyecto también en 
una fecha determinada, por lo cual, si no todos, habrá varios proyectos que se estén ejecutando 
simultáneamente. 
A cada tipo de recurso debe asignarse una cantidad que estará disponible a lo largo de la duración 
de todo el conjunto de proyectos a realizar (desde el momento 0 hasta la entrega del proyecto con 
mayor fecha límite de terminación). Se deben respetar las relaciones de precedencia de las 
actividades de todos los proyectos. Una vez iniciada una actividad, ésta debe ejecutarse por 
completo. No hay preferencias entre actividades y se deben cumplir las fechas de entrega de cada 
proyecto iniciando mínimo en su fecha de inicio preestablecida. 
 
El objetivo de este problema es encontrar la asignación de recursos disponibles para los proyectos 
y el agendamiento de todas las actividades de todo el conjunto de proyectos de tal manera que se 
garantice el cumplimiento de sus fechas de entrega y sea minimizado el costo de disponibilidad de 
los recursos necesarios. En el capítulo Metodología, se establece el modelo matemático para el 
problema descrito. 
 
De acuerdo a la revisión bibliográfica realizada, se estableció que, al iniciar este trabajo, dada la 
escasa bibliografía acerca del problema RACP y a que no se encontraba en la literatura una variante 
que considerara un contexto multi proyecto, se decidió proponer esta variante del problema. 
 
3. OBJETIVOS 
 
3.1. Objetivo General 
 
Diseñar un algoritmo heurístico para resolver el problema de minimización de costos de recursos 
para múltiples proyectos con tiempo restringido mediante un enfoque de modelamiento basado en 
redes de Petri. 
 
3.2. Objetivos Específicos 
 
 Desarrollar el modelo matemático del problema de minimización de costos de recursos en 
múltiples proyectos con tiempo restringido. 
 Proponer el modelo matemático para el problema RACP multi proyecto. 
 Aplicar el algoritmo Beam A* Search para la solución del problema descrito. 
 Validar y comparar el desempeño del algoritmo respecto a otros algoritmos propuestos para 
la solución del problema mencionado en el caso de un solo proyecto. 
 Generar resultados de instancias del problema multiproyecto para que puedan utilizarse en 
futuras investigaciones. 
 Generar conclusiones y proponer recomendaciones para futuras investigaciones. 
4. MARCO TEÓRICO 
 
4.1. Revisión Bibliográfica 
 
Estado del Arte: Variantes y Métodos de Solución del Resource Availability Cost Problem 
 
Citando a Zhu et. al. (2016), se sabe que Mohring (1984) al proponer el problema RACP también 
conocido inicialmente como Resource Investment Problem, desarrolló un método exacto de 
solución basado en algoritmos de teoría de grafos además de que demostró la relación de dualidad 
existente entre el RACP y el problema de programación de proyectos con recursos restringidos 
RCPSP. Posteriormente Demeulemeester (1995) desarrolló un algoritmo basado en Branch & 
Bound en el que generaba un agendamiento de las actividades de tal manera que si la duración total 
sobrepasara la fecha límite de entrega del proyecto se asignaba una unidad adicional de recurso, con 
lo cual el problema se convertía en minimización del makespan con recursos limitados. Se repetía 
el procedimiento hasta que el makespan no supere la fecha de entrega del proyecto. 
 
Rodríguez y Yamashita (2010) desarrollaron una versión mejorada del algoritmo de 
Demeulemeester denomiado MMBA donde las soluciones iniciales eran generadas por una 
heurística logrando también reducir el espacio de búsqueda mejorando la efectividad del método. 
Por otra parte, Drexl & Kimms (2001) propusieron dos cotas inferiores por medio de métodos de 
relajación lagrangiana y generación de columna, además, afirman que la solución del RACP para 
distintas fechas de entrega proporciona información relevante en cuanto al precio de negociación de 
un proyecto. 
 
Yamashita, Armentano y Laguna (2006) propusieron una meta-heurística basada en búsqueda 
dispersa (Scatter Search SS) compuesta por una heurística de mejoramiento para hacer factibles 
soluciones iniciales que no lo son y en seguida es aplicado un procedimiento de vinculación de 
caminos (Path relinking), el cual genera nuevos elementos en la población de búsqueda. Estos 
autores lograron obtener buenos resultados en calidad y tiempo computacional. 
 
Shadrokh & Kianfar (2007) propusieron un algoritmo genético para resolver el RACP con tardanza 
permitida con costos de penalización. Los cromosomas utilizados son representados por una lista de 
prioridad y una lista de disponibilidad de recursos mientras que Ranjbar, Kianfar & Shadrokh (2008) 
propusieron un algoritmo basado en revinculación de caminos (Path Relinking) y un algoritmo 
genético. Las soluciones representadas por listas de actividades son asignadas a un vector y el 
agendamiento es generado usando un esquema basado en el planteado por Burgess & Killebrew 
(1962) donde se busca nivelar el uso de diferentes tipos de recurso. Como resultado obtuvieron que 
el algoritmo Path Relinking superó el desempeño del algoritmo genético. 
 
Peteghem & Vanhoucke (2013) presentaron un algoritmo denominado Artificial Inmune System, el 
cual utiliza mecanismos inspirados en el sistema inmune de los vertebrados. Los autores representan 
los vectores solución como listas de actividades y de capacidad e incluyen una función de 
probabilidad para la lista de capacidad. Los autores logran establecer que su algoritmo supera el 
genético de Shadrokh & Kianfar. Posteriormente en 2015, Peteghem & Vanhoucke proponen aplicar 
un método basado en el comportamiento de la “hierva mala” denominado Invasive Weed 
Optimization6 desarrollado por Mehrabian & Lucas (2006), conservando el uso de las listas 
mencionadas y modificando la búsqueda de acuerdo a la proliferación de semillas de las hiervas en 
que está inspirado el método. Los autores con este algoritmo superan los resultados obtenidos con 
el Artificial Inmune System. 
 
Cabe agregar que en su estudio, Peteghem & Vanhoucke (2013) también proponen una variante del 
problema en el que agregan la posibilidad de no satisfacer la restricción de la fecha de entrega del 
proyecto e incluyen al costo a minimizar, los relacionados a la penalización por la entrega tardía del 
proyecto. 
 
La variante de múltiples modos del RACP fue abordada por Hsu & Kim (2005) utilizando una 
heurística basada en reglas de prioridad para la generación del agendamiento de actividades, donde 
a través del cálculo de una función de prioridad que tiene en cuenta el tiempo faltante del proyecto 
y el mínimo de inversión (costo) selecciona la actividad a desarrollar y el modo en que se realizará. 
 
Los autores Qi, Liu & Jiang (2015) para el problema RACP multi modo presentan un algoritmo 
basado en Particle Swarm Optimization. Inicialmente generan una reparación de soluciones iniciales 
no factibles y posteriormente aplican un proceso modificado de la PSO que la combina con Scatter 
Search. Los autores reportanresultados promisorios de esta variante del problema. 
 
Zhu, Ruiz y demás (2016) proponen un algoritmo heurístico en el que no utilizan el enfoque 
comúnmente observado en la literatura de resolver el RACP solucionando iterativamente un 
problema de recursos limitados (RCPSP), sino que dividen el RACP en dos sub problemas: 
problema de secuenciación y problema de recursos. La heurística propuesta es iterativa multi inicio, 
comenzando por la secuenciación de las actividades y al abordar el problema de recursos realiza 
una eliminación de los picos de recurso existentes. Los autores se comparan con los tres métodos 
considerados los mejores hasta el momento: Scatter Search (Yamashita, 2006), Path Relinking y el 
algoritmo genético (Ranjbar, Kianfar & Shadrokh, 2008) reportando la superación del desempeño 
de estos algoritmos en efectividad y eficiencia7. 
 
En trabajos más recientes, variantes del RACP han sido estudiadas con el objetivo de dar mayor 
realismo al problema, modificando los supuestos mencionados anteriormente. Una de estas 
variantes es propuesta por Afshar-Nadjafi (2014) donde a través de algoritmos de búsqueda 
exhaustiva (GRASP) y la metaheurística recocido simulado (SA) aborda el problema del costo de 
disponibilidad de recursos (RACP) con múltiples modos, contratación y fechas de liberación de 
 
6 Peteghem, V. Vanhoucke, M. Heuristic Methods for the Resource Availability Cost Problem. Handbook on Project 
Management and Scheduling. Vol 1. Capítulo 16. 2015. 
7 X. Zhu et al., An effective heuristic for project scheduling with resource availability cost, European Journal of 
Operational Research. 2016. 
recurso. El problema tiene en cuenta la relajación del supuesto de que los recursos asignados al 
proyecto se contratan para toda la duración del mismo aunque solo sean utilizados en un periodo 
reducido de tiempo, por lo cual, el autor incluye la posibilidad de utilizar un recurso cuando se 
requiere y posteriormente ser liberado, evitando el costo de mantenerlo disponible durante todo el 
proyecto, al mismo tiempo que establece que el costo de contratar un recurso depende del tiempo 
que será utilizado. El objetivo bajo estas condiciones sigue siendo minimizar el costo total de los 
recursos necesarios para desarrollar el proyecto dentro de la fecha límite. 
 
Otra variante fue propuesta por Verbeeck y Van Peteghem, et. al (2016)8. Los autores lo denotan 
problema de programación de proyectos con tiempo restringido (TCPSP), donde la diferencia 
principal con el RACP clásico es que se cuenta con un conjunto de recursos con una determinada 
capacidad fija, tal como en el Resource Constrained Project Scheduling Problem (RCPSP), además 
de una fecha límite de tiempo de entrega, donde el objetivo no es determinar la cantidad de recurso 
necesario a lo largo del proyecto sino decidir la cantidad de recurso de cada tipo, cúando debe ser 
asignada y para cuáles tipos de recurso se requiere adquirir capacidad adicional por encima de la 
capacidad disponible inicialmente. En este sentido el problema tiene como fin minimizar el costo 
total de contratación de recursos adicionales. 
 
Una parte de la literatura existente aborda el Resource Investment Problem con distintas variantes 
tales como RIP/Max, en donde el objetivo es encontrar la máxima tardanza de cada actividad. Para 
resolver este problema Zimmermann & Englehardt (1998) realizaron un algoritmo de ramificación 
y acote basado en ventanas de tiempo, mientras que Nübel (1999) propuso un método de solución 
considerando capacidades de recurso ficticias, con lo cual resolviendo el problema de conflictos de 
recurso solucionaba el agendamiento de las actividades en sus ventanas de tiempo. 
 
Najafi y Seyed (2006)9 proponen un algoritmo genético para la solución del problema RIP de tal 
manera que se logre la asignación de recursos que permita encontrar una agenda que garantice la 
maximización del valor presente neto del proyecto. De acuerdo con Najafi y Seyed (2006), gran 
parte de las variantes del Resource Investment Problem se enfocan en el aspecto financiero cuyo 
objetivo principal en le programación de proyectos es la maximización del valor presente neto. 
Autores como Doersch y Patterson (1977), Grinold (1972) y Russell (1970) consideraron el 
problema con dicho objetivo, proponiendo una variante distinta al problema, tales como fechas de 
entrega, limitación de recursos y demás variantes donde se tiene en cuenta el valor del dinero en el 
tiempo, pagos recibidos a medida que el proyecto progresa, etc. 
 
Red de Petri 
Una red de Petri10 es un grafo bipartito con dos tipos de nodos denominados plazas y transiciones. 
Dichos nodos están conectados a través de arcos dirigidos. Se aclara que los arcos conectan los 
 
8 Verbeeck, C. Van Peteghem, V. Vanhoucke, M. Vansteenwegen, P. A Metaheuristic Solution Approach for the 
Time-Constrained Project Scheduling Problem. Springer-Verlag Berlin Heideberg. 2016. 
9 Najafi, A. Seyed, T.N. A Genetic algorithm for resource investment problema with discounted cash flows. Applied 
Mathematics and Computation 183. 1057-1070. 2006. 
10 W.M.P. Van der Aalst. Petri Net Based Scheduling. OR Spektrum, Springer-Verlag. 1996. 
nodos y éstos deben ser de diferentes tipos. Las plazas contendrán un número determinado de tokens, 
los cuales son disparados por las transiciones a las plazas sucesoras. Las plazas usualmente 
representan acciones o condiciones y las transiciones representan eventos. El número necesario de 
tokens para que una transición sea disparada depende del peso de los arcos de entrada, siendo esto 
la condición de verdad para la acción asociada a su correspondiente plaza. La transición será 
disparada si y sólo si, las plazas de entrada de dicha transición contienen tantos o más tokens como 
indiquen los pesos de los arcos de entrada de la transición en cuestión. 
 
Los arcos conectan las plazas con las transiciones y las transiciones con las plazas, sin que sea 
permitido conectar dos plazas o dos transiciones a través de un arco. Al ser disparada una transición, 
el cambio de estado de la red se registra cuantificando la cantidad de tokens en cada plaza, esto es 
conocido como marcaje11, el cual es definido como un arreglo que contiene en cada posición el 
número de tokens en cada plaza, lo cual representa uno de todos los posibles estados de la red. Se 
dice que un marcaje M’ es alcanzable desde un estado M si y sólo si, existe una secuencia válida de 
transiciones que lleven la red del estado M al M’. 
 
Diversas modificaciones se han propuesto a las clásicas redes de Petri, tales como las 
temporizadas12, redes de Petri con colores13, estocásticas14, con prioridades, etc. Las distintas 
modificaciones propuestas para las redes de Petri se resumen en la figura 1. 
 
Figura 1. Variantes de las Redes de Petri 
 
Fuente: Zhou, K. Zain, A. 2016. 
 
Gran cantidad de sistemas complejos pueden ser modelados y analizados utilizando redes de Petri 
de alto nivel. De acuerdo con Reddy et. al. (2001) y Zhou & Zain (2016), las diversas clases de 
redes de Petri han sido utilizadas exitosamente en modelamiento de prototipos de software, 
 
11 Mejía, G. Montoya, C. Applications of Resource Assignment and Scheduling with Petri Nets and Heuristic Search. 
Springer Science+Business Media. 2010. 
12 Aalst, W.M.P. Petri Net Based Scheduling. OR Spektrum. Springer-verlag. 1996. 
13 Jensen, K. Kristensen, L. Coloured Petri nets: modelling and validation of concurrent systems. Springer, Berlin. 
2009. 
14 Reddy, J. Kumanan, S. Krishnaiah, C. Application of Petri Nets and a Genetic Algorithm to Multi-Mode Multi-
Resource Constrained Project Scheduling. International Journal of Advanced Manufacturing Technology. Springer 
Verlag London.2001. 
protocolos de comunicación (Co, Swami, Chen, 2012), para el diseño de sistemas logísticos y 
organizaciones administrativas, así como redes de Petri temporizadas y con colores se han utilizado 
para modelar sistemas flexibles de manufactura (Ha & Suh, 2008), sistemas de manejo de materiales 
y máquinas en general. 
 
Las redes de Petri también han sido aplicadas en la solución de problemas de secuenciación de 
múltiples proyectos con recursos limitados RCMPSP, como es el caso de Zhuang, Song et. al (2008), 
quienes utilizaron las redes de Petri coloridas y temporizadas para modelar el ambiente 
multiproyecto donde obtienen soluciones cercanas al óptimo y concluyen que utilizar redes de Petri 
temporizadas y coloridas no solo resulta factible sino efectivo. 
 
Hu y Wang (2014) obtienen también resultados competitivos respecto a otros algoritmos propuestos 
para el RCMPSP. Estos autores realizan modificaciones a la red de Petri formada con la información 
del proyecto añadiendo plazas y reemplazando transiciones de liberación de recurso con transiciones 
de retraso. 
 
Kao, Wang, Dong et. al. utilizan el modelamiento a través de redes de Petri para considerar eventos 
inesperados en la ejecución de un portafolio de proyectos. El marco de solución propuesto es 
beneficioso ya que en la evaluación del desempeño del agendamiento se cuenta con una perspectiva 
multi criterio con el balance entre duración del proyecto y costo. 
 
Beam Search 
 
El algoritmo Beam Search, es la versión más general de una heurística cuyo propósito fundamental 
es la búsqueda controlada de la solución de un problema combinatorio expandiendo solo una 
cantidad de nodos determinada en cada nivel del árbol de branch & bound. Este enfoque heurístico 
ha sido utilizado en problemas de secuenciación de trabajos (Bautista, et. al, 2008) 15, (Bautista, 
Corominas, 1996) (Blum, 2005). Della Croce y demás aplicaron una versión modificada16 del 
método para resolver un problema de secuenciación de dos máquinas y el problema de optimización 
combinatoria conocido como el p-median problem. Reyes, Araya et. al. (2016) aplicaron el enfoque 
del Beam Search para resolver un problema de Set Covering17. 
 
Algoritmo A * 
 
Este algoritmo consiste en una modificación del conocido Branch & Bound. En un problema 
combinatorio, por ejemplo, progresivamente condicionar una variable a tomar un valor entero abre 
un conjunto de posibilidades, lo cual es representado como un nodo en un árbol cuya expansión 
crece exponencialmente (Velez-Gallego, et al. 2016). 
 
15 Bautista, J. Pereira, J. et. al. A beam search approach for the optimization versión of the car sequencing problema. 
Springer Science+Business Media. 2007. 
16 Della Croce, F. et. al. Recovering Beam Search: enhancing the beam search approach for combinatorial 
optimization problems. Journal of heuristics. 10:89-104. 2004. 
17 Reyes, V. Araya, I. et. al A Beam Search approach to the Set Covering Problem. Springer International Publishing 
Switzerland. 2016. 
 
Considerando la desventaja mencionada, el A* Search modifica el proceso de ramificación y 
acotamiento controlando el crecimiento del árbol de exploración18. El proceso de exploración 
consiste en expandir únicamente los nodos más promisorios en el árbol de acuerdo a una función 
heurística asociada al objetivo que se quiere lograr en el problema de optimización. El criterio de 
expansión Best-first selecciona el nodo que tenga el mejor valor de la función heurística 
mencionada. 
 
El nodo raíz representa el nodo Mo y sus nodos sucesores se van generando a medida que se realiza 
la generación de sus nodos hijos. La función heurística que contempla el criterio de exploración es 
de la forma 𝑓(𝑀) = 𝑔(𝑀) + ℎ(𝑀) siendo g(M) el valor de la función objetivo del nodo actual 
(makespan, costo de recurso, etc) desde el nodo inicial Mo hasta dicho nodo nodo M. h(M) es un 
estimado del valor de la función objetivo desde el nodo M hasta el nodo que representaría el final 
del problema Mf. Aquellos nodos que tengan los mejores valores de f(M) tendrán prioridad en la 
expansión del árbol (espacio de búsqueda) de modo tal que la expansión avance en profundidad más 
que horizontalmente para forzar el método a alcanzar el nodo objetivo (Lee y DiCesare, 1994). 
 
La función h(M) es admisible si subestima el verdadero valor de la función objetivo de alcanzar el 
nodo final, por lo cual, si h(M) es admisible para todos los nodos, el A* Search garantiza optimalidad 
aunque tendría complejidad exponencial en cuanto a tiempo y esfuerzo computacional (Mejía y 
Odrey, 2005). Debido a esta dificultad, diversos autores han propuesto modificaciones a este 
algoritmo, tales como Lee y DiCesare (1995), Mejía y Odrey (2005), Xion y Zhou (1998), Yu et. 
al. (2003) y Mejía, Sánchez, Niño y Figueroa (2013). Entre dichas mejoras se encuentran cotas más 
herméticas para la función h(M), reducción del espacio de búsqueda por recorte de nodos no 
promisorios, incluso la incorporación de cotas superiores e inferiores para mejorar la dirección de 
la búsqueda. 
 
En la literatura existente se encuentra que las modificaciones propuestas para el Algoritmo A* 
incluyen adoptar el criterio Depth-First (Huang, Sun y Sun, 2008), poda selectiva de nodos para 
mejor reducción del espacio de búsqueda (Abdallah, Elmaraghy, 1998. Elmakkawy y Elmaraghy, 
2003. Kim, Suzuki y Narikiyo, 2007). Otras tendencias respecto al algoritmo se enfocan en el 
estudio de las funciones heurísticas utilizadas, donde se encuentra que han sido propuestas tanto 
admisibles como no admisibles. De acuerdo con Mejía, Niño (2017), las funciones admisibles (que 
garantizarían soluciones óptimas), son basadas por lo general en características de las redes de Petri, 
tales como la ruta más corta, mientras que funciones no admisibles utilizan reglas de despacho19, 
cabe agregar que al ser un método heurístico, en algún momento de la expansión del árbol pudo 
haber podado la solución óptima. 
 
 
 
18 Mejía, G. Montoya, C. Applications of Resource Assignment and Scheduling with Petri Nets and Heuristic Search. 
Springer Science+Business Media. 2010. 
19 Mejía, G. Niño, K. A new hybrid filtered beam search algorithm for deadlock-free scheduling of flexible 
manufacturing systems using Petri Nets. Computers & Industrial Engineering 108. 2017. 
5. METODOLOGÍA 
 
5.1. Propuesta del Modelo Matemático Multiproyecto 
 
Tal como se mencionó anteriormente, en la revisión bibliográfica no se encontró estudios del RACP 
multiproyecto, por lo cual se propone esta variante y el presente modelo matemático correspondiente 
a la situación mencionada en la descripción del problema. 
𝑰𝒏𝒅𝒊𝒄𝒆𝒔 
j: actividades de cada proyecto. 
k: índice para el tipo de recurso. k = 1…K con K recursos totales. 
t: índice relacionado con el tiempo (unidad de tiempo depende del contexto del proyecto). t = 
0,1,2,3…T. T representa el largo del horizonte de planeación de todo el conjunto de proyectos, 
consistiendo en la fecha de entrega del proyecto con tiempo límite más alejado). 
S: índice relacionado a cada proyecto a ejecutar. 
𝑷𝒂𝒓á𝒎𝒆𝒕𝒓𝒐𝒔 
T: Horizonte de planeación. Fecha de entrega más alejada. 
Ck: costo unitario del recurso tipo k. 
djs: duración de la actividad j del proyecto s. 
rkjs: cantidad de recurso tipo k requerido para la ejecución de la actividad j del proyecto s. 
Pjs: conjunto de predecesores inmediatos de la actividad j del proyecto s. 
𝐸𝑆𝑗𝑠: tiempo de inicio temprano de la actividad j del proyecto s 
𝐿𝑆𝑗𝑠: tiempo de inicio más tardío de la actividad j del proyecto s. 
𝑽𝒂𝒓𝒊𝒂𝒃𝒍𝒆𝒔 𝒅𝒆 𝑫𝒆𝒄𝒊𝒔𝒊ó𝒏 
𝑋𝑗𝑡𝑠: variable binaria. Toma valor de 1 si la actividad j del proyecto s, inicia en el tiempo t. 0 de lo 
contrario. t ∈ [ ESjs , LSjs ]. 
𝑅𝑘: variableque indica la cantidad de unidades de recurso tipo k requeridas en todo el conjunto de 
proyectos (cantidad disponible de recurso tipo k que se debe asignar a lo largo del conjunto de 
proyectos). 
𝐹𝑂:𝑀𝑖𝑛 ∑ 𝐶𝑘𝑅𝑘
𝑘∈𝐾
 
∑ 𝑋𝑗𝑡𝑠
𝐿𝑆𝑗𝑠
𝑡=𝐸𝑆𝑗𝑠
= 1 ∀ 𝑗 ∈ 𝐽, 𝑠 ∈ 𝑆 (1) 
∑ 𝑋𝑖𝑡𝑠
𝐿𝑆𝑖𝑠
𝑡=𝐸𝑆𝑖𝑠
∗ (𝑡 + 𝑑𝑖𝑠) ≤ ∑ 𝑋𝑗𝑡𝑠
𝐿𝑆𝑗𝑠
𝑡=𝐸𝑆𝑗𝑠
∗ 𝑡 ∀ 𝑠 ∈ 𝑆, (𝑖, 𝑗) ∈ �⃑� 𝑗,𝑠 (2) 
∑ ∑ ∑ 𝑟𝑘𝑗𝑠 ∗ 𝑋𝑗𝑦𝑠
𝑡
𝑦=(𝑡−𝑑𝑗𝑠)𝑗∈𝐽𝑠∈𝑆
≤ 𝑅𝑘 ∀ 𝑘 ∈ 𝐾 , 𝑡 ∈ (0… 𝑇) | 𝑦 > 0 (3) 
𝑋𝑗𝑡𝑠 ∈ {0, 1} ∀ 𝑗 ∈ 𝐽, 𝑡 ∈ [ ESjs , LSjs ] , 𝑠 ∈ 𝑆 (4) 
𝑅𝑘 ≥ 0 ∀ 𝑘 ∈ 𝐾 𝑐𝑜𝑛 𝑅𝑘 ∈ Ζ+ (5) 
Es importante mencionar que este problema y en general los problemas de proyectos implican un 
pre-procesamiento de las instancias, ya que en esta formulación es necesario calcular como datos 
de entrada los tiempos de inicio tempranos y tardíos (ESis, LSis) de cada actividad. Dentro de este 
procesamiento está contemplada la información de fechas de inicio máxima de los proyectos y sus 
respectivas fechas de entrega, por lo tanto, con ES y LS siendo calculados respecto a dichas fechas, 
un proyecto tendrá entonces como intervalo posible de ejecución el tiempo de inicio de su primera 
actividad y su fecha de entrega 𝐷𝑢𝑒𝐷𝑎𝑡𝑒𝑠 así [ 𝐸𝑆0𝑠 , 𝐷𝑢𝑒𝐷𝑎𝑡𝑒𝑠 ]. Los tiempos de terminación e 
inicio tardíos de las actividades de cada proyecto están calculados respecto a la fecha de entrega de 
cada proyecto, por esto se cumple: 
[ 𝐸𝑆0𝑠 , 𝐷𝑢𝑒𝐷𝑎𝑡𝑒𝑠 ] = [ 𝐸𝑆0𝑠 , 𝐿𝐹𝑁𝑠 ] 
Donde 𝐿𝐹𝑁𝑠 corresponde a la fecha de terminación tardía de la última actividad del proyecto s. 
La función objetivo del problema establece la minimización del costo total de los recursos asignados 
al conjunto de proyectos. 
La restricción (1) refuerza la condición de que una actividad de cada proyecto inicia y se realiza una 
sola vez. La restricción (2) establece las relaciones de precedencia entre las actividades de cada 
proyecto s. La restricción (3) permite determinar la cantidad de recurso de cada tipo que debe ser 
asignada al conjunto de proyectos (disponibilidad de recursos). Las restricciones (4) y (5) 
respectivamente definen la naturaleza binaria de las variables de decisión relacionadas con tiempo 
de inicio de las actividades de cada proyecto y la cantidad entera de recurso necesaria para el 
horizonte de planeación. 
El modelo matemático fue implementado en Python y se utilizó el optimizador Gurobi para obtener 
soluciones óptimas de las instancias propuestas. Ver capítulo resultados. 
 
 
 
 
Modelo Matemático sin Tiempos de Inicio Tempranos y Tardíos. 
 
También se presenta el modelo matemático indexado en tiempo que no incluye los tiempos de inicio 
tempranos y tardíos de las actividades de todos los proyectos. En esta formulación se hacen 
explícitas las condiciones de cumplimiento de fechas de entrega de cada proyecto y las fechas 
permitidas de inicio de los mismos. 
 
Utilizando los mismos parámetros de la formulación anterior, a excepción de los ES y LS, la 
formulación es la siguiente: 
 
𝐹𝑂:𝑀𝑖𝑛 ∑ 𝐶𝑘𝑅𝑘
𝑘∈𝐾
 
∑ 𝑋𝑗𝑡𝑠
𝑡∈[0, 𝑇]
= 1 ∀ 𝑗 ∈ 𝐽, 𝑠 ∈ 𝑆 (1) 
 
∑ 𝑋𝑖𝑡𝑠
𝑡∈[0, 𝑇]
∗ (𝑡 + 𝑑𝑖𝑠) ≤ ∑ 𝑋𝑗𝑡𝑠
𝑡∈[0, 𝑇]
∗ 𝑡 ∀ 𝑠 ∈ 𝑆, (𝑖, 𝑗) ∈ �⃑� 𝑗,𝑠 (2) 
 
∑ (𝑋𝑁𝑡𝑠 ∗ 𝑡)
𝑡∈[0, 𝑇]
+ 𝑑𝑁𝑠 ≤ 𝑇𝑠 ∀ 𝑠 ∈ 𝑆 (3) 
 
∑ 𝑋1𝑡𝑠
𝑡∈[0, 𝑇]
≥ 𝑡𝑜𝑠
 ∀ 𝑠 ∈ 𝑆 (4) 
 
∑ ∑ ∑ 𝑟𝑘𝑗𝑠 ∗ 𝑋𝑗𝑦𝑠
𝑡
𝑦=(𝑡−𝑑𝑗𝑠)𝑗∈𝐽𝑠∈𝑆
≤ 𝑅𝑘 ∀ 𝑘 ∈ 𝐾 , 𝑡 ∈ (0… 𝑇) | 𝑦 > 0 (5) 
 
𝑋𝑗𝑡𝑠 ∈ {0, 1} ∀ 𝑗 ∈ 𝐽, 𝑡 ∈ [ 0 , 𝑇] , 𝑠 ∈ 𝑆 (6) 
𝑅𝑘 ≥ 0 ∀ 𝑘 ∈ 𝐾 𝑐𝑜𝑛 𝑅𝑘 ∈ Ζ+ (7) 
 
El horizonte de planeación es el intervalo 𝑡 ∈ [ 0 , 𝑇] con T igual a la máxima fecha de entrega 
entre los distintos proyectos. La restricción (1) establece que cada actividad puede iniciar y 
realizarse una sola vez en todo el horizonte de planeación. La restricción (2) asegura el 
cumplimiento de las relaciones de precedencia entre actividades. La restricción (3) garantiza el 
cumplimiento de las fechas de entrega de cada proyecto mientras que la restricción (4) establece el 
inicio de cada proyecto a mínimo desde su fecha permitida de inicio. La restricción (5) calcula el 
requerimiento de recurso máximo debido a la ejecución de actividades en simultáneo, lo cual 
representa la disponibilidad de recurso que debe asegurarse a lo largo del horizonte de planeación 
del conjunto de proyectos. Por último, las restricciones (6) y (7) indican la naturaleza binaria y 
entera de las variables inicio de actividad y requerimiento de recurso. 
5.2. Modelamiento mediante Redes de Petri 
 
En este trabajo se utilizaron las redes de Petri temporizadas en las plazas, consistiendo en que cada 
plaza retiene los tokens que alberga por un tiempo determinado, asociando dicho tiempo a la 
duración de las distintas actividades del proyecto. Las redes de Petri utilizadas en este proyecto 
además de la temporización, conservan características como las relaciones de precedencia entre 
actividades, el modelamiento de recursos renovables que son el tipo de recurso incluido en este 
problema y tan solo un modo de realización de las actividades (single skill). 
 
En la figura 1 se muestra un ejemplo de la representación de un proyecto a través de una red de Petri 
con las características descritas en la tabla 1. 
 
Tabla 1. Actividades, duraciones y requerimientos de recurso. 
Actividad Sucesor Modo Duración Recurso 1 Recurso 2 
A B,C 1 8 2 0 
B D 
1 6 1 0 
2 4 2 0 
C D 
1 6 0 3 
2 3 0 2 
D - 1 8 0 0 
Fuente: Mejía, Sánchez, Niño y Figueroa. 2013. 
 
Figura 2. Representación del Proyecto Mediante una Red de Petri 
 
Fuente: Mejía, Sánchez, Niño y Figueroa. 2013. 
 
Se puede observar en la figura 2 que todas las características señaladas en la tabla 1 son 
representadas en la red de Petri. Éstas incluyen el requerimiento de recursos renovables, como es el 
caso de los requeridos en las actividades A (P13), recursos no renovables como el requerido por la 
actividad C, la cual cuenta con dos modos de ejecución mutuamente excluyentes (P7 modo 2, P5 
modo 1), múltiples modos y recursos renovables en la actividad B (P12 modo 2 y P10 modo 1), se 
representan las relaciones de precedencia de las actividades del proyecto (D depende de B y C) así 
como el caso de la actividad D que no requiere ningún tipo de recurso. 
 
Entre las ventajas del modelamiento de los proyectos a través de Redes de Petri se encuentran20: 
 
 Las redes de Petri y sus extensiones capturan la esencia de la mayoría de características de 
los proyectos tales como relaciones de precedencia, restricciones de recurso, retrasos de 
tiempo y demás. 
 La lógica de entendimiento es relativamente sencilla. 
 El agendamiento de actividades puede ser llevado a cabo con técnicas de optimización cuyas 
búsquedas serían realizadas sobre el espacio de estados de la red de Petri. 
 Es posible modelar interrupciones y reprocesos debidos a agentes externos, esto 
especialmente en secuenciación de trabajos y proyectos. 
 Las redes de Petri permitirían realizar el ajuste del modelamiento de un único proyecto para 
contemplar contextos multi proyecto gracias a que la lógica de la red de Petri en cuanto a 
estructura y características principales como tipos de recurso y precedencias se conserva en 
el contexto de múltiples proyectos. 
 
5.3. Algoritmo Beam A* Search 
 
En la aplicación de este algoritmo a problemas de programación de proyectos modelados a través 
de redes de Petri, se establece que el espacio de búsqueda será compuesto por cada uno de los 
distintos estados de la red de Petri. A medida que una transición es disparada, los nodos hijos 
representarán cada una delas posibles rutas (bifurcaciones) que se desprendan del disparo de dicha 
transición. De esta manera es que se genera el árbol de branch and bound, donde encontrar la 
secuencia de transiciones que lleve la red de Petri desde el estado inicial hasta el marcaje final (se 
tiene un token en la última plaza), es equivalente a generar un agendamiento de las actividades del 
proyecto. 
La poda inteligente de los nodos del espacio de búsqueda evita la exploración de todo el espacio de 
estados y tiene las siguientes ventajas: 
 La posibilidad de controlar la expansión del árbol de branch & bound también en cuanto a 
profundidad. 
 La utilización del algoritmo Beam A* Search es conveniente dada la gran cantidad de 
estados que presentaría una red de Petri que represente un proyecto, así pues, aunque el 
método puede obtener soluciones óptimas, la complejidad del problema llevaría a optar por 
bajos y competitivos tiempos computacionales a expensas de optimalidad para instancias 
grandes, lo cual se lograría con las ventajas de este algoritmo. 
 
 
20 Mejía, G. Niño, K. Montoya, C. et. al. A Petri Net-based Framework for Realistic Project Management and 
Scheduling: An application in animation and videogames. Computers and Operations Research. 2016. 
Cabe resaltar que el Beam A* Search ha sido utilizado exitosamente en problemas de secuenciación 
de trabajos modelados a través de redes de Petri obteniendo buenos resultados en cuanto a calidad 
de la solución y tiempo computacional (Mejía y Odrey, 2005) (Mejía y Montoya, 2010) y en 
problemas de programación de proyectos con recursos limitados con múltiples modos (MSRCPSP) 
(Mejía, Sánchez, Niño y Figueroa, 2013). 
 
El algoritmo Beam A* Search utilizado en los trabajos mencionados estaba enfocado en la 
minimización del makespan del proyecto con la siguiente lógica21: 
 
a. Cálculo de la función heurística. 
La función es de la forma 𝑓(𝑀) = 𝑔(𝑀) + ℎ(𝑀). Dado que el objetivo del MSRCPSP es la 
minimización del makespan, la función ℎ(𝑀) es un estimado del tiempo que resta para la 
finalización del proyecto desde el marcaje M, tomando como referencia la ruta crítica, mientras que 
𝑔(𝑀) es el tiempo transcurrido desde el marcaje inicial hasta el marcaje actual M. La cota inferior 
es el cálculo del tiempo restante, teniendo en cuenta la relajación de la restricción de recursos y 
disparando las transiciones de acuerdo a una regla de prioridad. De este modo también es calculada 
la cota superior de cada marcaje. 
 
b. Expansión y búsqueda. 
Como parámetro de entrada del algoritmo se tiene la magnitud del rayo de expansión (Beam), el 
cual consiste en el número de nodos máximo a expandir en cada nivel. El algoritmo a medida que 
genera los hijos de los nodos del árbol, va registrando en una lista denominada OPEN aquellos 
nodos generados pero aún no expandidos, almacenados en orden ascendente respecto la cota 
inferior. Se da prelación al nodo de mayor profundidad y con mejor cota superior en caso de 
empates. 
 
La información de los nodos ya explorados es guardada en la lista CLOSE, por lo cual el algoritmo 
toma el primer nodo de la lista OPEN, genera sus respectivos hijos y lo lleva a la lista CLOSE. 
 
c. Pseudocódigo 
El funcionamiento puede describirse como sigue (tomado de Mejía, Niño, et. al. 2013): 
 
1. Establece el marcaje inicial Mo como el marcaje actual, se incluye en la lista OPEN. 
2. Establece el conjunto de transiciones activas para el marcaje actual. 
3. Genera el conjunto de marcajes (nodos) hijos del marcaje actual disparando cada una de las 
transiciones activas. Luego de generar esta expansión calcula las cotas superior e inferior de 
cada marcaje hijo. 
4. Inserta los nodos hijos en la lista OPEN en la posición derecha de acuerdo a sus valores de 
cota superior e inferior. Retira el marcaje actual de la lista OPEN y lo incluye en la lista 
CLOSE. 
 
21 Mejía, G. Niño, K. Montoya, C. et. al. A Petri Net-based Framework for Realistic Project Management and 
Scheduling: An application in animation and videogames. Computers and Operations Research. 2016. 
5. Si la lista OPEN está vacía el algoritmo termina con falla intentando buscar el marcaje final. 
En caso contrario, selecciona el primer marcaje disponible en la lista OPEN si es susceptible 
de expansión, es decir, si el número de marcajes expandidos en su nivel no supera la 
magnitud del beam. Establece el marcaje expandido como marcaje actual. 
6. Borra aquellos marcajes que no son susceptibles de expansión. 
7. Si el marcaje actual es igual al marcaje final, la construcción de la solución se realiza 
retrocediendo desde el nodo final, rastreando su nodo padre hasta llegar al nodo inicial, 
siendo esto la secuencia de transiciones generada (equivalente al agendamiento de 
actividades). Devuelve el valor f(M) del marcaje final. 
8. Mientras no se encuentre el marcaje final, vuelve al paso 2. 
 
5.4. Estructura del Algoritmo de Solución Propuesto 
 
El método de solución del problema propuesto en este trabajo se ideó bajo el enfoque tradicional de 
solución del RACP que se encuentra en la literatura para un solo proyecto, consistiendo en 
iterativamente realizar una asignación de recursos y posteriormente solucionar un problema de 
programación de proyectos con recursos limitados estableciendo la duración del proyecto. Si la 
duración excede la fecha de entrega del proyecto, la asignación es infactible y se requiere aumentar 
la cantidad de recursos, repitiendo este proceso hasta encontrar una asignación factible de recursos. 
En este enfoque de solución autores como Demeulemeester (1995) y Rodrígues y Yamashita (2010) 
han propuesto métodos exactos donde realizan iterativamente cortes en el espacio de búsqueda de 
las cantidades de los tipos de recursos dentro de una región limitada por una línea incumbente que 
representa las combinaciones de recurso con el mismo valor objetivo de costo total como se muestra 
en la figura 2. El vector de recurso es evaluado por un método de solución del RCPSP para saber si 
es factible o no. 
Figura 2. Línea incumbente CD en el espacio de valores de recurso R1 y R2 
 
Fuente: Rodriguez. S. Yamashita, D. 2015. 
En total se propusieron cuatro versiones del método de solución que funcionan bajo el enfoque de 
los métodos exactos mencionados anteriormente. 
 Métodos lógicos: 
o AStar-Add 
o AStar-Remove 
 Métodos Exhaustivos 
o G-Add 
o G-Remove 
En los dos primeros métodos, las decisiones de aumentos de recurso se realizan mediante el uso de 
indicadores con una lógica de utilización de recurso. Los últimos dos no tienen en cuenta dichos 
indicadores sino que realizan una búsqueda exhaustiva, explorando todas las posibilidades de 
aumento de recurso y seleccionando el aumento que permite la mayor reducción de la duración del 
proyecto, lo cual implica un considerable aumento del tiempo computacional. 
El método propuesto en este trabajo consiste en los siguientes pasos: 
1. Lectura de información del problema y modelamiento del proyecto como una red de Petri. 
2. Calcular el vector de recurso inicial a asignar. Para este cálculo se utilizó la cota inferior22 
propuesta por Drexl & Kimms (2001). Este será el vector de recurso mínimo necesario para la 
ejecución de las actividades del proyecto. 
𝐶𝑜𝑡𝑎 𝐼𝑛𝑓𝑒𝑟𝑖𝑜𝑟: R k = 𝑚𝑎𝑥 {max𝑗 ∈𝐽 𝑟𝑗𝑘 , ⌈
∑ 𝑟𝑗𝑘∗𝑑𝑗𝑗 ∈𝐽
𝑚𝑖𝑛{𝑇 , ∑ 𝑑𝑗𝑗 ∈𝐽, 𝑟𝑗𝑘>0 }
⌉} 
3. Llamar la sub rutina que calcula la duración del proyecto teniendo en cuenta la limitación del 
recurso asignado. Ver la sub rutina makespan. 
4. Establecer el denominado recurso cuello de botella de acuerdo al criterio seleccionado. Ver 
determinación del recurso crítico. Añadir una unidad de recurso al recurso crítico. 
(Si el método es exhaustivo se omite este paso y se evalúa el efectode añadir una unidad a todos 
los tipos de recurso, uno a la vez). 
5. Llamar la sub rutina makespan para calcular la duración del proyecto con la nueva asignación 
de recursos. Si la duración del proyecto es menor a la fecha de entrega, ir al paso 6. De lo 
contrario ir al paso 4. 
6. Realizar un proceso de búsqueda local para determinar a cuál de los recursos puede reducirse su 
cantidad sin afectar el cumplimiento de la fecha de entrega. 
7. Cuando no hay más opción de reducir el recurso, terminar. Recuperar secuencia de transiciones 
y vector final de recurso. 
 
 
22 Drexl, A. Kimms, A. Optimization guided lower and upper bounds for the resource investment problem. Journal of 
the operational research society. 2001. 
Sub Rutinas Makespan 
a. Disparo de Transiciones según regla de despacho. 
Este método consiste principalmente en el disparo de las transiciones activas seleccionadas 
de acuerdo a la regla de despacho seleccionada. Una vez disparada la última transición, se 
retorna el valor de la duración calculada del proyecto. 
 
Cabe agregar que se tiene en cuenta las restricciones de precedencia y la limitación del 
recurso asignado. Sin embargo, al no ser una aproximación robusta al vector óptimo de 
recurso, el tiempo computacional de esta subrutina es considerablemente bajo, pero, la 
cantidad asignada de recurso será aproximada por exceso. 
 
b. Beam A* Search 
Tal como se mencionó anteriormente, este método tiene por objetivo la minimización de la 
duración del proyecto asumiendo los recursos asignados como limitados. No se optó por 
modificar este algoritmo para establecer una función heurística basada en costo por las 
mencionadas dificultades que esto conlleva en cuanto a admisibilidad. 
 
El Beam A* Search explora la red de Petri con las características del proyecto y con el 
recurso asignado en cada iteración, determina la duración del proyecto, sirviendo como 
método robusto de determinación de la factibilidad del vector de recurso. 
 
El algoritmo también hace uso de las siguientes reglas de despacho: 
 
 SPT: selecciona la transición que da paso a la actividad con la menor duración. 
 LPT: selecciona la transición que da paso a la actividad con la mayor duración. 
 MWR (most remaining work time): selecciona la transición que da paso a la 
actividad con mayor tiempo remanente. El tiempo remanente es el tiempo restante 
desde dicha actividad hasta el final del proyecto. 
 LWR (least remaining work time): selecciona la transición que da paso a la actividad 
con menor tiempo remanente. 
 SPR: basada en un indicador de criticidad del recurso en el tiempo. Selecciona la 
actividad con mayor valor del indicador de criticidad descrito a continuación. 
Se propuso una regla de despacho denominada SPR para considerar no solo aspectos como la 
duración de las actividades sino el uso que hacen de los recursos. 
Consiste en calcular un indicador de criticidad del uso del recurso en el tiempo como el costo total 
de requerimiento de recurso sobre la holgura de la actividad j: 
𝐼𝑛𝑑𝑟𝑒𝑐 =
{
 
 
 
 
∑ 𝑟𝑗𝑘 ∗ 𝐶𝑘𝑗 ∈𝐽
𝐻𝑜𝑙𝑔𝑢𝑟𝑎𝑗
=
∑ 𝑟𝑗𝑘 ∗ 𝐶𝑘𝑗 ∈𝐽
𝐿𝑆𝑗 − 𝐸𝑆𝑗
, 𝑠𝑖 𝐿𝑆𝑗 > 𝐸𝑆𝑗
∑ 𝑟𝑗𝑘 ∗ 𝐶𝑘
𝑗 ∈𝐽
 , 𝑠𝑖 𝐿𝑆𝑗 = 𝐸𝑆𝑗
}
 
 
 
 
 
Este indicador es mayor para las actividades críticas, por lo cual da prioridad al cumplimiento de la 
ruta crítica mientras que se esperaría que las actividades que no son críticas tiendan a seleccionarse 
en un momento posterior dentro del intervalo que permite su holgura. Las reglas basadas en tiempo 
tienden a disparar las transiciones de tal manera que las actividades inicien en su tiempo de inicio 
más temprano, mientras que con esta regla se intenta permitir en el agendamiento de las actividades 
que se logre mayor flexibilidad en la agenda al iniciar dentro del intervalo de holgura de las 
actividades, buscando así la posibilidad de necesitar menor asignación de recursos al permitir a las 
actividades dicho margen de maniobra. 
Determinación del Recurso Crítico 
Se establece que el recurso cuello de botella es aquel cuya cantidad representa la mayor limitante 
para la duración del proyecto y cuyo aumento permitiría la reducción del makespan. Para determinar 
el recurso crítico o cuello de botella, se cuenta con tres criterios para determinar un indicador de 
utilización de recurso. 
1. Utilización temporal: es la relación entre la ponderación del recurso requerido con la 
duración de las actividades que lo requieren y el recurso actualmente asignado 𝑅𝑘 por la 
fecha de entrega. 
𝑈𝑡𝑖𝑙𝑖𝑧𝑎𝑐𝑖ó𝑛 𝑡𝑒𝑚𝑝𝑜𝑟𝑎𝑙 =
∑ 𝑟𝑗𝑘 ∗ 𝑑𝑗𝑗 ∈𝐽
𝑅𝑘 ∗ 𝐷𝑢𝑒𝐷𝑎𝑡𝑒
 
El recurso cuello de botella será aquel que presente mayor valor en su indicador de utilización 
temporal. 
2. Utilización: es la relación entre la sumatoria del requerimiento de recurso y la cantidad 
actualmente asignado 𝑅𝑘. 
𝑈𝑡𝑖𝑙𝑖𝑧𝑎𝑐𝑖ó𝑛 =
∑ 𝑟𝑗𝑘𝑗 ∈𝐽
𝑅𝑘
 
El recurso crítico será el de mayor indicador de utilización. 
3. Sensibilidad: es el cálculo de la variación en el indicador de utilización temporal ante 
cambios en la duración permitida del proyecto (se tomó como base su fecha de entrega). 
𝑆𝑒𝑛𝑠𝑖𝑏𝑖𝑙𝑖𝑑𝑎𝑑 =
∑ 𝑟𝑗𝑘 ∗ 𝑑𝑗𝑗 ∈𝐽
𝐷𝑢𝑒𝐷𝑎𝑡𝑒 − 1
−
∑ 𝑟𝑗𝑘 ∗ 𝑑𝑗𝑗 ∈𝐽
𝐷𝑢𝑒𝐷𝑎𝑡𝑒
 
𝑅𝑘
 
Este indicador refleja qué tan sensible es el requerimiento de recurso ante cambios en la fecha de 
entrega, con lo cual, el recurso crítico será el que presente mayor indicador de sensibilidad. 
Enfoques de Aproximación a la solución óptima 
Se utilizaron dos enfoques para la aproximación al vector óptimo de recuso. 
a. Enfoque de Aumento de Cota Mínima 
Se utiliza la sub rutina Makespan basada en el algoritmo Beam A* Search, para establecer la 
duración del proyecto, tratando de que al ser utilizado éste algoritmo robusto en el presente método, 
se logre alcanzar la fecha de entrega sin asignar recursos en exceso. 
La figura 3 ilustra la secuencia de pasos para la aplicación del método propuesto bajo este enfoque. 
Figura 3. Secuencia del Método Propuesto – Enfoque Cota Mínima 
 
Fuente: Elaboración propia. 
 
b. Enfoque de Reducción de Cota Superior 
Consta de dos fases. Primero se utiliza la sub rutina Disparo de transiciones según regla de despacho 
hasta establecer una cantidad de recursos que garantiza para dicha subrutina el cumplimiento de la 
fecha de entrega. Se entiende que las reglas de despacho proporcionan un agendamiento de 
actividades y un vector de recurso factible pero con excesos de asignación. 
La segunda fase es en proceso de mejora en la estimación del vector recurso a través del algoritmo 
Beam A* Search, el cual obtendrá iterativamente la duración del proyecto a medida que se reduce 
la cantidad de recurso asignada a aquel que resulte ser el más costoso no crítico. Se utilizan los 
criterios de criticidad de modo invertido para establecer el recurso no crítico. Este proceso se repetirá 
hasta el punto en que la reducción de recurso ya no permita cumplimiento de la fecha de entrega. 
La figura 4 ilustra la secuencia de pasos del método propuesto bajo este enfoque. 
Figura 4. Secuencia del Método Propuesto – Enfoque Cota Mínima 
 
Fuente: Elaboración propia 
6. RESULTADOS 
 
6.1. Instancias de prueba 
 
Para obtener las instancias del RACP, se pueden modificar las del RCPSP existentes en la literatura 
de acuerdo a la metodología propuesta por Drexl and Kimms (2001), en la cual establecen que las 
características de ambos problemas son similares y el RACP puede hacer uso de los mismos datos 
de relaciones de precedencia y requerimientos de recurso. 
 
Como la fecha de entrega es un parámetro de entrada del RACP, los autores proponen igualar la 
fecha de entrega como mínimo a la duración de la ruta crítica del proyecto o aumentarla de acuerdo 
a un factor DF = Ɵ (Deadline Factor) cuyos valores pueden ser 0, 0.1,0.2, 0.3, 0.4, 0.5. 
𝐷𝑢𝑒𝑑𝑎𝑡𝑒 = (1 + Ɵ) ∗ 𝑀𝑎𝑘𝑒𝑠𝑝𝑎𝑛 
 
Adicional a la fecha de entrega, el RACP requiere costos de los recursos Ck y éstos pueden ser 
determinados como un valor aleatorio uniformemente distribuido con parámetros a=1, b=10, así, 
Ck ~ U[1, 10]. 
 
Se utilizaron dos conjuntos de instancias existentes en la literatura para comparar los resultados del 
método propuesto en problemas de un solo proyecto, con los reportados en la literatura. 
 
Conjunto 1: es el conjunto de instancias PSPLIB23 utilizado por Yamashita, Armentano y Laguna 
(2006) consistente de 30, 60, 90 y 120 actividades con 4, 6 y 8 recursos. El factor de fecha de entrega 
es de 1.2. El factor de recurso es RF=0.25, 0.5, 0.75 y 1. La complejidad de la red es 1.5, 1.8 y 2.1. 
 
Conjunto 2: conjunto de instancias RACP30 utilizado por Van Pethegen y Vanhoucke, quienes lo 
obtuvieron del generador de instancias RANGEN24 compuestas por un proyecto de 30 actividades 
y 4 recursos renovables. Las especificaciones de complejidad de la red (order strenth, Mastor, 1970) 
son de 0.25, 0.5 y 0.75. El factor de recurso indica la densidad de los tipos de recursos utilizados 
por actividad (Pascoe, 1966) y son de 0.25, 0.5 y 0.75. El tamaño del conjunto es de 240 instancias, 
las cuales pueden modificarse expandiendo la duración de la ruta crítica del proyecto de acuerdo al 
factor de fecha de entrega (Deadline Factor Ɵ) con Ɵ = 0, 0.1, y 0.2. El costo de los recursos en un 
valor entero aleatorio según metodología de Drexl & Kimms. Éstas instancias se encuentran 
disponibles en http://www.projectmanagement.ugent.be. 
 
Instancias Propuestas Multi Proyecto 
 
Se proponen instancias multiproyecto construidas teniendo en cuenta las condiciones mencionadas 
en la descripción del problema, por lo cual siguiendo la metodología de Drexl & Kimms se modificó 
el conjunto de instancias de Perez, Posada y Lorenzana (2016), compuestas de 2, 3, 4, 5 y 10 
proyectos con 90, 20, 60, 60 y 10 actividades por proyecto respectivamente. 
 
Adicionalmente se propusieron instancias pequeñas de elaboración propia con un número de 
proyectos y actividades así:3x5, 3x6, 2x10, 2x15, 3x10 y 4x10. A cada combinación de número de 
proyectos y actividades se asignó un total de 4 y 6 recursos. 
 
Las instancias propias fueron resueltas a optimalidad aplicando el modelo matemático propuesto 
mediante Python y utilizando el optimizador Gurobi. Se solucionaron a optimalidad también las 
instancias modificadas de Perez et. al. que comprenden un máximo número de actividades totales 
(nxp) de 60. 
 
Tanto para las instancias propias como para las de Perez et. al. se determinó con un valor aleatorio 
el número de proyectos que inician en el tiempo t=0. Se calculó la duración de cada proyecto y se 
tomó como parámetro el proyecto de mayor duración. D = max{𝐷𝑠} 
El tiempo de inicio 𝑡𝑜𝑠 de cada proyecto que no inicia en t=0 se determinó como un valor aleatorio 
en el intervalo [
𝐷
3
 , 𝐷]. 
Las fechas de entrega fueron establecidas una vez se calculó la fecha inicial, de acuerdo a la 
expansión según el Deadline Factor Ɵ: 
𝐷𝑑𝑎𝑡𝑒𝑠 = 𝑡𝑜𝑠 + (1 + Ɵ) ∗ 𝐷𝑠 
 
23 Kolisch, J. Sprecher, A. PSPLIB – A Project scheduling Project library. European Journal of Operational Research, 
96. 1996. 
24 Demeulemeester, E. Vanhoucke, M. Herroelen, W. RANGEN: A random network generator for activity on the node 
networks. Journal of Scheduling 6: 17-38. 2003. 
http://www.projectmanagement.ugent.be/
Donde Ɵ toma valores de 0.1, 0.2 y 0.3. 
 
6.2. Comparación de Resultados para el RACP de un proyecto 
 
Las pruebas computacionales se realizaron en un computador con procesador Intel Corei3 de 2GHz 
y RAM de 4GB. El algoritmo cuyo pseudocódigo fue descrito anteriormente está programado en 
Java. 
 
Resultados Conjunto 1: se comparan los resultados obtenidos con el método propuesto respecto a 
los algoritmos propuestos por Yamashita (2006), es decir, Scatter Search y los multinicio RMS y 
FMS en las instancias de 4, 6 y 8 recursos con 30 actividades. Se logró resolver las instancias de 
este conjunto, sin embargo, los resultados no son tan competitivos como se esperaba. 
Es importante recalcar que la implementación del método inicialmente no contemplaba la búsqueda 
local que se realiza al finalizar los métodos AStar-Add y AStar-Remove. Dados los resultados al 
realizar esta comparación, se optó por incluir esta búsqueda local como medida para mejorar la 
calidad de la solución. La tabla 2 muestra los resultados para las instancias con 4, 6 y 8 recursos con 
las cuatro versiones del método propuesto incluyendo las versiones que no incluyen la búsqueda 
local mencionada, donde se evidencia el efecto de mejora de la solución a través de dicho 
procedimiento. 
Tabla 2. Comparacion con Scatter Search 
Método Recursos Gap Promedio Gap Mínimo 
Astar Remove sin BL 4 58.30% 6.21% 
 6 48.08% 23.76% 
 8 53.31% 13.98% 
Astar Add sin BL 4 48.60% 12.46% 
 6 42.75% 17.99% 
 8 49.06% 11.98% 
Astar Remove 4 36.17% 9.61% 
 6 32.58% 17.61% 
 8 30.79% 14.79% 
Astar Add 4 47.72% 10.25% 
 6 36.57% 22.87% 
 8 40.64% 22.86% 
G Remove 4 35.93% 9.61% 
 6 30.80% 17.94% 
 8 30.31% 14.79% 
G Add 4 37.79% 12.74% 
 6 29.79% 17.99% 
 8 33.34% 17.25% 
Fuente: elaboración propia 
Se esperaba que para las instancias de menor cantidad de recursos se tuvieran los mejores resultados 
promedio, sin embargo, el desempeño es mejor en las de 6 recursos para 3 de los 4 métodos 
definitivos. Los GAP mínimos si son como se esperaba obtenidos en las instancias de 4 recursos. 
La figura 5 resume los resultados, donde se puede concluir que los métodos con mejor desempeño 
general en estas instancias son los exhaustivos, principalmente G-Remove. La diferencia de 
desempeño entre el método exhaustivo G Remove y el basado en indicadores lógicos Astar Remove 
no es considerable, por lo cual se puede decir que este enfoque de reducción por medio del Beam 
A* Search, de la cota superior de recurso es suficientemente bueno como para igualar a la búsqueda 
exhaustiva. 
Figura 5. Comparación con SS, GAP Mínimo y Gap Promedio 
 
Fuente: elaboración propia 
El efecto de la búsqueda local en las versiones del método basadas en indicadores lógicos es evidente 
en la calidad de la solución a nivel general, pues se observan reducciones en el valor del GAP 
promedio, consistiendo en una mejora del 61%, 47% y 73% en la calidad de la solución para las 
instancias de 4, 6 y 8 recursos respectivamente. 
Efecto de las reglas de despacho y de los indicadores de criticidad de recurso 
Se realizaron pruebas ANOVA para establecer si hay diferencias en los resultados de las versiones 
del método respecto a las reglas de despacho utilizadas. Con una confianza del 95% se concluye 
que para los métodos Astar Add las reglas de despacho si son incidentes (p-value=0,0448), pudiendo 
afirmarse que la regla con mejor funcionamiento en este método es MWR, esto se ilustra en la figura 
6 usando como referente el GAP obtenido en una muestra de instancias. Para esta misma versión se 
encontró que no hay diferencia significativa en los resultados obtenidos con los diferentes 
indicadores de determinación del recurso crítico para realizar la adición de recurso. 
Figura 6. Resultados con Diferentes Reglas de Despacho 
 
Fuente: Elaboración propia 
En la versión Astar Remove no se encontró diferencia significativa en los resultados obtenidos 
utilizando las diferentes reglas de despacho. Para esta versión se utilizaron los indicadores de 
determinación del recurso crítico y sus correspondientes criterios invertidos para establecer el 
recurso no crítico al cual remover una unidad de recurso. Se encuentra que hay evidencia estadística 
para afirmar que no hay efecto en la combinación de indicadores lógicos de criticidad de recurso. 
Para los métodos exhaustivos tampocose encontró impacto en las reglas de despacho, ni en los 
indicadores de recurso crítico y no crítico, esto es explicado debido a que la exploración exhaustiva 
no está ligada a dichos criterios, sino que selecciona un recurso luego de evaluar la reducción lograda 
al agregar a todos, una unidad a la vez. 
 
Resultados Conjunto 2: en las instancias RACP30 de Van Pethegen y Vanhoucke se obtuvieron 
resultados positivos ya que el algoritmo logró en tres versiones evaluadas un GAP promedio del 
orden del 14% y cada versión resolvió a optimalidad un 12%, 13% y 9% del total de 720 instancias 
evaluadas. La tabla 3 muestra los resultados obtenidos con los métodos evaluados y para cada uno 
de los 3 factores de fecha de entrega (DF). 
Tabla 3. Resultados Métodos Propuestos en Instancias RACP30 
 DF 
GAP 
Promedio 
GAP 
mínimo 
GAP 
Máximo Óptimos % Óptimos 
Total 
Óptimos 
Astar Remove 1 11.5% 0.0% 66.9% 38 16% 
87 1.1 14.0% 0.0% 46.7% 21 9% 
 1.2 14.8% 0.0% 48.6% 28 12% 
G Add 1 9.8% 0.0% 59.3% 41 17% 
96 1.1 12.2% 0.0% 45.6% 24 10% 
 1.2 12.8% 0.0% 47.3% 31 13% 
G Remove 1 11.6% 0.0% 64.6% 30 13% 
65 1.1 14.0% 0.0% 43.9% 13 5% 
 1.2 14.8% 0.0% 47.3% 22 9% 
Fuente: Elaboración propia 
Las pruebas de significancia demuestran con un p-value de 0.039 considerando un nivel de 
confianza del 95% que el desempeño de los algoritmos probados es significativamente diferente 
pudiendo afirmarse la superioridad de la versión G Add para este grupo de instancias puesto que en 
este método se observa el menor gap promedio y la mayor cantidad de soluciones óptimas 
encontradas. 
Se esperaba un mejor desempeño de la versión basada en los indicadores lógicos planteados (Astar 
Remove), aunque si bien es superada por el G Add, resulta tener mejores resultados que la versión 
exhaustiva G Remove. En la tabla 4 se presenta el tiempo computacional promedio en segundos, de 
las versiones del método en evaluación. 
 
 
 
Tabla 4. Resultados RACP30 - Tiempo computacional 
 DF 
Tiempo 
Computacional 
(Segundos) 
Desviación 
Estándar 
Astar Remove 1 16.41 14.52 
 1.1 13.77 15.70 
 1.2 11.70 15.78 
G Add 1 61.65 35.01 
 1.1 45.63 30.74 
 1.2 41.52 75.35 
G Remove 1 12.51 9.85 
 1.1 10.49 7.97 
 1.2 8.58 6.55 
Fuente: elaboración propia 
Se aprecia que tal como se esperaría de los métodos exhaustivos, son los que presentan los mayores 
tiempos computacionales. Precisamente la versión G Add es la que requiere mayor tiempo, como 
se esperaba ya que utiliza el algoritmo robusto Beam A* Search en cada iteración del método. Este 
hecho es la principal diferencia en el tiempo computacional al compararlo con el disparo de las 
reglas de despacho en la adición de recursos que se usa en las versiones G Remove y Astar Remove. 
En la figura 7 se ilustra esta afirmación. 
Figura 7. Tiempo Computacional de los Métodos Propuestos. DF=1 
 
Fuente: Elaboración propia 
Como máximo, se registraron tiempos de 331, 276 y 243 segundos necesarios para resolver 
instancias para los factores de expansión DF de 1, 1.1 y 1.2 respectivamente, lo cual permite afirmar 
que los métodos propuestos en este grupo de instancias son competitivos en cuanto a tiempo 
computacional. 
Cabe agregar que el tiempo computacional es más bajo a medida que aumenta el valor del factor de 
expansión de la fecha de entrega. Esto es consistente dado que, a mayor fecha de entrega, se le da 
mayor margen de maniobra a las actividades de tal manera que menor cantidad de actividades 
realizándose simultáneamente posibilitan la asignación de una menor cantidad de recurso, por lo 
cual, se realizan menos llamadas al algoritmo Beam A* Search en la fase del cálculo de la duración 
del proyecto. 
Las figuras 8, 9 y 10 ilustran el comportamiento del tiempo computacional en una escala logarítmica 
(base 10) para cada uno de los factores de expansión de la fecha de entrega (DF) respectivamente 
para los tres métodos utilizados en este grupo de instancias. 
 
Figura 8. Tiempo Computacional G Remove 
 
Fuente: Elaboración propia 
Figura 9. Tiempo Computacional G Add 
 
Fuente: Elaboración propia 
 
Figura 10. Tiempo Computacional Astar Remove 
 
Fuente: Elaboración propia 
 
6.3. Resultados en Instancias RACP Multiproyecto 
 
Procedimiento de Solución 
El método propuesto con sus cuatro versiones debe contemplar el cumplimiento de la fecha de 
entrega de cada proyecto y que cada uno puede iniciar máximo en una fecha de inicio 𝑡𝑜𝑠 
predefinida. 
Para la solución de las instancias multiproyecto conservando la misma estructura del método 
propuesto, se realizó el ajuste de la información de las instancias para que pueda ser cumplida la 
fecha de entrega de cada proyecto y que cada uno de éstos inicie en sus fechas de inicio permitidas. 
Siguiendo el enfoque tradicional de los problemas multiproyecto en el que el conjunto de proyectos 
puede ser visto como un mega proyecto, con la modificación realizada, las soluciones obtenidas 
cumplen las restricciones del problema mientras se intenta minimizar el costo total de recursos 
asignado a todo el conjunto de proyectos. 
La figura 11 muestra la estructura básica del problema multiproyecto propuesto. El horizonte de 
planeación T corresponde a la máxima fecha de entrega. En este ejemplo se tienen cuatro proyectos 
con fecha de entrega definida y una fecha de inicio máxima permitida según la descripción del 
problema. Tan solo el proyecto 1 inicia en el momento 0, mientras que los demás proyectos tienen 
tiempos de inicio 𝑡𝑜𝑠 > 0 . 
Figura 11. Estructura Básica del Problema RACP Multiproyecto propuesto 
 
Fuente: Elaboración propia 
Para logar el cumplimiento de las fechas de entrega de cada proyecto y del inicio de las actividades 
iniciales de cada uno en las fechas permitidas, se incluyeron actividades ficticias a cada proyecto 
cuya fecha de inicio permitida sea mayor que cero (𝑡𝑜𝑠 > 0). Estas actividades ficticias tendrán una 
duración equivalente a sus respectivos inicios permitidos 𝑡𝑜𝑠. Mientras que para lograr el 
cumplimiento de las fechas de entrega de cada proyecto se incluyeron actividades ficticias 
seguidamente a las actividades finales de cada proyecto. La figura 12 ilustra esta situación para un 
ejemplo de 4 proyectos, donde el proyecto 2 debe ser entregado en t=100 y el horizonte de 
planeación es T=200. 
Figura 12. Ejemplo de Conjunto de 4 Proyectos – Actividades Ficticias Incluidas 
 
Fuente: Elaboración propia 
Se puede observar que las actividades ficticias incluidas B’, C’ y D’ para los proyectos 1, 2 y 3 
deben tener una duración pero no un requerimiento de recurso. Para establecer la duración de las 
actividades ficticias se toma como ejemplo el proyecto 2. Tanto B como C son actividades que por 
tarde deben terminar en t=100 para cumplir la entrega del proyecto 2. La diferencia entre dicha 
entrega y el horizonte de planeación es de t=200-100 =100 unidades de tiempo, entonces dicha 
diferencia será la duración que tendrán las actividades B’ y C’ del proyecto 2. Este valor de duración 
es consistente al conservar la criticidad de la actividad B, y la holgura presente en la actividad C, 
puesto que por temprano termina en 90, es decir que por temprano C’ iniciaría en 90 y terminaría 
en 190, sin alterar el horizonte de planeación. 
Adicionalmente, si se evalúan los tiempos tardíos, se observa que por tarde la actividad C puede 
terminar en 100, cumpliendo la entrega del proyecto 2, por lo cual la actividad C’ iniciaría por tarde 
en 100 y terminaría por tarde en t=200, cumpliendo con el horizonte de planeación, así se permite 
que la actividad C y su ficticia C’ conserven su holgura. 
Se obtuvieron soluciones de las instancias propuestas y debido al esfuerzo computacional, para las 
instancias adaptadas de Perez, et. al. solo se resolvieron las que corresponden a un total de 60 
actividades en total (p*a). En la tabla 5 se muestra el valor del GAP promedio y el