  We develop a new algorithm for scheduling the charging process of a large
number of electric vehicles (EVs) over a finite horizon. We assume that EVs
arrive at the charging stations with different charge levels and different
flexibility windows. The arrival process is assumed to have a known
distribution and that the charging process of EVs can be preemptive. We pose
the scheduling problem as a dynamic program with constraints. We show that the
resulting formulation leads to a monotone dynamic program with Lipschitz
continuous value functions that are robust against perturbation of system
parameters. We propose a simulation based fitted value iteration algorithm to
determine the value function approximately, and derive the sample complexity
for computing the approximately optimal solution.
