🔢 mathematics

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

This paper addresses the Resource-Constrained Project Scheduling Problem with Time-of-Use energy tariffs and machine states by proposing a Logic-Based Benders Decomposition approach that significantly outperforms monolithic methods in minimizing makespan and energy costs, while demonstrating its generalizability to other complex scheduling problems.

Original authors: Corentin Juvigny, Antonín Novák, Jan Mandík, Zdeněk Hanzálek

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Corentin Juvigny, Antonín Novák, Jan Mandík, Zdeněk Hanzálek

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a busy factory. You have a list of tasks to complete, some machines that can only do one thing at a time, and a strict set of rules about which tasks must happen before others. This is the classic "Resource-Constrained Project Scheduling Problem" (RCPSP). It's like trying to organize a massive wedding where the caterer, the band, and the venue all have limited availability, and the cake cutting can't happen before the ceremony.

But now, add a twist: Electricity prices change throughout the day.

In some hours, power is cheap (like 3 AM); in others, it's expensive (like 5 PM). Furthermore, your most energy-hungry machine (let's call it the "Big Oven") has three moods:

Cooking (Proc): It's running and eating energy.
Idle: It's warm but not cooking. It uses a little energy to stay ready.
Off: It's cold. Turning it back on takes time and a huge burst of energy.

Your goal is to schedule every task so that you finish the job as fast as possible and spend the least amount of money on electricity. This is a balancing act: Do you run the oven during cheap hours, even if it means the whole factory waits? Or do you rush to finish early, even if it costs a fortune in peak-hour power?

The Problem: A Puzzle Too Big for One Brain

The authors of this paper tried to solve this puzzle using two traditional methods:

The "Monolithic" ILP: Trying to write one giant mathematical equation that accounts for every single task, every second of time, and every machine state at once. It's like trying to solve a 1,000-piece jigsaw puzzle while blindfolded, holding all the pieces in one hand.
The "Monolithic" CP: A different type of logic solver that is very good at scheduling but struggles when you add the complex "electricity price" rules on top.

Both methods worked okay for small puzzles, but when the factory got bigger (more tasks), they got stuck. They couldn't find the best solution in a reasonable amount of time.

The Solution: The "Master Chef" and the "Line Cook"

The authors proposed a new, smarter way called Logic-Based Benders Decomposition (LBBD). Think of this as splitting the job between two people with different skills:

The Master Chef (The Master Problem): This person is an expert in money. They look at the electricity price chart and decide: "Okay, the Big Oven should be cooking during these cheap hours and resting during these expensive ones." They don't worry about which specific cake goes in the oven; they just set the schedule for the oven's "mood" (On, Idle, Off) to save money. They use a fast mathematical solver (ILP) to do this.
The Line Cook (The Subproblem): This person is an expert in logistics. They take the Master Chef's oven schedule and ask: "Can we actually fit all the other tasks (the cakes, the decorations, the guests) around this oven schedule without breaking any rules?" They use a powerful logic engine (Constraint Programming) to check if the plan works.

How they talk to each other:

The Master Chef makes a plan.
The Line Cook tries to execute it.
If it works: Great! They check if they can do it even better.
If it fails: The Line Cook says, "Hey, you can't put the oven in 'Off' mode at 2 PM because the cake batter needs to be ready then!"
The Master Chef takes this feedback, learns from it, and makes a new plan that avoids that specific mistake.

They repeat this conversation until they find the perfect schedule.

What They Found

The authors tested this "Team Approach" against the "Solo Approach" on hundreds of different factory scenarios:

When the goal is purely saving money (ignoring how long the job takes): The Team Approach (LBBD) was a massive winner. It solved problems with up to 480 tasks perfectly, while the solo methods gave up or took forever. It was like having a GPS that knew exactly when to drive to avoid traffic, while the solo driver just guessed.
When the goal is a mix of speed and money: The Team Approach was still usually the best, especially for big, crowded factories.
The Exception: If the factory was very empty (few tasks) and speed was the only thing that mattered, the old "Solo Logic" method (Constraint Programming) was sometimes faster.

The "Magic Trick" (Generalization)

The most exciting part of the paper is that this "Master Chef / Line Cook" teamwork isn't just for this specific factory. The authors showed that you can use this same teamwork strategy for other types of scheduling problems, like:

Flexible Job Shops: Where a task can be done on any of several machines.
Projects with "Blocking": Where a machine is stuck waiting for a part to arrive.

In all these cases, splitting the "Energy/Money" decision from the "Task/Time" decision made the computer solve the problem much faster and find better solutions.

Summary

In simple terms, this paper says: Don't try to solve the whole energy-scheduling puzzle in one giant brain. Instead, split it up. Have one expert handle the electricity bills and another expert handle the task logistics. Let them talk to each other until they agree on the best plan. This method is faster, smarter, and can handle much bigger, more complex real-world factories than the old ways.

Technical Summary: Resource-Constrained Project Scheduling with Time-of-Use Energy Tariffs and Machine States

1. Problem Definition

The paper addresses a variant of the Resource-Constrained Project Scheduling Problem (RCPSP) that integrates Time-of-Use (TOU) energy tariffs and machine state transitions. The problem involves scheduling a set of non-preemptive tasks subject to precedence constraints and limited resource capacities.

