Large scale charging of Electric Vehicles

The problem of scheduling for large scale charging of Electric Vehicles (EVs) is considered. As part of the future EV infrastructure, a Large Scale Charging (LSC) facility is capable of charging hundreds of electric vehicles simultaneously. As an intelligent load in the future smart grid, LSC requires properly designed pricing and scheduling algorithms that take into account the electricity consumed, the arrival-departure characteristics, and overall charging capacity. The scheduling of LSC is formulated as a deadline scheduling problem. Utility functions that combine both amount of charge and tightness of the deadline are proposed. Under arbitrary (and deterministic) arrival, departure, and charging characteristics, a scheduling policy referred to as deadline scheduling with admission control is proposed. The proposed algorithm achieves the highest competitive ratio (against the best offline scheduling) for the utility function linear in charging level among all online scheduling algorithms. It also offers significant gain over benchmark scheduling algorithms such as the Earliest Deadline First (EDF) scheduling and the First Come First Serve (FCFS) scheduling in terms of average performance for general utility functions when tested with randomly generated charging requests.