Relating Electric Vehicle Charging to Speed Scaling with Job-Specific Speed Limits

Leoni Winschermann, Marco E. T. Gerards, Antonios Antoniadis, Gerwin Hoogsteen, Johann L. HurinkOperations 2023

This paper, from researchers at the University of Twente, provides a rigorous mathematical bridge between two seemingly disparate worlds: the scheduling of electric vehicle (EV) charging and the classical computer science problem of "speed scaling" for processors.

TL;DR

The authors introduce a novel algorithm, FOCS, that optimally schedules EV charging to minimize grid impact while respecting individual vehicle power limits. By proving that this problem is a specific extension of processor speed scaling, they show that existing online strategies remain theoretically robust and practically efficient for managing large-scale charging infrastructure.

What Problem Does This Paper Address?

As we electrify transport, large parking lots (like those at offices or malls) face a major challenge: charging dozens or hundreds of EVs simultaneously can easily overwhelm local power grid capacities. To prevent this, we use Model Predictive Control (MPC), which repeatedly solves an "offline" optimization problem to find the smoothest charging profile that still meets everyone's energy needs by their departure time.

Mathematically, this is often treated as a speed scaling problem—a concept originally developed to manage CPU power by slowing down tasks to save energy. However, classical speed scaling models assume a single processor or don't account for individual "speed limits." In the EV world, every car has a different maximum charging rate (its "job-specific speed limit"). This paper fills that gap, providing a formal framework for scheduling multiple "jobs" (EVs) that run simultaneously, each with its own unique power constraint.

Methods

The authors define the Deadline-Based Speed-Scaling with Speed Limits (DSL) problem. Their primary contribution is the Flow-based Offline Charging Scheduler (FOCS).

  • FOCS Algorithm: Unlike generic solvers, FOCS uses a maximum flow network formulation. It iteratively identifies "critical intervals"—periods where the required charging power is highest—and fixes the schedule for those periods before moving to the next.
  • Optimality Proof: Using Karush-Kuhn-Tucker (KKT) conditions, the authors prove that FOCS always finds the mathematically optimal schedule for any increasing, convex objective function (like minimizing the sum of squares of power to reduce energy losses).
  • Online Adaptation: They also adapt two classic online algorithms—Average Rate (AVR) and Optimal Available (OA)—to the EV context. These algorithms make decisions in real-time as cars arrive, without knowing future arrivals.

Datasets

The study evaluates its algorithms using a substantial real-world dataset:

  • Utrecht Office Dataset: Data from an office parking lot in Utrecht, Netherlands, spanning September 2022 to June 2023.
  • Scope: 13,694 charging sessions, with a peak of 113 sessions in a single day.
  • Details: Each record includes arrival/departure times, total energy requested, and specific charging power limits (11 kW or 22 kW).

Key Insights and Ideas

  • The "Speed Limit" Doesn't Break the Theory: Surprisingly, adding individual speed limits to the model doesn't worsen the theoretical "competitive ratio" (the worst-case performance gap between an online algorithm and an all-knowing offline one). The ratios for the DSL problem match those of the classical speed scaling problem.
  • Feasibility is Tricky: The authors prove a "negative" result: even if you know the perfect total power profile for a parking lot, you cannot guarantee a feasible schedule for individual cars using a simple deterministic rule. You must account for individual car limits during the scheduling process, not just as an afterthought.
  • FOCS vs. Commercial Solvers: While commercial solvers like Gurobi are powerful, FOCS is designed to exploit the specific "flow" structure of the scheduling problem. This allows it to scale more gracefully as the number of EVs increases.

Key Results

  • Efficiency: FOCS can solve a full-day schedule for 400 EVs in approximately 2.5 seconds (median) using 15-minute intervals. This makes it highly suitable for real-time MPC applications.
  • Theoretical vs. Practical: While the theoretical worst-case competitive ratio for the "Optimal Available" algorithm is 4 (for a quadratic objective), testing on real-world data showed an empirical ratio of only 1.10 to 1.15. This suggests these algorithms perform much better in the real world than the math might suggest.
  • Peak Reduction: Compared to an uncontrolled "Greedy" approach (where cars charge at max power immediately), the optimized schedules reduced peak power demand by roughly 50%.

Limitations and Future Work

The current model assumes that the grid capacity itself is the only constraint being managed via the objective function. It does not explicitly model global power limits (hard caps on the total lot power) as a constraint, which is a common real-world requirement.

Additionally, the paper focuses on "one-way" charging. Future research could extend this framework to Vehicle-to-Grid (V2G) scenarios, where cars can discharge energy back into the grid, adding a new layer of complexity to the "speed scaling" analogy.

Summary updated

Abstract

Due to the ongoing electrification of transport in combination with limited power grid capacities, efficient ways to schedule the charging of electric vehicles (EVs) are needed for the operation of, for example, large parking lots. Common approaches such as model predictive control repeatedly solve a corresponding offline problem. In this work, we first present and analyze the Flow-based Offline Charging Scheduler (FOCS), an offline algorithm to derive an optimal EV charging schedule for a fleet of EVs that minimizes an increasing, convex and differentiable function of the corresponding aggregated power profile. To this end, we relate EV charging to processor speed scaling models with job-specific speed limits. We prove our algorithm to be optimal and derive necessary and sufficient conditions for any EV charging profile to be optimal. Furthermore, we discuss two online algorithms and their competitive ratios for a specific class objective functions. In particular, we show that if those algorithms are applied and adapted to the presented EV scheduling problem, the competitive ratios for Average Rate and Optimal Available match those of the classical speed scaling problem. Finally, we present numerical results using real-world EV charging data to put the theoretical competitive ratios into a practical perspective.
BibTeX
@inproceedings{winschermann2023relating,
  author = {Leoni Winschermann and Marco E. T. Gerards and Antonios Antoniadis and Gerwin Hoogsteen and Johann L. Hurink},
  title = {{Relating Electric Vehicle Charging to Speed Scaling with Job-Specific Speed Limits}},
  booktitle = {Operations},
  year = {2023},
}
Figure