Optimiza la secuenciación de trabajos con heurísticas y Ortools en Python. Minimiza la tardanza total con un modelo de programación lineal paso a paso

Optimización de Secuenciación de Trabajos con PuLP y Heurísticas en Python
Secuenciación de trabajos

Fuente: Algocademy

La secuenciación de trabajos es un problema clásico de optimización en el que se busca determinar el orden óptimo para procesar tareas en una máquina, minimizando la tardanza total. En este artículo, combinamos heurísticas clásicas (SPT, EDD, etc.) con un modelo de programación lineal usando ortools para garantizar la solución óptima.

Trabajaremos con 10 trabajos generados aleatoriamente, aplicaremos 7 heurísticas y un modelo de optimización.

Paso 1: Generación de Datos

Generamos 10 trabajos con duraciones y fechas de entrega aleatorias.

import random

num_trabajos = 10
trabajos = [f'J{i+1}' for i in range(num_trabajos)]
duraciones = [random.randint(1, 10) for _ in range(num_trabajos)]
fechas_entrega = [random.randint(5, 30) for _ in range(num_trabajos)]

datos_trabajos = list(zip(trabajos, duraciones, fechas_entrega))
print("Datos generados:")
for t in datos_trabajos:
    print(t)

Paso 2: Aplicación de Heurísticas

Calculamos la tardanza total con 7 heurísticas:

# @title
def calcular_tardanza(secuencia, duraciones, fechas_entrega):
    n = len(secuencia)
    tiempo_actual = 0
    tardanza_total = 0
    for i in secuencia:
        tiempo_actual += duraciones[i]
        tardanza = max(0, tiempo_actual - fechas_entrega[i])
        tardanza_total += tardanza
    return tardanza_total

def heuristica_spt(duraciones):
    return sorted(range(len(duraciones)), key=lambda i: duraciones[i])

def heuristica_edd(fechas_entrega):
    return sorted(range(len(fechas_entrega)), key=lambda i: fechas_entrega[i])

def heuristica_slack(duraciones, fechas_entrega):
    slack = [fechas_entrega[i] - duraciones[i] for i in range(len(duraciones))]
    return sorted(range(len(slack)), key=lambda i: slack[i])

# Implementación de las heurísticas adicionales
def heuristica_lpt(duraciones):
    return sorted(range(len(duraciones)), key=lambda i: duraciones[i], reverse=True)

def heuristica_ldd(fechas_entrega):
    return sorted(range(len(fechas_entrega)), key=lambda i: fechas_entrega[i], reverse=True)

def heuristica_cr(duraciones, fechas_entrega):
    # Critical Ratio (Fecha de Entrega / Duración) - menor CR primero
    cr = [fechas_entrega[i] / duraciones[i] if duraciones[i] > 0 else float('inf') for i in range(len(duraciones))]
    return sorted(range(len(cr)), key=lambda i: cr[i])

def generar_secuencia_gantt(secuencia, trabajos, duraciones, fechas_entrega):
    df = []
    start = 0
    for idx in secuencia:
        job = trabajos[idx]
        dur = duraciones[idx]
        end = start + dur
        tardanza = max(0, end - fechas_entrega[idx])
        df.append(dict(Task=job, Start=start, Finish=end, Due=fechas_entrega[idx], Tardanza=tardanza))
        start = end
    return pd.DataFrame(df)

# Ejecutar todas las heurísticas
n = len(trabajos)
indices = list(range(n))

heurísticas = {
    'FCFS': indices, # First Come First Served es simplemente el orden inicial
    'SPT': heuristica_spt(duraciones),
    'LPT': heuristica_lpt(duraciones),
    'EDD': heuristica_edd(fechas_entrega),
    'LDD': heuristica_ldd(fechas_entrega),
    'Slack': heuristica_slack(duraciones, fechas_entrega),
    'CR': heuristica_cr(duraciones, fechas_entrega)
}

resultados = {}
secuencias_resultados = {}
for nombre, sec_indices in heurísticas.items():
    tardanza = calcular_tardanza(sec_indices, duraciones, fechas_entrega)
    resultados[nombre] = tardanza
    secuencias_resultados[nombre] = ' → '.join(trabajos[i] for i in sec_indices)

# Determinar la mejor y peor tardanza
mejor_tardanza = min(resultados.values())
peor_tardanza = max(resultados.values())

print(f"\nMejor Tardanza Total (Heurísticas): {mejor_tardanza}")
print(f"Peor Tardanza Total (Heurísticas): {peor_tardanza}")


