Investigación de operaciones

Método de la Ruta Crítica mediante Python (CPM)

Critical Path Method

Para entender de qué se trata el método de Ruta Crítica, y cómo funciona como un algoritmo de redes, podemos dirigirnos a: Método de la Ruta Crítica (CPM). De acuerdo al objetivo de este artículo, basta con mencionar que la Ruta Crítica es una herramienta que soporta el análisis, la planificación, y la programación de proyectos. Que básicamente, nos ayuda a determinar cuáles de las actividades que componen un proyecto, son críticos con relación en su efecto sobre el tiempo total del proyecto.

El objetivo de este artículo es el de, mediante herramientas tecnológicas, abordar un caso básico de CPM, para desarrollar el método utilizando un lenguaje de programación, en este caso Python, que nos permita, automatizar los cálculos y así obtener las actividades críticas del proyecto, la duración del mismo y un diagrama de Gantt.

En el desarrollo de este ejercicio emplearemos:

  • Colaboratory: Este es un entorno de programación y ejecución virtual de Python desarrollado por Google. Nos permitirá no tener la necesidad de realizar ninguna instalación en nuestros equipos. Todo lo que desarrollemos lo ejecutaremos en un cuaderno virtual.
  • Python: Este será el lenguaje de programación que vamos a utilizar, y advertimos: No es necesario tener conocimientos previos, y el objetivo del artículo no es convertirnos en programadores expertos. Utilizaremos fragmentos de códigos, librerías disponibles, y explicaremos lo necesario para configurar nuestro desarrollo de acuerdo a los objetivos específicos de nuestros modelos.
  • CriticalPath: Las librerías son a Python, lo que las apps son a un teléfono celular. Esta es quizá una de las características más a tractivas de este lenguaje: Casi que existe una librería para cada necesidad. En este caso, CriticalPath, es una librería que calcula la ruta crítica a través de una red de tareas.
  • Matplotlib: Es una biblioteca completa para crear visualizaciones estáticas, animadas e interactivas en Python. Nos permitirá visualizar nuestros nodos y nuestras localizaciones solución.
  • Pandas: Es un paquete de Python que proporciona estructuras de datos rápidas, y flexibles, diseñadas para que el trabajo con datos estructurados (tabulares, multidimensionales, potencialmente heterogéneos) y de series de tiempo sea fácil e intuitivo.
  • Numpy: Es una librería que nos permitirá efectuar operaciones matriciales en Python.
  • Datetime: Es un módulo que proporciona herramientas para manipular fechas y horas.

 

Para evaluar los resultados obtenidos a través del tratamiento de un problema técnicamente formulado y abordado, utilizaremos un caso descrito en el libro Investigación de Operaciones (9na edición), de Hamdy A. Taha (University of Arkansas, Fayetteville), (Ejemplo 6.5-1):

Caso de aplicación

Un editor firmó un contrato con un autor para publicar un libro de texto. El autor somete a consideración una copia impresa de un archivo de computadora del manuscrito. Las actividades (simplificadas) asociadas con la producción del libro de texto se resumen en la siguiente tabla.

Actividades Predecesoras Duración (semanas)
A Corrección del manuscrito, por parte del editor 3
B Preparación de páginas muestra 2
C Diseño de la portada del libro 4
D Preparación de las ilustraciones 3
E Aprobación del manuscrito editado y de páginas muestra, por parte del autor A, B 2
F Formación del libro E 4
G Revisión de las páginas formadas, por parte del autor F 2
H Revisión de las ilustraciones por el autor D 1
I Producción de las placas de impresión G, H 2
J Producción y encuadernación del libro C, I 4

La tarea será determinar la Ruta Crítica (Actividades críticas) y la duración estimada del proyecto.


Paso 1: Crear el entorno de trabajo en Colaboratory

Lo primero que vamos a hacer consiste en crear un entorno de trabajo en Google Colaboratory, así que vayamos allá: Abrir cuaderno nuevo.

Verán que tienen un lienzo para programar el modelo, así que en este cuaderno podemos ir generando las líneas de código que explicaremos en los pasos siguientes.

Paso 2: Importar las librerías necesarias

