Relating Electric Vehicle Charging to Speed Scaling with Job-Specific Speed Limits
研究了电动汽车充电的离线调度问题，提出了基于流的离线充电调度器（FOCS）算法，能最优求解，并量化了重复求解离线问题的近似比，实验表明最坏情况近似比为4，实际仅为1.3，且调度400辆电动车仅需数秒。
With the adoption of electric vehicles emerges a need for coordinated charging strategies to cater to the increased and often synchronized energy demand without violating physical infrastructure limits. Common charging strategies repeatedly solve a corresponding offline problem. In “Relating Electric Vehicle Charging to Speed Scaling with Job-Specific Speed Limits,” Winschermann, Antoniadis, Gerards, Hoogsteen, and Hurink thoroughly analyze that offline problem and present the flow-based offline charging scheduler (FOCS), an algorithm that solves the problem to optimality. The authors continue to quantify the approximation ratio of repeatedly solving the offline problem throughout the day as opposed to solving the offline problem with a priori knowledge of future arrivals. Numerical experiments confirmed that the found worst-case approximation ratio of 4 is far from the achieved empirical ratio of 1.3 when evaluating the ratio for real-world electric vehicle charging instances. Experiments based on that same real-world data show that FOCS only takes seconds to schedule 400 EVs in 15-minute granularity, which is competitive with commercial solvers.