Resource-constrained Project Scheduling with Time-of-Use Energy Tariffs and Machine States: A Logic-based Benders Decomposition Approach

Resumen Técnico: Programación de Proyectos con Restricciones de Recursos con Tarifas de Energía según el Tiempo de Uso y Estados de Máquina

1. Definición del Problema

El artículo aborda una variante del Problema de Programación de Proyectos con Restricciones de Recursos (RCPSP) que integra tarifas de energía según el tiempo de uso (TOU) y transiciones de estado de la máquina. El problema consiste en programar un conjunto de tareas no preventivas sujetas a restricciones de precedencia y capacidades limitadas de recursos.

Características clave:

• Recurso Intensivo en Energía: Un recurso específico ($R_0$) tiene una capacidad unitaria y es intensivo en energía. Puede existir en tres estados: proc (procesamiento), idle (inactivo) u off (apagado).
• Transiciones de Estado: Las transiciones entre estados incurren en duraciones y costos de energía específicos. Por ejemplo, encender o apagar una máquina consume una cantidad significativa de energía y tiempo. La máquina debe comenzar y terminar en el estado off.
• Clasificación de Tareas: Las tareas se dividen en tareas intensivas en energía (que requieren que $R_0$ esté en el estado proc) y tareas no intensivas en energía (que no utilizan $R_0$).
• Objetivo: El objetivo es minimizar una combinación convexa del Costo Total de Energía (TEC) y la Duración de la Ejecución (Makespan, $C_{max}$). El TEC se calcula basándose en las tarifas TOU, que pueden variar en el tiempo e incluso tomar valores negativos. El objetivo se normaliza utilizando límites inferiores derivados de optimizaciones independientes de los componentes TEC y $C_{max}$.

2. Metodología

Los autores proponen y comparan tres enfoques de modelado distintos:

A. Modelos Monolíticos
Se formulan dos modelos compactos para resolver el problema de forma integral:

1. ILP Monolítico: Un modelo de Programación Lineal Entera que utiliza variables indexadas en el tiempo. Incorpora costos de transición óptimos precalculados (mediante el algoritmo SPACES) entre intervalos de procesamiento para gestionar los estados de la máquina.
2. CP Monolítico: Un modelo de Programación por Restricciones que utiliza variables de intervalo opcionales. Este enfoque representa el procesamiento de tareas y las transiciones de estado óptimas como variables de intervalo, lo que permite al solver determinar dinámicamente el número y la ubicación de las transiciones.

B. Descomposición de Benders Basada en Lógica (LBBD)
La contribución principal es un enfoque híbrido de LBBD que descompone el problema en dos subproblemas acoplados:

• Problema Maestro (ILP): Resuelve la optimización del estado de la máquina y el costo de energía. Determina los tiempos de inicio de las tareas intensivas en energía y la secuencia de las transiciones de estado. Utiliza un grafo SPACES modificado para calcular los costos de transición.
• Subproblema (CP): Una verificación de factibilidad para el componente RCPSP. Dados los tiempos de inicio fijos de las tareas intensivas en energía del Problema Maestro, este intenta programar todas las tareas restantes no intensivas en energía respetando las capacidades de los recursos y las restricciones de precedencia.
• Planos de Corte (Cutting Planes):
  • Cortes de Factibilidad: Generados cuando el subproblema es infactible, evitando que el Problema Maestro seleccione el mismo conjunto conflictivo de tiempos de inicio de tareas intensivas en energía.
  • Cortes de Optimalidad: Generados cuando el subproblema es factible pero produce un makespan diferente al estimado por el Maestro. Estos cortes utilizan la ruta crítica del grafo de flujo de recursos para imponer un límite inferior al makespan en el Problema Maestro.

3. Principales Contribuciones

1. Formulación del Problema: La introducción de una nueva variante de RCPSP que acopla la dinámica de estado de la máquina (proc, idle, off) con las tarifas TOU, extendiendo estudios previos de una sola máquina a un contexto de programación de proyectos con múltiples recursos.
2. Marco de Trabajo LBBD Novedoso: El desarrollo de una estrategia de descomposición que separa la gestión de la energía (Maestro) de la programación combinatoria (Subproblema). Los autores derivan cortes de Benders específicos adaptados a la interacción entre los estados de la máquina y las restricciones de RCPSP.
3. Generalización: Demostración de que la arquitectura LBBD es aplicable a otros problemas de programación, específicamente:
   • RCPSP con tiempos de bloqueo y un objetivo de penalización total ponderada.
   • Programación de Taller de Trabajo Flexible (FJSP).

4. Resultados Experimentales

Los experimentos se realizaron en instancias derivadas del conjunto de datos PSPLIB, categorizadas por la densidad de tareas intensivas en energía (Sparse/Ralas, Standard/Estándar, Dense/Densas) y variando los parámetros de ponderación ($\alpha$) entre el costo de energía y el makespan.

• Rendimiento frente a Modelos Monolíticos:
  • Ambos enfoques monolíticos (ILP y CP) son superados por el LBBD en la mayoría de los escenarios, particularmente para instancias grandes (hasta 480 tareas) y cuando el criterio de makespan es menos dominante ($\alpha \to 1$).
  • El enfoque LBBD resuelve instancias a la optimalidad significativamente más rápido que el CP monolítico, el cual tiene dificultades con espacios de búsqueda grandes.
  • El ILP monolítico se desempeña razonablemente bien, pero es generalmente más lento que el LBBD.
• Impacto de los Parámetros:
  • $\alpha = 1$ (Solo Energía): El LBBD funciona excepcionalmente bien, ya que el subproblema se reduce a una verificación de factibilidad pura, que los solvers de CP manejan eficientemente.
  • $\alpha < 1$ (Objetivos Mixtos): El LBBD sigue siendo superior en las instancias Standard y Dense. Sin embargo, en las instancias Sparse con un $\alpha$ bajo (alto peso en el makespan), el CP monolítico a veces supera al LBBD porque los límites de tiempo del subproblema en el LBBD pueden dificultar la exploración del espacio de búsqueda.
• Resultados de Generalización:
  • En el RCPSP con tiempos de bloqueo, el LBBD encontró soluciones óptimas para casi el 90% de las instancias en 30 minutos, en comparación con menos del 5% para el CP monolítico.
  • En el problema de Taller de Trabajo Flexible (FJSP), el LBBD encontró soluciones factibles con mayor frecuencia (107/120 veces) que el ILP monolítico (83/120 veces) bajo restricciones de tiempo.

5. Significación y Reivindicaciones

El artículo afirma que el enfoque LBBD propuesto representa un avance significativo para los problemas de programación conscientes de la energía que involucran estados de máquina complejos. Su principal significación radica en su capacidad para desacoplar la optimización continua del costo de energía de las restricciones discretas de programación combinatoria, permitiendo que cada una sea resuelta por el solver más adecuado (ILP para energía, CP para programación).

Los autores sostienen que esta descomposición no solo es efectiva para el problema específico de RCPSP-TOU, sino que es un marco generalizable para cualquier problema de programación donde las actividades intensivas en energía puedan separarse de la lógica de asignación de recursos restante. El trabajo destaca que, si bien los modelos monolíticos son intuitivos, a menudo no logran escalar con el tamaño y la complejidad del problema, mientras que el enfoque LBBD mantiene su robustez a través de diversas densidades de instancias y ponderaciones de objetivos.

El artículo concluye señalando que trabajos futuros podrían explorar múltiples recursos intensivos en energía, transiciones de estado más complejas y la integración de almacenamiento de energía o generación en sitio, así como el impacto de la incertidumbre en las tarifas de energía.