Affiliations: Department of Computer Science, University of Oviedo, Gijón, Spain
Correspondence:
[*]
Corresponding author: Ramiro Varela, Department of Computer Science,
Abstract: It seems clear that general adoption of electric vehicles is coming in the near future. But this adoption will bring new challenges as, for example, that of recharging the batteries of a large fleet of electric vehicles under power and other technological constraints of the charging infrastructure. Among others, these will require solving challenging scheduling problems as well. In this paper, we study one of such problems derived from a charging station designed to be installed in community parks, which consists in scheduling a set of jobs on a single machine with varying capacity over time and exhibits high computational complexity. We propose the use of meta-heuristics as a means to solving the problem efficiently. Concretely, we propose a memetic algorithm, that combines a genetic algorithm with a local search method specifically designed for the problem. The contributions are analyzed theoretically, with formal proofs of their properties, and evaluated empirically. Experimental results show that the proposed memetic algorithm is very effective at solving the problem, while keeping running times reasonably low.
Keywords: Scheduling, one machine scheduling, electric vehicles charging, genetic algorithm, local search
