  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.