Respecto a las librerías, en la introducción del artículo hicimos una descripción de la funcionalidad de cada una, veamos como importarlas en nuestro entorno:

#Importar las librerías necesarias
!pip install criticalpath
from criticalpath import Node
import datetime
import pandas as pd
import matplotlib.pyplot as plt
from matplotlib.patches import Patch
import numpy as np

De esta manera, tenemos todo lo necesario para empezar a desarrollar nuestro código.

Paso 3: Ingresar los datos del modelo

Básicamente los datos del modelo corresponden a las tareas, su duración y las relaciones de dependencia que rigen la secuencia del proyecto.

El siguiente fragmento permite ingresar estos datos al modelo:

#Ingresar los datos del modelo (Tareas y dependencias)

#Crear el proyecto "p"
p = Node('proyecto')

tareas = [("A", {"duracion": 3}), 
          ("B", {"duracion": 2}), 
          ("C", {"duracion": 4}), 
          ("D", {"duracion": 3}), 
          ("E", {"duracion": 2}), 
          ("F", {"duracion": 4}), 
          ("G", {"duracion": 2}), 
          ("H", {"duracion": 1}), 
          ("I", {"duracion": 2}), 
          ("J", {"duracion": 4})]

dependencias = [("A", "E"), 
                ("B", "E"), 
                ("E", "F"),
                ("F", "G"), 
                ("G", "I"), 
                ("I", "J"),
                ("C", "J"), 
                ("H", "I"), 
                ("D", "H")]

# Cargar al proyecto las tareas y sus duraciones
for i in tareas:
    p.add(Node(i[0], duration=i[1]["duracion"]))

# Cargar al pro yecto sus dependencias (secuencias)
for j in dependencias:
    p.link(j[0],j[1])

# Actualizar el proyecto:
p.update_all() 

El anterior fragmento nos permite cargar todos los datos necesarios para conocer la Ruta Crítica del modelo. Veamos cómo obtenerla:

#Obtener la Ruta Crítica del modelo
p.get_critical_path()

Al ejecutar esta instrucción tenemos la siguiente salida:

De la misma manera, podemos obtener la duración estimada del proyecto:

#Obtener la duración del proyecto
p.duration

Al ejecutar esta instrucción tenemos la siguiente salida:

Así entonces, de esta manera muy sencilla tenemos las actividades que componen la Ruta Crítica y la duración del proyecto de acuerdo a CPM (17 semanas). Podríamos finalizar el modelo hasta acá, sin embargo, queremos obtener el diagrama de Gantt del proyecto, y para eso es necesario obtener algunas variables adicionales.

Paso 4: Obtener las variables de inicio y finalización

Ya que el problema planteado no establece fechas de inicio y finalización, podemos, mediante Python

, utilizar una fecha de inicio artificial, por ejemplo: Hoy. ¿Con qué objetivo hacemos esto? Los diagramas de Gantt requieren de una línea de tiempo y es preciso establecer estas variables. Estableceremos fechas de inicio, de finalización y un status para cada actividad del proyecto.

En este caso puntual, ya que la duración de cada actividad se nos da en semanas, multiplicaremos el valor de la duración por 7:

#Obtener las variables de inicio y finalización
ruta_critica = [str(n) for n in p.get_critical_path()]

proj_fecha_inicio = datetime.date.today()

proj_calendario = pd.DataFrame([dict(Tarea = key, 
                                   Inicio = datetime.date.today(), 
                                   Fin = datetime.date.today() + datetime.timedelta(val['duracion']*7), 
                                   Status = 'Actividad Normal')
                              for key, val in dict(tareas).items()])

for key, val in dict(tareas).items():
    dep = [d for d in dependencias if d[1] == key]
    prev_tareas = [t[0] for t in dep]
    if prev_tareas:
        prev_fin = proj_calendario[proj_calendario.Tarea.isin(prev_tareas)]['Fin'].max()
        proj_calendario.loc[proj_calendario.Tarea == key, 'Inicio'] = prev_fin
        proj_calendario.loc[proj_calendario.Tarea == key, 'Fin'] = prev_fin + datetime.timedelta(val['duracion']*7)
        