resultados_df = pd.DataFrame(list(resultados.items()), columns=['Heurística', 'Tardanza Total (días)'])
#resultados_df['Secuencia'] = resultados_df['Heurística'].map(secuencias_resultados)
resultados_df = resultados_df.sort_values(by='Tardanza Total (días)')
display(resultados_df.style.hide(axis='index').bar(subset=['Tardanza Total (días)'], color='#1e40af'))

Paso 3: Optimización con ortools (Opcional)


        # @title
import time
from ortools.sat.python import cp_model

start_time = time.time()

# Crear el modelo CP-SAT
model = cp_model.CpModel()
n = len(trabajos)

# Variables
# Interval variables for each job on the single machine
job_intervals = []
# Start, end, and duration variables for each job
starts = []
ends = []
tardiness = []

for i in range(n):
    # The start and end times can be at most the total duration of all jobs
    max_end_time = sum(duraciones)
    start_var = model.NewIntVar(0, max_end_time, f'start_{i}')
    end_var = model.NewIntVar(0, max_end_time, f'end_{i}')
    interval_var = model.NewIntervalVar(start_var, duraciones[i], end_var, f'interval_{i}')

    starts.append(start_var)
    ends.append(end_var)
    job_intervals.append(interval_var)

    # Tardiness variable for each job: max(0, end_var - due_date)
    tardy_var = model.NewIntVar(0, max_end_time, f'tardy_{i}')
    model.AddMaxEquality(tardy_var, [end_var - fechas_entrega[i], 0])
    tardiness.append(tardy_var)


# Restricción de no solapamiento en la máquina única
# Use a no_overlap constraint on the interval variables
model.AddNoOverlap(job_intervals)

# Objetivo: Minimizar la tardanza total
model.Minimize(sum(tardiness))


# Crear el solucionador
solver = cp_model.CpSolver()

# Resolver
# Incrementar el tiempo límite para problemas más grandes si es necesario (en segundos)
solver.parameters.max_time_in_seconds = 300.0
status = solver.Solve(model)

tiempo_opt = time.time() - start_time

# Extraer resultados
secuencia = []
tardanza_optima = None

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    tardanza_optima = solver.ObjectiveValue()

    # Extraer la secuencia ordenando por tiempo de inicio
    start_times_with_indices = [(solver.Value(starts[i]), i) for i in range(n)]
    start_times_with_indices.sort()
    secuencia = [index for start_time, index in start_times_with_indices]

    print(f"✅ Solución encontrada en {tiempo_opt:.2f} segundos (Estado: {solver.StatusName(status)})")
    print(f"📊 Tardanza total: {tardanza_optima:.1f} días")
    print(f"🔄 Orden encontrado: {' → '.join(trabajos[i] for i in secuencia)}")

else:
    print(f"❌ No se encontró una solución óptima o factible. Estado: {solver.StatusName(status)}")
    secuencia = [] # Secuencia vacía si no hay solución
    tardanza_optima = None

Resultados

HeurísticaTardanza (días)
EDD6
Óptimo (ortools)6
Slack12
FCFS43
SPT8830
Critical Ratio (CR)13135
Longest Processing Time (LPT)24717
Least Due Date (LDD)25370

¡El modelo de ortools obtiene el mismo resultado que la heurística EDD!

Consejos Pro

¿Quieres aplicarlo HOY en tu empresa?

Descarga el Jupyter Notebook con Gantt

Abrir en Colab Contactarme

¿Cómo aplicarlo HOY?

  1. Excel: Copia tus datos (columna A: ID, B: Duración, C: Entrega)
  2. Código: Pega en líneas 6-8
  3. Ejecuta: Obtén el orden óptimo en 3 segundos
  4. Implementa: Envía al jefe → "Esto ahorra días por semana"

Ejemplo real: Una fábrica de muebles redujo 3 días de retraso con este método.

Referencias

[1] Ortools Documentation – ortools

[2] Principles of Sequencing and Scheduling – Kenneth R. Baker, Dan Trietsch

Entradas populares de este blog

Cómo Equilibrar Múltiples Productos con Pedidos a la Medida

