Time and energy driven online scheduling problem in EV charging

Xinru Guo; Sijia Dai; Xinxin Han; Yicheng Xu; Yong Zhang

doi:10.1016/j.tcs.2025.115266

Time and energy driven online scheduling problem in EV charging

Xinru Guo
, Sijia Dai
, Xinxin Han^*
, Yicheng Xu
, Yong Zhang

^*Corresponding author for this work

Department of Computer Science

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

1 Citation (Scopus)

Abstract

Electric vehicles (EVs) become more and more popular, along with the higher and higher efficiency demand for charging scheduling. This paper studies the online scheduling problem of EV charging that minimizes the maximum flow time, solving the problem of queuing congestion at charging stations during peak hours. Based on the characteristics of the charging power curve of electric vehicles, we design an online scheduling algorithm for EV charging and prove that the ratio of this algorithm to the optimal offline algorithm is γ = 3.4528 ⋅ (1 + ϵ). We analyse and find that the proposed algorithm can adjust the charging time proportionally, allowing the electric vehicle EV j to gradually reach the final State of Charge (SOC), which is 0.7313 + 0.2687 ⋅ j_ini, from its initial charging state (j_ini). According to the battery overheating protection mechanism, charging will stop when the battery level starts to decrease. This method effectively balances the trade-off between time cost and energy intake, significantly improving the queuing situation for charging electric vehicles during peak hours. © 2025 Elsevier B.V.

Original language	English
Article number	115266
Journal	Theoretical Computer Science
Volume	1044
Online published	22 Apr 2025
DOIs	https://doi.org/10.1016/j.tcs.2025.115266
Publication status	Published - 1 Aug 2025

Bibliographical note

Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).

Funding

Supported by National Key R&D Program of China (No. 2022YFE0196100), Guangdong Basic and Applied Basic Research Foundation 2024A1515030197, NSFC 12071460, NSFC 12371321, Shenzhen Science and Technology Program CJGJZD20210408092806017, Shenzhen Polytechnic Research Fund No. 6023310009K.

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 7 Affordable and Clean Energy

Research Keywords

Competitive analysis
EV charging
Flow-time
Online algorithm
Scheduling

Access Output

10.1016/j.tcs.2025.115266Licence: Elsevier user license

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{849f374a75b34a66b097b18f36238261,

title = "Time and energy driven online scheduling problem in EV charging",

abstract = "Electric vehicles (EVs) become more and more popular, along with the higher and higher efficiency demand for charging scheduling. This paper studies the online scheduling problem of EV charging that minimizes the maximum flow time, solving the problem of queuing congestion at charging stations during peak hours. Based on the characteristics of the charging power curve of electric vehicles, we design an online scheduling algorithm for EV charging and prove that the ratio of this algorithm to the optimal offline algorithm is γ = 3.4528 ⋅ (1 + ϵ). We analyse and find that the proposed algorithm can adjust the charging time proportionally, allowing the electric vehicle EV j to gradually reach the final State of Charge (SOC), which is 0.7313 + 0.2687 ⋅ jini, from its initial charging state (jini). According to the battery overheating protection mechanism, charging will stop when the battery level starts to decrease. This method effectively balances the trade-off between time cost and energy intake, significantly improving the queuing situation for charging electric vehicles during peak hours. {\textcopyright} 2025 Elsevier B.V.",

keywords = "Competitive analysis, EV charging, Flow-time, Online algorithm, Scheduling",

author = "Xinru Guo and Sijia Dai and Xinxin Han and Yicheng Xu and Yong Zhang",

note = "Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).",

year = "2025",

month = aug,

day = "1",

doi = "10.1016/j.tcs.2025.115266",

language = "English",

volume = "1044",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Time and energy driven online scheduling problem in EV charging

AU - Guo, Xinru

AU - Dai, Sijia

AU - Han, Xinxin

AU - Xu, Yicheng

AU - Zhang, Yong

N1 - Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).

PY - 2025/8/1

Y1 - 2025/8/1

N2 - Electric vehicles (EVs) become more and more popular, along with the higher and higher efficiency demand for charging scheduling. This paper studies the online scheduling problem of EV charging that minimizes the maximum flow time, solving the problem of queuing congestion at charging stations during peak hours. Based on the characteristics of the charging power curve of electric vehicles, we design an online scheduling algorithm for EV charging and prove that the ratio of this algorithm to the optimal offline algorithm is γ = 3.4528 ⋅ (1 + ϵ). We analyse and find that the proposed algorithm can adjust the charging time proportionally, allowing the electric vehicle EV j to gradually reach the final State of Charge (SOC), which is 0.7313 + 0.2687 ⋅ jini, from its initial charging state (jini). According to the battery overheating protection mechanism, charging will stop when the battery level starts to decrease. This method effectively balances the trade-off between time cost and energy intake, significantly improving the queuing situation for charging electric vehicles during peak hours. © 2025 Elsevier B.V.

AB - Electric vehicles (EVs) become more and more popular, along with the higher and higher efficiency demand for charging scheduling. This paper studies the online scheduling problem of EV charging that minimizes the maximum flow time, solving the problem of queuing congestion at charging stations during peak hours. Based on the characteristics of the charging power curve of electric vehicles, we design an online scheduling algorithm for EV charging and prove that the ratio of this algorithm to the optimal offline algorithm is γ = 3.4528 ⋅ (1 + ϵ). We analyse and find that the proposed algorithm can adjust the charging time proportionally, allowing the electric vehicle EV j to gradually reach the final State of Charge (SOC), which is 0.7313 + 0.2687 ⋅ jini, from its initial charging state (jini). According to the battery overheating protection mechanism, charging will stop when the battery level starts to decrease. This method effectively balances the trade-off between time cost and energy intake, significantly improving the queuing situation for charging electric vehicles during peak hours. © 2025 Elsevier B.V.

KW - Competitive analysis

KW - EV charging

KW - Flow-time

KW - Online algorithm

KW - Scheduling

UR - https://www.scopus.com/pages/publications/105003174250

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-105003174250&origin=recordpage

U2 - 10.1016/j.tcs.2025.115266

DO - 10.1016/j.tcs.2025.115266

M3 - RGC 21 - Publication in refereed journal

SN - 0304-3975

VL - 1044

JO - Theoretical Computer Science

JF - Theoretical Computer Science

M1 - 115266

ER -

Time and energy driven online scheduling problem in EV charging

Abstract

Bibliographical note

Funding

UN SDGs

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this