Solver-Free and Cost-Aware Online Scheduling of AI Data Center Tasks

Xin Qin, Dawei Qiu, Fei TengarXiv 2026 · arXiv

In the rapidly expanding world of AI data centers (AIDCs), electricity isn't just an overhead—it's the single largest operating expense, often accounting for two-thirds of total costs. While wholesale electricity prices fluctuate throughout the day, AI tasks arrive at the data center continuously, second by second. This creates a "timing gap": traditional optimization tools (solvers) are too slow to run for every arriving task, but waiting to batch tasks means missing out on the cheapest electricity windows.

A new paper titled "Solver-Free and Cost-Aware Online Scheduling of AI Data Center Tasks" proposes an elegant bridge for this gap. By ditching heavy optimization solvers in favor of a fast, mathematically-grounded rule, the authors demonstrate how to slash energy costs in real-time without delaying critical workloads.

TL;DR

The authors develop a "solver-free" online scheduling rule that assigns AI tasks to the cheapest available time slots the moment they arrive. By using a simplified version of dual decomposition, the method achieves energy costs within 1.7% of a perfect "future-seeing" optimum while running over 1,000 times faster than traditional rolling optimization methods.

What Problem Does This Paper Address?

AIDCs face a fundamental mismatch in timescales. On one hand, computing tasks (like training a large language model or running real-time inference) arrive continuously. On the other hand, electricity is priced in settlement periods (e.g., every 15 or 60 minutes).

Current scheduling approaches usually fall into one of two traps:

  1. The Delay Trap: Waiting for a specific "settlement period" to run a batch optimization. This makes tasks wait unnecessarily and can cause them to miss low-price windows.
  2. The Complexity Trap: Trying to solve a Mixed-Integer Linear Programming (MILP) problem every time a task arrives. This is computationally expensive and often fails to finish before the next task arrives.

The challenge is to create a rule that can make a "good enough" decision in milliseconds, respecting hardware limits (GPU and CPU capacity) and task priorities (some tasks can wait, others can't).

Methods

The core innovation is a solver-free online rule inspired by dual decomposition. In formal optimization, "shadow prices" represent the cost of using a limited resource. The authors simplify this: if a resource (GPU/CPU) is available, its shadow price is zero; if it's full, the price is infinite.

The workflow, illustrated in Figure 1, follows these steps for every arriving task:

  1. Forecast: Use day-ahead electricity prices as a proxy for real-time costs.
  2. Reserve: Maintain a "reservation" for high-priority (HP) tasks to ensure they always have a slot.
  3. Evaluate: For an arriving task, check all possible start times within its allowed delay.
  4. Select: Pick the cheapest start time where the task's resource needs fit within the remaining capacity.
  5. Commit: Update the data center's committed resource state and move to the next task.

![Fig.

  1. Workflow of the proposed solver-free online scheduling rule.](/figures/art_f254aebbbb234507aff9d20478611965)

Datasets

The researchers evaluated their method using a practical AI workload trace:

  • Hardware: A simulated cluster of 3,456 NVIDIA A100 GPUs and 55,296 vCPUs.
  • Workload: A trace of 1,343 tasks categorized into three priorities: High-Priority (no delay allowed), Priority (up to 60 min delay), and Spot (up to 120 min delay).
  • Electricity Prices: Real-world locational marginal prices from the CAISO (California ISO) market for August 21, 2026 (simulated/forecasted).

Key Insights and Ideas

  • Shadow Prices as Binary Gates: By treating resource constraints as binary (available vs. unavailable), the authors transform a complex optimization problem into a simple search-and-select rule.
  • Capacity Reservation is Key: Unlike some "rolling" benchmarks that might accidentally fill up a cluster with low-priority tasks during cheap hours, this method explicitly reserves space for future high-priority arrivals. This ensures that "saving money" doesn't come at the cost of "missing deadlines."
  • The Power of Forecasts: Even using a simple day-ahead price forecast allows the system to shift "Spot" tasks to significantly cheaper hours, as seen in the price fluctuations in Figure 2.

![Fig.

  1. Day-ahead and real-time prices of CAISO NP15 on August 21, 2026.](/figures/art_397f23bf0aef4194b7b6e4b205a5c8e2)

Key Results

The proposed rule was compared against an "Earliest Feasible" rule (Benchmark 1), a "Rolling MILP" solver (Benchmark 2), and a "Perfect" offline optimum.

  • Cost Savings: The proposed rule achieved a 9.9% lower energy cost than the simple "Earliest Feasible" approach.
  • Extreme Speed: It required only 0.024 ms per decision, compared to 41.4 ms for the rolling MILP. This makes it truly viable for high-frequency task arrivals.
  • Near-Optimal Performance: The total cost was within 1.7% of the "Perfect" optimum, which assumes you know all future task arrivals and prices in advance.
  • Reliability: While the rolling MILP benchmark (Benchmark 2) actually caused seven high-priority tasks to start late due to lack of reservation, the proposed rule kept 100% of high-priority tasks on schedule.

Limitations and Future Work

While highly effective, the authors note a few areas for further development:

  • Price Uncertainty: The current model relies on day-ahead prices as a forecast. Significant deviations in real-time prices can reduce the effectiveness of the scheduling.
  • Scope: The study focuses on task start times but does not yet integrate on-site renewable generation (like solar/batteries) or dynamic cooling adjustments, which are also major factors in data center efficiency.
  • Theoretical Bounds: Future work will aim to establish a formal "competitive ratio" to mathematically guarantee how close this online rule stays to the offline optimum under all conditions.

Summary updated

Abstract

AI data centers receive computing tasks continuously, whereas solver-based optimization takes time to run and electricity is priced per settlement period. This paper bridges this timing gap through a solver-free online optimization rule inspired by dual decomposition. The rule assigns each task a start period upon arrival to optimize energy cost subject to operational constraints, shifting flexible tasks toward low-price periods while keeping high-priority tasks on schedule. Simulations on the A100 GPU trace (3,456 GPUs, 1,343 tasks) show that the proposed rule keeps GPU and CPU use within capacity while scheduling tasks at low cost. Compared with a multi-timescale optimization benchmark, it achieves a lower cost and, because it needs no solver, much less computation time.
BibTeX
@misc{qin2026solver,
  author = {Xin Qin and Dawei Qiu and Fei Teng},
  title = {{Solver-Free and Cost-Aware Online Scheduling of AI Data Center Tasks}},
  year = {2026},
  eprint = {2611.22239},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.22239},
}
Figure