Imagen
Domina tus Pedidos: Modelo de Inventario Multiproducto con Restricción de Órdenes Créditos: mygestion.com ¿Alguna vez has sentido que gestionar un almacén es como bailar una coreografía imposible? Productos que entran y salen, clientes que esperan, y un límite de pasos (¡o pedidos!) que no puedes exceder. ¡No te preocupes! Hoy te guiaremos por un modelo de inventario multiproducto que hará que tus pedidos fluyan como una danza perfecta, respetando una restricción de 15 pedidos al año. Con este modelo, aprenderás a ajustar cuánto pedir y cuándo hacerlo , manteniendo los costos bajo control. ¡Prepárate para una aventura numérica llena de estrategia y diversión! ¿Por qué Optimizar los Pedidos? En el mundo empresarial, optimizar los pedidos es clave para: Red...
Leer más

Maximiza la rentabilidad de tu negocio: Cómo optimizar la selección de proveedores de mercancías.

Imagen
Optimización de Proveedores con Programación Lineal en Python La programación lineal es una herramienta poderosa para optimizar decisiones en la gestión de la cadena de suministro. En este artículo, exploramos cómo seleccionar proveedores para maximizar la utilidad total, respetando restricciones como presupuesto, capacidad y demanda. Usaremos la biblioteca PuLP en Python para modelar y resolver este problema. ¡Acompáñanos en este recorrido técnico! 🚀 Gestión de proveedores para optimizar la cadena de suministro (Fuente: CEUPE). El Problema de Selección de Proveedores Imagina una empresa que necesita adquirir productos de varios proveedores para satisfacer una demanda específica. Cada proveedor ofrece productos a un costo y precio de venta distintos, con una capacidad máxima de suministro. El objetivo es maximizar la utilidad total (diferencia entre precio de venta y costo) mientra...
Leer más

Descubriendo el Poder de los Modelos de Clasificación en Machine Learning: Predicciones Precisas y Clasificaciones Sorprendentes

Imagen
Clasificación de Materias Primas con Machine Learning en Python El problema de clasificación en Machine Learning permite predecir categorías a partir de datos, como identificar el tipo de materia prima (CD, DB, SBT, R) según características como porcentajes de Grado A, B, C y el peso total del lote. En este artículo, exploramos algoritmos clave como Regresión Logística , Máquina de soporte vectorial (SVM) , Árboles de Decisión , Random Forest , Extreme gradient descent (XGBoost) y K-nearest neighborhood (KNN) , con implementaciones en Python, manejo de datos desbalanceados y evaluación de métricas. ¡Acompáñanos en este viaje técnico! 🚀 Ilustración de clasificación de datos con Machine Learning, representando la asignación de categorías (Fuente: Propia). El Problema de Clasificación de Materias Primas El objetivo es clasificar lotes de materias primas en categorías (CD, DB, SBT, R) según...
Leer más

Cómo Realizar One-Hot Encoding en Power BI: Guía Paso a Paso para Principiantes y Expertos

Imagen
Cómo Realizar One-Hot Encoding en Power BI: Guía Paso a Paso Fuente: aiplusinfo.com ¡Hola, comunidad de análisis de datos en Power BI ! Hoy te traigo un tutorial completo para implementar One-Hot Encoding directamente en Power Query . Si estás preparando datos para modelos de machine learning , regresiones lineales o simplemente quieres variables dummy para análisis avanzados, este método es rápido, nativo y escalable . ¡No necesitas R, Python ni extensiones! ¿Qué es el One-Hot Encoding? El One-Hot Encoding convierte variables categóricas (como "Rojo", "Azul", "Verde") en columnas binarias (0 o 1). Categoría Rojo Azul Verde Rojo 1 0 0 Azul 0 1 0 Verde 0 0 1 Ventajas en Power BI : Compatible con DAX y vis...
Leer más

Análisis ABC en Power BI con DAX: Guía Completa para Profesionales

Imagen
Análisis ABC en Power BI con DAX: Guía Completa para Profesionales Fuente: Webflow El análisis ABC es una técnica poderosa para clasificar ítems (productos, clientes, inventarios) según su importancia relativa, basada en el Principio de Pareto (80/20) . En este artículo, te guiamos paso a paso para implementarlo en Power BI con DAX , automatizando cálculos y creando visualizaciones impactantes. ¿Qué es el Análisis ABC? Clasifica ítems en tres categorías según su contribución acumulada: A : ~20% ítems → ~80% valor B : Ítems intermedios C : Bajo impacto Ideal para priorizar recursos, optimizar inventarios y enfocar esfuerzos comerciales. Requisitos Previos Tabla Ventas con: SKU : Identificador Cantidad , ValorUnitario Opcional: Peso ...
Leer más

Optimización del Inventario Multiproducto en Espacios Reducidos: Una guía para la eficiencia en gestión de stocks

