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

Because of 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 and strictly convex function of the corresponding aggregated power profile. To this end, we relate EV charging to processor speed scaling models with job-specific speed limits. Experiments based on real-world EV charging data show that FOCS takes only 2.5 seconds to schedule 400 EVs in 15-minute granularity. Furthermore, we analyze the online algorithms Average Rate and Optimal Available and show that they are, respectively, 2𝛼−1⁢𝛼𝛼 and 𝛼𝛼 competitive, where 𝛼 is typically two in energy applications. Further numerical experiments show that, for the real-world EV charging use case, both algorithms achieve approximation ratios of less than 1.3. Furthermore, they significantly improve on the uncontrolled default often applied in practice.