Approximation scheduling algorithms for electric vehicle charging with discrete charging options

To cope with the high-level penetration of electric vehicles (EVs), an intelligent scheduling mechanism for EV charging is required for maintaining the electricity grid within the operating limits, mitigating the demand peaks, and maximizing the benet of intermient renewable energy. is paper studies the scheduling optimization problem of EV charging in the presence of discrete charging options with minimum power requirements. We present an approximation algorithm to solve the scheduling optimization problem of EV charging, which has a provably small parameterized gap with the optimal solution. We also present a pruning scheme and specic conditions that can improve the running time in practice. Based on this algorithm, we further provide a fast heuristic with a signicant reduction in the running time. Finally, extensive simulations show our algorithms can produce close-to-optimal solutions in practice.