# Complexity of Scheduling Charging in the Smart Grid

arXiv: https://arxiv.org/abs/1709.07480 · HTML: https://mlsanity.com/paper/1709.07480/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Sep 2017.

## Built on by (most cited first, 2 of 2)

- [Sparse Training Theory for Scalable and Efficient Agents](https://mlsanity.com/paper/2103.01636/) (2021)
- [Press Start to Charge: Videogaming the Online Centralized Charging Scheduling Problem](https://mlsanity.com/paper/2601.12543/) (2026)

## Abstract (arXiv)

In the smart grid, the intent is to use flexibility in demand, both to balance demand and supply as well as to resolve potential congestion. A first prominent example of such flexible demand is the charging of electric vehicles, which do not necessarily need to be charged as soon as they are plugged in. The problem of optimally scheduling the charging demand of electric vehicles within the constraints of the electricity infrastructure is called the charge scheduling problem. The models of the charging speed, horizon, and charging demand determine the computational complexity of the charge scheduling problem. For about 20 variants, we show, using a dynamic programming approach, that the problem is either in P or weakly NP-hard. We also show that about 10 variants of the problem are strongly NP-hard, presenting a potentially significant obstacle to their use in practical situations of scale.