Imagen
Optimización de Inventario Multiproducto: Magia en Espacios Reducidos ¿Alguna vez has sentido que tu almacén es como un rompecabezas imposible? Productos apilados, espacio limitado y clientes que esperan que todo esté listo en un chasquido de dedos. ¡No te preocupes! Hoy te guiaremos por un hechizo de optimización que hará que tu inventario sea tan eficiente como un caldero bien mezclado. Con nuestro modelo de inventario multiproducto con espacio restringido , aprenderás a decidir qué almacenar , cuánto pedir y cuándo hacerlo , todo mientras mantienes tus costos bajo control y el espacio limitado de 4000 ft². ¡Prepárate para convertir el caos en magia pura! ¿Por Qué Optimizar el Inventario? En un mundo donde el espacio es oro y los costos pueden salirse de control, optimizar el inventario es clave para: Re...
Leer más

Domina tu Almacén sin arruinarte: El Juego del Modelo de Inventario Múltiproductos con Presupuesto ajustado

Imagen
Domina tu Almacén sin Arruinarte: Modelo de Inventario Multiproductos con Presupuesto Ajustado ¿Tu almacén parece un rompecabezas imposible? Productos apilados, un presupuesto ajustado y clientes que esperan todo listo en un chasquido. ¡No temas! Hoy te guiaremos por un modelo de inventario multiproducto que transformará el caos en magia, manteniendo tus finanzas a salvo. Con nuestro modelo de inventario multiproducto con presupuesto restringido , aprenderás a decidir qué almacenar , cuánto pedir y cuándo hacerlo , todo dentro de un presupuesto de $25,000. ¡Prepárate para una aventura divertida y rentable! ¿Por Qué Optimizar el Inventario? En un mundo donde cada dólar cuenta, optimizar el inventario es clave para: Reducir costos : Minimiza gastos en pedidos y almacenamiento. Evitar faltantes : ...
Leer más

¡Plan Desagregado de Producción como un jefe!

Imagen
Plan Desagregado de Producción: Optimización con Programación Lineal Fuente: Webflow ¡El plan desagregado de producción desafía los límites de la eficiencia! Divide el proceso en pasos manejables para maximizar recursos, reducir costos y mejorar la respuesta al mercado. Con 2500 horas hombre disponibles, optimizamos la secuencia de producción de 4 productos (A, B, C, D) usando programación lineal para maximizar el tiempo de ciclo \( T \) . Datos del Problema A B C D Total Demanda (\( D_j \)) 400 600 800 700 2500 Inventario (\( I_j \)) 200 400 500 300 ...
Leer más

El Desafío del Empaque en Contenedores: Optimizando Espacios en contenedores con Ingenio

Imagen
Optimización del Embalaje en Contenedores: Algoritmos y Ejemplos en Python Algoritmos y Ejemplos en Python Elproblema de embalaje en contenedores (bin packing) es un desafío clásico en informática y matemáticas que busca minimizar el número de contenedores necesarios para almacenar un conjunto de objetos, cada uno con un tamaño específico, respetando una capacidad fija por contenedor. Este problema tiene aplicaciones en logística, gestión de inventarios y optimización de recursos. En este artículo, exploramos algoritmos clave como First Fit Decreasing , Best Fit , Next Fit y Algoritmos Genéticos , con implementaciones en Python. ¡Prepárate para optimizar al máximo! 🚀 ¿Qué es el Problema de Embalaje en Contenedores? El bin packing problem es un problema NP-difícil, lo que significa que no se conoce un algoritmo eficiente para resolverlo de forma óptima en casos grandes. El objetivo es asignar ítems...
Leer más

¡Optimización de Portafolios de Productos: El arte de maximizar el rendimiento!

Imagen
Optimización de Portafolios de Productos con K-means y Programación Lineal Fuente: Hamish Thorburn La optimización de portafolios de productos es clave para maximizar el rendimiento empresarial en industrias como retail, manufactura o tecnología. En este artículo, combinamos K-means clustering para agrupar productos similares y programación lineal con PuLP para construir portafolios óptimos, respetando restricciones como volumen, capacidad, precio y lead time. ¡Acompáñanos en este recorrido técnico! El Problema de Optimización de Portafolios Imagina que gestionas una empresa con múltiples productos, cada uno con características como volumen, precio, costo, lead time (tiempo de entrega) y calidad. El objetivo es construir portafolios de productos que maximicen el rendimiento total, cumpliendo restricciones como: Volumen mínimo por p...
Leer más