Scheduling electric vehicle regular charging tasks: A review of deterministic models

We formulate a fairly general deterministic problem of scheduling electric vehicle (EV) regular charging tasks on parallel chargers over time. Charging task is called regular if it is performed at the same time and in the same place. The charging time and place can be fixed or selectable The scheduling decision time range can be an interval or a circle. Charging tasks may or may not be preemptive. Each charging preemption may imply a setup time and a cost. Each task requires a given amount of energy to be received from the chargers. This energy determines the charging time requirement. The chargers consume electric power which can be limited from above. The objective is to minimize the cost of the chargers and their locations, received energy, maximum power and setups, or a function of task completion times. The problem is typical for urban electric buses with fixed timetables and charging points at depots or along the route. It can also be a part of a more general EV routing and charging scheduling problem, which is often decomposed into the routing and charging scheduling parts in order to reduce computational complexity. Various special cases of this problem have been studied in the literature, in the theoretical and practical contexts. We review and analyze these special cases using traditional scheduling terminology, thereby creating a bridge between theoretical machine scheduling and practical charging scheduling research.