  Nowadays, there has been a rapid growth in global usage of the electronic
vehicles (EV). Despite apparent environmental and economic advantages of EVs,
their high demand charging jobs pose an immense challenge to the existing
electricity grid infrastructure. In microgrids, as the small-scale version of
traditional power grid, however, the EV charging scheduling is more
challenging. This is because, the microgrid owner, as a large electricity
customer, is interested in shaving its global peak demand, i.e., the aggregated
demand over multiple parking stations, to reduce total electricity cost. While
the EV charging scheduling problem in single station scenario has been studied
extensively in the previous research, the microgrid-level problem with multiple
stations subject to a global peak constraint is not tackled. This paper aims to
propose a near-optimal EV charging scheduling mechanism in a microgrid governed
by a single utility provider with multiple charging stations. The goal is to
maximize the total revenue while respecting both local and global peak
constraints. The underlying problem, however, is a NP-hard mixed integer linear
problem which is difficult to tackle and calls for approximation algorithm
design. We design a primaldual scheduling algorithm which runs in polynomial
time and achieves bounded approximation ratio. Moreover, the proposed global
scheduling algorithm applies a valley-filling strategy to further reduce the
global peak. Simulation results show that the performance of the proposed
algorithm is 98% of the optimum, which is much better than the theoretical
bound obtained by our approximation analysis. Our algorithm reduces the peak
demand obtained by the existing alternative algorithm by 16% and simultaneously
achieves better resource utilization.
