CoChat
Sign Up
Cited by 39Electric Vehicles and InfrastructureSmart Grid Energy ManagementElectric Power System Optimization

Smoothed Least-Laxity-First Algorithm for Electric Vehicle Charging: Online Decision and Performance Analysis with Resource Augmentation

Open access
Chen, Niangjun, Kurniawan, Christian, Nakahira, Yorie, Chen, Lijun, Low, Steven H.·2022·IEEE Transactions on Smart Grid
DOI 10.1109/tsg.2021.3138615
Open this paper in CoChat — free accountOpen PDF

Abstract

Adaptive charging can charge electric vehicles (EVs) at scale cost effectively, despite of the uncertainty in EV arrivals. We formulate adaptive EV charging as a feasibility problem that meets all EVs’ energy demands before their deadlines while satisfying constraints in charging rate and total charging power. We propose an online algorithm, smoothed least-laxity-first (sLLF), that decides the current charging rates without the knowledge of future arrivals and demands. We characterize the performance of the sLLF algorithm analytically and numerically. Numerical experiments with real-world data show that it has a significantly higher rate of feasible EV charging than several other existing EV charging algorithms. Resource augmentation framework is employed to assess the feasibility condition of the algorithm. The assessment shows that the sLLF algorithm achieves perfect feasibility with only a 7% increase in the maximal power supply of the charging station.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1109/tsg.2021.3138615

Cites

