Optimiza la secuenciación de trabajos con heurísticas y Ortools en Python.

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

Minimiza la tardanza total combinando heurísticas clásicas con un modelo de programación lineal paso a paso.

Python ortools Heurísticas Optimización SPT · EDD · LPT
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.

1

Generación de Datos

Generamos 10 trabajos con duraciones y fechas de entrega aleatorias.

Python 
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)
2

Aplicación de Heurísticas

Calculamos la tardanza total con 7 heurísticas:

Python 
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])

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

heurísticas = {
    'FCFS': indices,
    '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)

mejor_tardanza = min(resultados.values())
peor_tardanza = max(resultados.values())

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

Optimización con ortools

Resolvemos el problema de forma exacta usando el solver CP-SAT de Google OR-Tools.

Python · ortools 
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: intervalo para cada trabajo en la máquina única
job_intervals = []
starts = []
ends = []
tardiness = []

for i in range(n):
    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)

    # Tardanza: 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
model.AddNoOverlap(job_intervals)

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

# Crear el solucionador
solver = cp_model.CpSolver()
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()

    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")
    print(f"📊 Tardanza total: {tardanza_optima:.1f} días")
    print(f"🔄 Orden: {' → '.join(trabajos[i] for i in secuencia)}")
else:
    print(f"❌ No se encontró solución. Estado: {solver.StatusName(status)}")

Resultados

HeurísticaTardanza (días)Ranking
EDD6🥇 Óptimo
Óptimo (ortools)6🥇 Óptimo
Slack12🥈 Cercano
FCFS43Medio
SPT8,830Malo
Critical Ratio (CR)13,135Malo
LPT24,717Muy malo
LDD25,370Peor
GANADOR

EDD + ortools

6
días de tardanza
PEOR CASO

LDD (Least Due Date)

25,370
días de tardanza

Insight clave: El modelo de ortools obtiene el mismo resultado óptimo que la heurística EDD. Esto no siempre ocurre — en instancias más grandes, las heurísticas pueden quedarse en óptimos locales mientras el solver encuentra el global.

Consejos Pro

  • Escala a más trabajos con Gurobi o CPLEX cuando ortools se vuelva lento (más de 100 trabajos).
  • Visualiza con Gantt en Plotly para presentar resultados a equipos no técnicos.
  • Valida siempre contra una heurística rápida (EDD o Slack) como benchmark antes de lanzar el solver.
  • Considera setup times si los trabajos requieren cambio de configuración entre uno y otro.

¿Quieres aplicarlo HOY en tu empresa?

Descarga el Jupyter Notebook completo con gráficos Gantt interactivos.

📓 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 del notebook
  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 promedio aplicando este método a su línea de producción.

Referencias

[1] OR-Tools Documentation — Google Optimization

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

Entradas populares de este blog

Análisis ABC en Power BI con DAX.

Imagen
Análisis ABC en Power BI con DAX: Guía Completa para Profesionales Guía completa para clasificar ítems con el Principio de Pareto. Medidas acumuladas, categorización automática y gráficos de Pareto. Power BI DAX Pareto ABC Análisis de Datos 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 al valor total: A ~20% de los ítems ≈ 80% del valor B ~30% de los ítems ≈ 15% del valor C ~50...
Leer más

Cómo Realizar One-Hot Encoding en Power BI.

Imagen
Cómo Realizar One-Hot Encoding en Power BI: Guía Paso a Paso Guía paso a paso con Power Query. Sin R, sin Python, sin extensiones. Power BI Power Query M Language One-Hot Encoding 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 V...
Leer más

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

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

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

Target Encoding en Power BI: La Guía Definitiva Sin Data Leakage

Target Encoding en Power BI: La Guía Definitiva Sin Data Leakage Domina esta técnica esencial para modelos predictivos con validación cruzada, smoothing y prevención de overfitting. Código M paso a paso + mejores prácticas. Power BI Power Query M Language DAX ML ¿Qué es Target Encoding (Mean Encoding)? Target Encoding es una técnica de codificación categórica que reemplaza cada categoría por el promedio de la variable objetivo para esa categoría. Es especialmente poderosa en modelos predictivos porque captura la relación real entre la categoría y el resultado. Ejemplo Simple: Ciudad Ventas Madrid 1000 Barcelona 800 Madrid 1200 Valencia 600 Target Encoding: Ciudad Target_Encoded Madrid 1100 ...
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

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

Optimización del Embalaje en Contenedores: Algoritmos y Ejemplos en Python Bin Packing explicado paso a paso: algoritmos, complejidad, código Python y cuándo usar cada estrategia. Python Algoritmos Optimización NP-duro Logística El problema de embalaje en contenedores (bin packing) es uno de los desafíos clásicos de la optimización combinatoria. Aparece en logística, planificación de servidores en la nube, corte de materiales y hasta en la asignación de anuncios publicitarios. En este artículo veremos cuatro algoritmos para resolverlo, sus garantías teóricas, código Python listo para usar y una comparativa real para que elijas el correcto según tu escenario. ¿Qué es el Bin Packing y por qué es difícil? Dado un conjunto de ítems con tamaños y contenedores de capacidad fija, el objetivo es usar el mínimo número de contenedores posible. Entrada: lista de tamaños (ej. [4...
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

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