Dynamic Scheduling for Charging Electric Vehicles: A Priority Rule
Authors:
Open Access
- 11 March 2016
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 61 (12) , 4094-4099
Abstract
We consider the scheduling of multiple tasks with pre-determined deadlines under arbitrarily random processing cost and task arrival. This problem is motivated by the potential of large scale adoption of plug-in (hybrid) electric vehicles (PHEVs) in the near future. We seek to properly schedule the battery charging of multiple PHEVs so as to minimize the overall cost, which is derived from the total charging cost and the penalty for not completing charging before requested deadlines. Through a dynamic programming formulation, we establish the Less Laxity and Longer remaining Processing time (LLLP) principle that improves any charging policy on a sample-path basis, when the non-completion penalty is a convex function of the additional time needed to fulfill the uncompleted request. Specifically, the LLLP principle states that priority should be given to vehicles that have less laxity and longer remaining processing times. Numerical results demonstrate that heuristic policies that violate the LLLP principle, for example, the earliest deadline first policy, can result in significant performance loss.Keywords
All Related Versions
Funding Information
- National Science Foundation
This publication has 20 references indexed in Scilit:
- Matching EV Charging Load With Uncertain Wind: A Simulation-Based Policy Improvement ApproachIEEE Transactions on Smart Grid, 2015
- Using ICT-Controlled Plug-in Electric Vehicles to Supply Grid Regulation in California at Different Renewable Integration LevelsIEEE Transactions on Smart Grid, 2012
- Optimal decentralized protocol for electric vehicle chargingIEEE Transactions on Power Systems, 2012
- A Multi-Agent System for Controlled Charging of a Large Population of Electric VehiclesIEEE Transactions on Power Systems, 2012
- Decentralized Charging Control of Large Populations of Plug-in Electric VehiclesIEEE Transactions on Control Systems Technology, 2011
- Integration of Electric Vehicles in the Electric Power SystemProceedings of the IEEE, 2010
- Coupling of day ahead and real-time power markets for energy and reserves incorporating local distribution network costs and congestion2010
- A Stochastic Optimal Control Approach for Power Management in Plug-In Hybrid Electric VehiclesIEEE Transactions on Control Systems Technology, 2010
- Multiprocessor online scheduling of hard-real-time tasksIEEE Transactions on Software Engineering, 1989
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973