1 of 1 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 34

  1. [2][2] O. Sundstr¨ om and C. Binding, 'Planning electric-drive vehicle charging under constrained grid conditions,' in Power System Technology (POWERCON), 2010 International Conference on . IEEE, 2010, pp. 1-6. -
  2. [3][3] A. Subramanian, M. J. Garcia, D. S. Callaway, K. Poolla, and P. Varaiya, 'Real-time scheduling of distributed resources,' IEEE Transactions on Smart Grid , vol. 4, no. 4, pp. 2122-2130, 2013. -
  3. [5][5] L. Gan, U. Topcu, and S. H. Low, 'Optimal decentralized protocol for electric vehicle charging,' IEEE Transactions on Power Systems , vol. 28, no. 2, pp. 940-951, 2013. -
  4. [6][6] Z. Ma, D. Callaway, and I. Hiskens, 'Decentralized charging control for large populations of plug-in electric vehicles,' in 49th IEEE conference on decision and control (CDC) . IEEE, 2010, pp. 206-212. -
  5. [7][7] N. Chen, C. W. Tan, and T. Q. Quek, 'Electric vehicle charging in smart grid: Optimality and valley-filling algorithms,' IEEE Journal of Selected Topics in Signal Processing , vol. 8, no. 6, pp. 1073-1083, 2014. -
  6. [8][8] L. Gan, A. Wierman, U. Topcu, N. Chen, and S. H. Low, 'Realtime deferrable load control: handling the uncertainties of renewable generation,' in Proceedings of the fourth international conference on Future energy systems . ACM, 2013, pp. 113-124. -
  7. [9][9] S. Chen, Y. Ji, and L. Tong, 'Large scale charging of electric vehicles,' in 2012 IEEE Power and Energy Society General Meeting . IEEE, 2012, pp. 1-9. -
  8. [10][10] Z. Yu, Y. Xu, and L. Tong, 'Deadline scheduling as restless bandits,' arXiv preprint arXiv:1610.00399 , 2016. - · arXiv
  9. [11][11] S. Stein, E. Gerding, V. Robu, and N. R. Jennings, 'A modelbased online mechanism with pre-commitment and its application to electric vehicle charging,' in Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 2 , ser. AAMAS '12. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems, 2012, pp. 669-676. [Online]. Available: http://dl.acm.org/citation.cfm?id=2343776.2343792 -
  10. [12][12] L. Sha, T. Abdelzaher, K.-E. ˚ Arz´ en, A. Cervin, T. Baker, A. Burns, G. Buttazzo, M. Caccamo, J. Lehoczky, and A. K. Mok, 'Real time scheduling theory: A historical perspective,' Real-time systems , vol. 28, no. 2-3, pp. 101-155, 2004. -
  11. [13][13] R. Carvalho, L. Buzna, R. Gibbens, and F. Kelly, 'Congestion control in charging of electric vehicles,' arXiv preprint arXiv:1501.06957 , 2015. - · arXiv
  12. [14][14] F. Kong, Q. Xiang, L. Kong, and X. Liu, 'On-line event-driven scheduling for electric vehicle charging via park-and-charge,' in 2016 IEEE Real-Time Systems Symposium (RTSS)2016 IEEE . IEEE, 2016, pp. 69-78. -
  13. [15][15] L. Guo, K. F. Erliksson, and S. H. Low, 'Optimal online adaptive electric vehicle charging,' in 2017 IEEE Power Energy Society General Meeting , 2017. -
  14. [16][16] M. Alonso, H. Amaris, J. G. Germain, and J. M. Galan, 'Optimal charging scheduling of electric vehicles in smart grids by heuristic algorithms,' Energies , vol. 7, no. 4, pp. 2449-2475, 2014. [Online]. Available: https://www.mdpi.com/1996-1073/7/4/2449 -
  15. [17][17] T. Mao, X. Zhang, and B. Zhou, 'Intelligent energy management algorithms for ev-charging scheduling with consideration of multiple ev charging modes,' Energies , vol. 12, no. 2, 2019. [Online]. Available: https://www.mdpi.com/1996-1073/12/2/265 -
  16. [18][18] M. Elmehdi and M. Abdelilah, 'Genetic algorithm for optimal charge scheduling of electric vehicle fleet,' in Proceedings of the 2nd International Conference on Networking, Information Systems & Security , ser. NISS19. New York, NY, USA: Association for Computing Machinery, 2019. [Online]. Available: https://doi.org/10. 1145/3320326.3320329 -
  17. [19][19] J. A. Stankovic, M. Spuri, K. Ramamritham, and G. C. Buttazzo, Deadline scheduling for real-time systems: EDF and related algorithms . Springer Science & Business Media, 2012, vol. 460. -
  18. [20][20] P. Whittle, 'Restless bandits: Activity allocation in a changing world,' Journal of applied probability , vol. 25, no. A, pp. 287-298, 1988. -
  19. [21][21] M. Brenna, F. Foiadelli, C. Leone, and M. Longo, 'Electric vehicles charging technology review and optimal size estimation,' Journal of Electrical Engineering & Technology , vol. 15, no. 6, pp. 2539-2552, Nov 2020. [Online]. Available: https://doi.org/10.1007/ s42835-020-00547-x -
  20. [22][22] M. Amjad, A. Ahmad, M. H. Rehmani, and T. Umer, 'A review of evs charging: From the perspective of energy optimization, optimization approaches, and charging techniques,' Transportation Research Part D: Transport and Environment , vol. 62, pp. 386 - 417, 2018. [Online]. Available: http://www.sciencedirect.com/science/article/ pii/S1361920917306120 -
  21. [23][23] B. Kalyanasundaram and K. Pruhs, 'Speed is as powerful as clairvoyance,' Journal of the ACM (JACM) , vol. 47, no. 4, pp. 617-643, 2000. -
  22. [24][24] Phillips, Stein, Torng, and Wein, 'Optimal time-critical scheduling via resource augmentation,' Algorithmica , vol. 32, no. 2, pp. 163-200, 2002. [Online]. Available: http://dx.doi.org/10.1007/s00453-001-0068-9 - · DOI
  23. [25][25] S. Im, J. Kulkarni, and K. Munagala, 'Competitive algorithms from competitive equilibria: non-clairvoyant scheduling under polyhedral constraints,' in Proceedings of the 46th Annual ACM Symposium on Theory of Computing . ACM, 2014, pp. 313-322. -
  24. [26][26] S. Im, J. Kulkarni, K. Munagala, and K. Pruhs, 'Selfishmigrate: A scalable algorithm for non-clairvoyantly scheduling heterogeneous processors,' in Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on . IEEE, 2014, pp. 531-540. -
  25. [27][27] C. L. Liu and J. W. Layland, 'Scheduling algorithms for multiprogramming in a hard-real-time environment,' Journal of the ACM (JACM) , vol. 20, no. 1, pp. 46-61, 1973. -
  26. [28][28] M. L. Dertouzos and A. K. Mok, 'Multiprocessor online scheduling of hard-real-time tasks,' IEEE Transactions on software engineering , vol. 15, no. 12, pp. 1497-1506, 1989. -
  27. [29][29] R. I. Davis and A. Burns, 'A survey of hard real-time scheduling for multiprocessor systems,' ACM Computing Surveys (CSUR) , vol. 43, no. 4, p. 35, 2011. -
  28. [30][30] G. Lee, T. Lee, Z. Low, S. H. Low, and C. Ortega, 'Adaptive charging network for electric vehicles,' in Proceedings of the IEEE Global Conference on Signal and Information Processing (GlobalSIP) , Washington, DC, December 2016. -
  29. [31][31] Z. Lee, D. Chang, C. Jin, G. S. Lee, R. Lee, T. Lee, and S. H. Low, 'Large-scale adaptive electric vehicle charging,' in Proceedings of the IEEE SmartGridComm Conference , Aalborg, Denmark, October 2018. -
  30. [32][32] Z. Lee, T. Li, and S. H. Low, 'ACN-Data: Analysis and applications of an open EV charging dataset,' in Proc. Tenth ACM International Conference on Future Energy Systems (e-Energy) , Phoenix, AZ, June 2019. -
  31. [33][33] A. K.-L. Mok, 'Fundamental Design Problems of Distributed Systems for The Hard-Real-Time Environment,' Ph.D. dissertation, Massachusetts Institute of Technology, 1983. [Online]. Available: http://hdl.handle.net/1721.1/15670 -
  32. [35][35] C. L. Liu and J. W. Layland, 'Scheduling algorithms for multiprogramming in a hard-real-time environment,' J. ACM , vol. 20, no. 1, p. 46-61, Jan. 1973. [Online]. Available: https://doi.org/10.1145/321738.321743 - · DOI · Paper page
  33. [36][36] J. Kay and P. Lauder, 'A fair share scheduler,' Commun. ACM , vol. 31, no. 1, p. 44-55, Jan. 1988. [Online]. Available: https: //doi.org/10.1145/35043.35047 - · DOI
  34. [37][37] S. Jiang, Z. Song, O. Weinstein, and H. Zhang, 'Faster dynamic matrix inverse for faster lps,' ArXiv , vol. abs/2004.07470, 2020. · arXiv