proj_calendario.loc[proj_calendario.Tarea.isin(ruta_critica), 'Status'] = 'Ruta Crítica'
        
display(proj_calendario)

Al ejecutar este fragmento de código, tendremos:

Podemos apreciar cómo tenemos las fechas estimadas de inicio de cada actividad y su correspondiente fecha de finalización (teniendo en cuenta que la duración de las actividades está dada en semanas). También tenemos un status relacionado con la naturaleza de cada actividad: Crítica o Normal.

Y tenemos fechas de inicio y finalización, lo siguiente será calcular cuántos días pasan entre el inicio del proyecto y el inicio y finalización de cada actividad:

# Número de días desde que el proyecto inicia hasta que la tarea inicia
proj_calendario['dias_inicio'] = (proj_calendario.Inicio-proj_fecha_inicio).dt.days
# Número de días desde que el proyecto inicia hasta que la tarea finaliza
proj_calendario['dias_fin'] = (proj_calendario.Fin-proj_fecha_inicio).dt.days
# Días entre el inicio y el fin de cada tarea
proj_calendario['dias_inicio_fin'] = proj_calendario.dias_fin - proj_calendario.dias_inicio

display(proj_calendario)

Al ejecutar este fragmento de código, tendremos:

Paso 5: Obtener el diagrama de Gantt (Graficar)

El siguiente paso consiste en graficar de acuerdo al diagrama de Gantt, ls actividades del proyecto. El eje x estará dado en días.

#Graficar las actividades en un diagrama de Gantt
fig, ax = plt.subplots(1, figsize=(16,6))
ax.barh(proj_calendario.Tarea, proj_calendario.dias_inicio_fin, left=proj_calendario.dias_inicio)
plt.show()

Al ejecutar el fragmento tendremos:

Paso 6: Mejorar el diagrama de Gantt

Una vez obtenido el diagrama podemos realizar modificaciones sobre el mismo, por ejemplo: dar un color específico a las actividades de la ruta crítica, anexar leyendas, entre otros. Vamos a resaltar con rojo las actividades críticas, y a anexar alguna leyenda de actividades:

# Dar color rojo a las columnas de actividades críticas
def color(row):
    c_dict = {'Ruta Crítica':'#E64646', 'Actividad Normal':'#4F81BE'}
    return c_dict[row['Status']]
proj_calendario['color'] = proj_calendario.apply(color, axis=1)
fig, ax = plt.subplots(1, figsize=(16,6))
ax.barh(proj_calendario.Tarea, proj_calendario.dias_inicio_fin, left=proj_calendario.dias_inicio, color=proj_calendario.color)

#Anexar leyendas
c_dict = {'Ruta crítica':'#E64646', 'Actividad normal':'#4F81BE'}
leyenda = [Patch(facecolor=c_dict[i], label=i)  for i in c_dict]
plt.legend(handles=leyenda)

plt.show()

Al ejecutar el fragmento tendremos:

Ahora tenemos un modelo capaz de obtener las actividades críticas de un proyecto, determinar su duración de acuerdo al algoritmo CPM y graficar las actividades mediante un diagrama de Gantt.

También es posible incorporar una variable de «estado de terminación» de cada actividad, para así observar el avance del proyecto.

El código completo de este desarrollo lo puedes encontrar en nuestro cuaderno: Método de la Ruta Crítica (CPM) mediante Python.

Bryan Salazar López

Ingeniero Industrial y Magíster en Logística Integral especializado en productividad y modelamiento de procesos bajo dimensiones de sostenibilidad, industria 4.0, transformación digital y modelos de optimización. Docente universitario de pregrado y posgrado con experiencia en la enseñanza de estos temas. Fundador de Ingenieriaindustrialonline.com, un sitio en donde se recogen las aportaciones de investigaciones, artículos y referencias relevantes para la industria.

Entradas recientes

El sentido común y la Teoría de Restricciones (TOC)

En una pequeña comunidad agrícola en Michoacán, México, un niño llamado José Hernández soñaba con…

hace % días

La restricción nos blinda contra las malas noticias

Sábado por la mañana, Robert acaba de acompañar a su mujer a su clase de…

hace % días