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

Resumo Técnico: Escalonamento de Projetos com Restrição de Recursos com Tarifas de Energia por Tempo de Uso e Estados de Máquina

1. Definição do Problema

O artigo aborda uma variante do Problema de Escalonamento de Projetos com Restrição de Recursos (RCPSP) que integra tarifas de energia por tempo de uso (TOU) e transições de estado de máquina. O problema envolve o escalonamento de um conjunto de tarefas não preemptivas sujeitas a restrições de precedência e capacidades limitadas de recursos.

As características principais incluem:

• Recurso Intensivo em Energia: Um recurso específico ($R_0$) possui capacidade unitária e é intensivo em energia. Ele pode existir em três estados: proc (processamento), idle (ocioso) ou off (desligado).
• Transições de Estado: As transições entre estados incorrem em durações e custos de energia específicos. Por exemplo, ligar ou desligar uma máquina consome energia e tempo significativos. A máquina deve iniciar e terminar no estado off.
• Classificação de Tarefas: As tarefas são divididas em tarefas intensivas em energia (que requerem $R_0$ no estado proc) e tarefas não intensivas em energia (que não utilizam $R_0$).
• Objetivo: O objetivo é minimizar uma combinação convexa do Custo Total de Energia (TEC) e do Makespan ($C_{max}$). O TEC é calculado com base em tarifas TOU, que podem variar ao longo do tempo e até assumir valores negativos. A função objetivo é normalizada usando limites inferiores derivados de otimizações independentes dos componentes TEC e $C_{max}$.

2. Metodologia

Os autores propõem e comparam três abordagens de modelagem distintas:

A. Modelos Monolíticos
Dois modelos compactos são formulados para resolver o problema como um todo:

1. ILP Monolítico: Um modelo de Programação Linear Inteira que utiliza variáveis indexadas no tempo. Ele incorpora custos de transição pré-computados (via algoritmo SPACES) entre intervalos de processamento para lidar com os estados da máquina.
2. CP Monolítico: Um modelo de Programação por Restrições que utiliza variáveis de intervalo opcionais. Esta abordagem representa o processamento de tarefas e as transições de estado ideais como variáveis de intervalo, permitindo que o solver determine dinamicamente o número e o posicionamento das transições.

B. Decomposição de Benders Baseada em Lógica (LBBD)
A principal contribuição é uma abordagem híbrida de LBBD que decompõe o problema em dois subproblemas acoplados:

• Problema Mestre (ILP): Resolve a otimização do estado da máquina e do custo de energia. Ele determina os tempos de início das tarefas intensivas em energia e a sequência de transições de estado. Utiliza um grafo SPACES modificado para calcular os custos de transição.
• Subproblema (CP): Uma verificação de viabilidade para o componente RCPSP. Dados os tempos de início fixos das tarefas intensivas em energia do Problema Mestre, ele tenta escalonar todas as tarefas restantes não intensivas em energia, respeitando as capacidades de recursos e as restrições de precedência.
• Planos de Corte (Cutting Planes):
  • Cortes de Viabilidade: Gerados quando o subproblema é inviável, impedindo que o Mestre selecione o mesmo conjunto conflitante de tempos de início de tarefas intensivas em energia.
  • Cortes de Otimalidade: Gerados quando o subproblema é viável, mas resulta em um makespan diferente da estimativa do Mestre. Esses cortes utilizam o caminho crítico do grafo de fluxo de recursos para impor um limite inferior no makespan no Problema Mestre.

3. Principais Contribuições

1. Formulação do Problema: A introdução de uma nova variante do RCPSP que acopla a dinâmica de estado da máquina (proc, idle, off) com tarifas TOU, estendendo estudos anteriores de máquina única para um contexto de escalonamento de projetos com múltiplos recursos.
2. Estrutura LBBD Inovadora: O desenvolvimento de uma estratégia de decomposição que separa a gestão de energia (Mestre) do escalonamento combinatório (Subproblema). Os autores derivam cortes de Benders específicos adaptados para a interação entre estados de máquina e restrições de RCPSP.
3. Generalização: Demonstração de que a arquitetidade LBBD é aplicável a outros problemas de escalonamento, especificamente:
   • RCPSP com tempos de bloqueio e um objetivo de atraso total ponderado.
   • Escalonamento de Job Shop Flexível (FJSP).

4. Resultados Experimentais

Experimentos foram conduzidos em instâncias derivadas do conjunto de dados PSPLIB, categorizadas pela densidade de tarefas intensivas em energia (Esparsas, Padrão, Densas) e variando os parâmetros de peso ($\alpha$) entre custo de energia e makespan.

• Desempenho vs. Modelos Monolíticos:
  • Ambos os modelos monolíticos (ILP e CP) são superados pelo LBBD na maioria dos cenários, particularmente para instâncias maiores (até 480 tarefas) e quando o critério de makespan é menos dominante ($\alpha \to 1$).
  • A abordagem LBBD resolve instâncias para a otimalidade significativamente mais rápido que o CP monolítico, que tem dificuldade com grandes espaços de busca.
  • O ILP monolítico apresenta um desempenho razoável, mas é geralmente mais lento que o LBBD.
• Impacto dos Parâmetros:
  • $\alpha = 1$ (Apenas Energia): O LBBD performa excepcionalmente bem, pois o subproblema se reduz a uma pura verificação de viabilidade, que os solvers de CP lidam de forma eficiente.
  • $\alpha < 1$ (Objetivos Mistos): O LBBD permanece superior nas instâncias Padrão e Densas. No entanto, em instâncias Esparsas com $\alpha$ baixo (alto peso de makespan), o CP monolítico às vezes supera o LBBD porque os limites de tempo do subproblema no LBBD podem dificultar a exploração do espaço de busca.
• Resultados de Generalização:
  • No RCPSP com tempos de bloqueio, o LBBD encontrou soluções ótimas para quase 90% das instâncias dentro de 30 minutos, comparado a menos de 5% para o CP monolítico.
  • No problema de Job Shop Flexível, o LBBD encontrou soluções viáveis com mais frequência (107/120 vezes) do que o ILP (83/120 vezes) sob restrições de tempo.

5. Significância e Alegações

O artigo afirma que a abordagem LBBD proposta representa um avanço significativo para problemas de escalonamento conscientes de energia envolvendo estados de máquina complexos. Sua principal significância reside na capacidade de desacoplar a otimização contínua do custo de energia da lógica de restrições de escalonamento combinatório discreto, permitindo que cada parte seja resolvida pelo solver mais adequado (ILP para energia, CP para escalonamento).

Os autores sustentam que esta decomposição não é apenas eficaz para o problema específico de RCPSP-TOU, mas é uma estrutura generalizável para qualquer problema de escalonamento onde atividades intensivas em energia possam ser separadas da lógica de alocação de recursos restante. O trabalho destaca que, embora os modelos monolíticos sejam intuitivos, eles frequentemente falham em escalar com o tamanho e a complexidade do problema, enquanto a abordagem LBBD mantém a robustez através de diferentes densidades de instâncias e ponderações de objetivo.

O artigo conclui observando que trabalhos futuros poderiam explorar múltiplos recursos intensivos em energia, transições de estado mais complexas e a integração de armazenamento de energia ou geração local, bem como o impacto da incerteza nas tarifas de energia.