Cited by

Sorted by citations

Authors
Chen, N., Kurniawan, C., Nakahira, Y., Chen, L., & Low, S. H.
Affiliations
  • Agency for Science, Technology and Research (SG)
  • Carnegie Mellon University (US)
  • University of Colorado Boulder (US)
  • California Institute of Technology (US)
ORCID
Venue
IEEE Transactions on Smart Grid
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Published
2022-05
Volume
13
Issue
3
Pages
2209-2217
ISSN
  • 1949-3053 (ISSN-L)
  • 1949-3061
DOI
10.1109/tsg.2021.3138615
OpenAlex
W4205251093
Cited by
39
References
1
Citations by year
2026: 7 · 2025: 12 · 2024: 8 · 2023: 5 · 2022: 6 · 2021: 1
FWCI
1.47
Type
journal article
Language
en
Open access
Licence
Locations
  • IEEE Transactions on Smart Grid (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • CaltechAUTHORS (California Institute of Technology) (submittedVersion, cc-by)
  • CaltechAUTHORS (California Institute of Technology) (submittedVersion)
  • arXiv (Cornell University) (cc-by)
Topics
  • Physical Sciences › Engineering › Electrical and Electronic Engineering › Electric Vehicles and Infrastructure
  • Physical Sciences › Engineering › Electrical and Electronic Engineering › Smart Grid Energy Management
  • Physical Sciences › Engineering › Electrical and Electronic Engineering › Electric Power System Optimization
Keywords
electric vehicle charging, adaptive charging, online algorithms, resource augmentation, feasibility study

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review