  The successful launch of electric vehicles (EVs) depends critically on the
availability of convenient and economic charging facilities. The problem of
scheduling of large-scale charging of EVs by a service provider is considered.
A Markov decision process model is introduced in which EVs arrive randomly at a
charging facility with random demand and completion deadlines. The service
provider faces random charging costs, convex non-completion penalties, and a
peak power constraint that limits the maximum number of simultaneous activation
of EV chargers.
  Formulated as a restless multi-armed bandit problem, the EV charging problem
is shown to be indexable. A closed-form expression of the Whittle's index is
obtained for the case when the charging costs are constant. The Whittle's index
policy, however, is not optimal in general. An enhancement of the Whittle's
index policy based on spatial interchange according to the less laxity and
longer processing time principle is presented. The proposed policy outperforms
existing charging algorithms, especially when the charging costs are time
varying.
