  We consider an increasingly popular demand-response scenario where a user
schedules the flexible electric vehicle (EV) charging load in response to
real-time electricity prices. The objective is to minimize the total charging
cost with user dissatisfaction taken into account. We focus on the online
setting where neither accurate prediction nor distribution of future real-time
prices is available to the user when making irrevocable charging decision in
each time slot. The emphasis on considering user dissatisfaction and achieving
optimal competitive ratio differentiates our work from existing ones and makes
our study uniquely challenging. Our key contribution is two simple online
algorithms with the best possible competitive ratio among all deterministic
algorithms. The optimal competitive ratio is upper-bounded by \min\left\{
\sqrt{\alpha/p_{\min}},p_{\max}/p_{\min}\right\} and the bound is
asymptotically tight with respect to \alpha, where p_{\max} and p_{\min} are
the upper and lower bounds of real-time prices and \alpha\geq p_{\min} captures
the consideration of user dissatisfaction. The bound under small and large
values of \alpha suggests the fundamental difference of the problems with
considering user dissatisfaction (\alpha takes small values) and without
(\alpha takes large values). Along the way we also develop a general technique
for designing online algorithms from an idea hinted in One-Way-Trading Problem,
which can be of independent interest. Simulation results based on real-world
traces corroborate our theoretical findings and show that our algorithms
achieve substantial performance gain as compared to conceivable alternatives.
The results also suggest that increasing EV charging rate limit decreases
overall cost almost linearly.