Key characteristics include:

Energy-Intensive Resource: One specific resource ( $R_0$ ) has a unitary capacity and is energy-intensive. It can exist in three states: proc (processing), idle, or off.
State Transitions: Transitions between states incur specific durations and energy costs. For instance, turning a machine on or off consumes significant energy and time. The machine must start and end in the off state.
Task Classification: Tasks are divided into energy-intensive tasks (requiring $R_0$ in the proc state) and non-energy-intensive tasks (which do not use $R_0$ ).
Objective: The goal is to minimize a convex combination of the Total Energy Cost (TEC) and the Makespan ( $C_{max}$ ). The TEC is calculated based on TOU tariffs, which can vary over time and even take negative values. The objective function is normalized using lower bounds derived from independent optimizations of the TEC and $C_{max}$ components.

2. Methodology

The authors propose and compare three distinct modeling approaches:

A. Monolithic Models
Two compact models are formulated to solve the problem as a whole:

Monolithic ILP: An Integer Linear Programming model using time-indexed variables. It incorporates precomputed optimal transition costs (via the SPACES algorithm) between processing intervals to handle machine states.
Monolithic CP: A Constraint Programming model utilizing optional interval variables. This approach represents task processing and optimal state transitions as interval variables, allowing the solver to dynamically determine the number and placement of transitions.

B. Logic-Based Benders Decomposition (LBBD)
The primary contribution is a hybrid LBBD approach that decomposes the problem into two coupled subproblems:

Master Problem (ILP): Solves the machine state and energy cost optimization. It determines the start times of energy-intensive tasks and the sequence of state transitions. It utilizes a modified SPACES graph to calculate transition costs.
Subproblem (CP): A feasibility check for the RCPSP component. Given the fixed start times of energy-intensive tasks from the Master, it attempts to schedule all remaining non-energy-intensive tasks while respecting resource capacities and precedence constraints.
Cutting Planes:
- Feasibility Cuts: Generated when the subproblem is infeasible, preventing the Master from selecting the same conflicting set of energy-intensive task start times.
- Optimality Cuts: Generated when the subproblem is feasible but yields a makespan different from the Master's estimate. These cuts use the critical path of the resource-flow graph to enforce a lower bound on the makespan in the Master problem.

3. Key Contributions

Problem Formulation: The introduction of a new RCPSP variant that couples machine state dynamics (proc, idle, off) with TOU tariffs, extending previous single-machine studies to a multi-resource project scheduling context.
Novel LBBD Framework: The development of a decomposition strategy that separates energy management (Master) from combinatorial scheduling (Subproblem). The authors derive specific Benders cuts tailored to the interaction between machine states and RCPSP constraints.
Generalization: Demonstration that the LBBD architecture is applicable to other scheduling problems, specifically:
- RCPSP with blocking times and a total weighted tardiness objective.
- Flexible Job Shop Scheduling (FJSP).

4. Experimental Results

Experiments were conducted on instances derived from the PSPLIB dataset, categorized by the density of energy-intensive tasks (Sparse, Standard, Dense) and varying weighting parameters ( $\alpha$ ) between energy cost and makespan.

Performance vs. Monolithic Models:
- Both the monolithic ILP and CP approaches are outperformed by the LBBD in most scenarios, particularly for larger instances (up to 480 tasks) and when the makespan criterion is less dominant ( $\alpha \to 1$ ).
- The LBBD approach solves instances to optimality significantly faster than the monolithic CP, which struggles with large search spaces.
- The monolithic ILP performs reasonably well but is generally slower than LBBD.
Impact of Parameters:
- $\alpha = 1$ (Energy only): The LBBD performs exceptionally well, as the subproblem reduces to a pure feasibility check, which CP solvers handle efficiently.
- $\alpha < 1$ (Mixed objectives): LBBD remains superior in Standard and Dense instances. However, in Sparse instances with low $\alpha$ (high makespan weight), the monolithic CP sometimes outperforms LBBD because the subproblem time limits in LBBD can hinder the exploration of the search space.
Generalization Results:
- In the RCPSP with blocking times, LBBD found optimal solutions for nearly 90% of instances within 30 minutes, compared to less than 5% for the monolithic CP.
- In the Flexible Job Shop problem, LBBD found feasible solutions more frequently (107/120 times) than the monolithic ILP (83/120 times) under time constraints.

5. Significance and Claims

The paper claims that the proposed LBBD approach represents a significant advancement for energy-aware scheduling problems involving complex machine states. Its primary significance lies in its ability to decouple the continuous energy cost optimization from the discrete combinatorial scheduling constraints, allowing each to be solved by the most suitable solver (ILP for energy, CP for scheduling).

The authors assert that this decomposition is not only effective for the specific RCPSP-TOU problem but is a generalizable framework for any scheduling problem where energy-intensive activities can be separated from the rest of the resource allocation logic. The work highlights that while monolithic models are intuitive, they often fail to scale with problem size and complexity, whereas the LBBD approach maintains robustness across varying instance densities and objective weightings.

The paper concludes by noting that future work could explore multiple energy-intensive resources, more complex state transitions, and the integration of energy storage or on-site generation, as well as the impact of uncertainty in energy tariffs.