Solving Complex Scheduling Problems with Google OR-Tools CP-SAT

Scheduling maintenance for cloud infrastructure is a high-stakes balancing act. When managing hypervisor hosts that serve hundreds of thousands of guest VMs, a simple reboot isn't just a server restart—it's a massive orchestration challenge. To minimize customer disruption, engineers must navigate the "3Cs": Capacity (available space for migrated VMs), Concurrency (network and I/O limits), and Conflict (SLA limits on how many of a single customer's VMs can move at once).

For these types of combinatorial optimization problems, the choice of solver can mean the difference between a model that solves in seconds and one that crashes due to exponential complexity. While Mixed Integer Programming (MIP) is a traditional go-to, Google's OR-Tools CP-SAT solver provides a more intuitive and performant framework specifically tailored for scheduling.

The Scheduling Challenge: RCPSP

Maintenance scheduling in the cloud is essentially a variation of the Resource-Constrained Project Scheduling Problem (RCPSP). In a standard RCPSP, you have tasks with specific durations and resource requirements, and the goal is to minimize the total project duration (the makespan) without exceeding resource limits.

In the context of cloud maintenance, each VM migration is a task. The resources are the available network bandwidth and host CPU. The objective is to complete all necessary maintenance across the fleet in the shortest time possible while adhering to the 3Cs.

Modeling with CP-SAT

CP-SAT is particularly powerful because it introduces specialized variables and constraints that map directly to the concept of time. Instead of treating time as a series of binary flags, CP-SAT uses interval variables.

Interval Variables

An interval variable encapsulates a start time, an end time, and a duration. This allows the solver to treat a task as a continuous block of time rather than a set of discrete points.

# Example: Creating an interval variable for a VM migration
start_var = model.new_int_var(0, planning_horizon, f"{vm}_start")
end_var = model.new_int_var(0, planning_horizon, f"{vm}_end")

vm_interval_var = model.new_interval_var(
    start=start_var, size=migration_duration, end=end_var, name=f"{vm}_interval"
)

Managing Concurrency

Once intervals are defined, enforcing resource limits becomes straightforward using two primary constraints:

1. AddNoOverlap: Ensures that no two tasks in a list overlap. This is ideal for single-threaded resources (e.g., one migration per host at a time).
2. AddCumulative: Models resources with a specific capacity. For example, if a host has a total network throughput of 5 units, and different VMs require different amounts of that throughput, AddCumulative ensures the sum of all active migrations never exceeds 5.

# Limiting total throughput across concurrent migrations
model.AddCumulative(vm_intervals, vm_throughputs, host_maximum_throughput)

CP-SAT vs. Mixed Integer Programming (MIP)

Many developers first attempt scheduling problems using MIP solvers. However, MIP typically requires one of two formulations, both of which have significant drawbacks:

1. Time-Indexed Formulation

This approach creates binary variables for every possible time step (e.g., active[task, time]). While intuitive, it scales poorly. As the planning horizon or the number of tasks increases, the number of variables grows exponentially, often making the problem unsolvable for real-world horizons (like a 24-hour window measured in minutes).

2. Time-Continuous Formulation

To avoid the time-index explosion, one can use binary "ordering" variables to specify if task A finishes before task B starts. While more efficient for large horizons, this is mathematically cumbersome. Implementing a cumulative resource constraint (like throughput) in MIP requires complex "Big-M" constraints and additional binary variables for every pair of tasks, leading to models that are difficult to write, debug, and maintain.

Practical Considerations and Trade-offs

While CP-SAT is highly expressive, it is not a silver bullet. Community insights highlight several key considerations for those implementing these solvers:

Scalability Limits

For extremely large-scale problems—such as assigning millions of shards to tens of thousands of tasks—even CP-SAT can become too slow. In such cases, engineers may need to move toward "hand-rolled" heuristics that provide sub-optimal but timely assignments.

Metaheuristic Alternatives

For certain problems, such as the Vehicle Routing Problem (VRP), metaheuristic solvers (e.g., Simulated Annealing or Tabu Search) may outperform CP-SAT. These solvers don't require a formal mathematical model of the problem; they only need a cost function to compare two different solutions. Tools like Timefold are often cited as alternatives when "good enough" solutions are needed faster than an optimal one.

The "AI" Misconception

Interestingly, there is a growing trend of labeling these solvers as "AI." While OR-Tools is hosted under Google AI, CP-SAT is based on Constraint Programming and SAT solving—technologies rooted in the 1960s. Unlike LLMs, these solvers provide deterministic guarantees and optimal solutions based on hard constraints, making them indispensable for infrastructure where "hallucinations" are not an option.

Summary

For most scheduling problems, the abstraction provided by CP-SAT's interval variables and cumulative constraints makes it the superior choice over MIP. It reduces the cognitive load on the developer and typically offers better performance for time-based constraints. For those looking to dive deeper, the CP-SAT Primer by Dr. Dominik Krupke is a highly recommended resource for mastering the nuances of the solver.