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.
CarlierJ. The one-machine sequencing problem. European Journal of Operational Research. 1982; 11: 42-47.
3.
BalasESimonettiNVazacopoulosA. Job shop scheduling with setup times, deadlines and precedence constraints. Journal of Scheduling. 2008; 11: 253-262.
4.
Hernández-ArauzoAPuenteJVarelaRSedanoJ. Electric vehicle charging under power and balance constraints as dynamic scheduling. Computers and Industrial Engineering. 2015; 85: 306-315.
5.
GrahamRLLawlerELLenstraJKKanAHGR. Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics. 1979; 5: 287-326.
6.
MencíaCSierraMRMencíaRVarelaR. In: Genetic Algorithm for Scheduling Charging Times of Electric Vehicles Subject to Time Dependent Power Availability. Ferrández VicenteJMÁlvarez-SánchezJRde la Paz LópezFToledo MoreoJAdeliH, editors, Cham: Springer International Publishing, 2017; 160-169.
7.
TalbiE. Metaheuristics-From Design to Implementation. Wiley, 2009.
8.
ReynoldsRGSverdlikW. Problem solving using cultural algorithms. Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence, Orlando, Florida, USA, June 27-29, 1994. IEEE; 1994; 645-650. Available from: https://doi.org/10.1109/ICEC.1994.349983.
9.
EDSO; 10 April 2012. Position paper on electric vehicles charging infrastructure. European Distribution system Operators for Smart Grids (EDSO). http://www.edsoforsmartgrids.eu.
10.
GanLTopcuULowS. Optimal decentralized protocol for electric vehicle charging. IEEE Conference on Decision and Control and European Control Conference, CDC-ECE, 2011; 5798-5804.
11.
WuDAliprantisDCYingL. Load scheduling and dispatch for aggregators of plug-in electric vehicles. IEEE Transactions on Smart Grid. 2012 March; 3(1): 368-376.
12.
MaZCallawayDSHiskensIA. Decentralized charging control of large populations of plug-in electric vehicles. IEEE Transactions on Control Systems Technology. 2013; 21(1): 67-78.
13.
KimHJLeeJParkGL. Constraint-based charging scheduler design for electric vehicles. Proceedings of the 4th Asian conference on Intelligent Information and Database Systems-Volume Part III. ACIIDS’12. Berlin, Heidelberg: Springer-Verlag; 2012; 266-275.
14.
KangJDuncanSJMavrisDN. Real-time scheduling techniques for electric vehicle charging in support of frequency regulation. Procedia Computer Science. 2013; 16: 767-775.
15.
XydasEMarmarasCCipciganLM. A multi-agent based scheduling algorithm for adaptive electric vehicles charging. Applied Energy. 2016; 177: 354-365.
16.
BinettiGDavoudiANasoDTurchianoBLewisFL. Scalable real-time electric vehicles charging with discrete charging rates. IEEE Transactions on Smart Grid. 2015; 6(5): 2211-2220.
17.
KamankeshHAgelidisVGKavousi-FardA. Optimal scheduling of renewable micro-grids considering plug-in hybrid electric vehicle charging demand. Energy. 2016; 100: 285-297.
18.
SubramanianAGarcáMDomínguez-GarcíaACallawayDPoollaandKVaraiyaP. Real-time scheduling of deferrable electric loads. Proceedings of American Control Conference (ACC), 2012; 3643-3650.
19.
ZhangTChenWHanZCaoZ. Charging scheduling of electric vehicles with local renewable energy under uncertain electric vehicle arrival and grid power price. IEEE Transactions on Vehicular Technology. 2014; 63(6): 2600-2612.
20.
GodinaRRodriguesEMGMatiasJCOCataloJPS. Smart electric vehicle charging scheduler for overloading prevention of an industry client power distribution transformer. Applied Energy. 2016; 178: 29-42.
21.
AlipourMMohammadi-IvatlooBMoradi-DalvandMZareK. Stochastic scheduling of aggregators of plug-in electric vehicles for participation in energy and ancillary service markets. Energy. 2017; 118: 1168-1179.
22.
JinXMuYJiaHWuJXuXYuX. Optimal day-ahead scheduling of integrated urban energy systems. Applied Energy. 2016; 180: 1-13.
23.
OttesenSØKorpåsMTomasgardA. Smart electric vehicle charging scheduling at capacity limited charging sites. Censes Working Paper 3/2016, Norwegian University of Science and Technology. 2016; 1-23.
24.
SedanoJPortalMHernández-ArauzoAVillarJRPuenteJVarelaR. Intelligent system for electric vehicle charging: Design and operation. DYNA. 2013; 88(6): 640-647.
25.
(IEC) TIEC; Electric Vehicle Conductive Charging System?Part 1: General Requirement; IEC 61851-1. London, UK, 2001.
26.
KoulamasC. The total tardiness problem: Review and extensions. Operations Research. 1994; 42: 1025-1041.
27.
SchmidtG. Scheduling with limited machine availability. European Journal of Operational Research. 2000; 121(1): 1-15. Available from: https://doi.org/10.1016/S0377-2217(98)00367-1.
28.
GareyMRJohnsonDS. Computers and Intractability. Freeman, 1979.
29.
GifflerBThompsonGL. Algorithms for solving production scheduling problems. Operations Research. 1960; 8: 487-503.
30.
ArtiguesCLopezPAyachePD. Schedule generation schemes for the job shop problem with sequence-dependent setup times: Dominance properties and computational analysis. Annals of Operations Research. 2005; 138: 21-52.
31.
MencíaRSierraMRMencíaCVarelaR. Genetic algorithms for the scheduling problem with arbitrary precedence relations and skilled operators. Integrated Computer-Aided Engineering. 2016; 23(3): 269-285.
32.
SprecherAKolischRDrexlA. Semi-active, active, and non-delay schedules for the resource-constrained project scheduling problem. European Journal of Operational Research. 1995; 80: 94-102.
33.
HungSAdeliH. A parallel genetic/neural network learning algorithm for MIMD shared memory machines. IEEE Trans Neural Networks. 1994; 5(6): 900-909. Available from: https://doi.org/10.1109/72.329686.
34.
KocieckiMAdeliH. Two-phase genetic algorithm for size optimization of free-form steel space-frame roof structures. Journal of Constructional Steel Research. 2013; 90: 283-296. Available from: http://www.sciencedirect.com/science/article/pii/S0143974X13002204.
35.
KocieckiMAdeliH. Shape optimization of free-form steel space-frame roof structures with complex geometries using evolutionary computing. Engineering Applications of Artificial Intelligence. 2015; 38: 168-182. Available from: http://www.sciencedirect.com/science/article/pii/S0952197614002528.
36.
LiWSchonfeldPYangJZhangHWangLXiongJ. Mountain railway alignment optimization with bidirectional distance transform and genetic algorithm. Computer-Aided Civil and Infraestructure Engineering. 2017; 32(8): 691-709.
37.
PrietoABellasFTruebaPDuroRJ. Real-time optimization of collective non-separable problems through distributed embodied evolution. Integrated Computer-Aided Engineering. 2016; 23(3): 237-253.
38.
PillonPEPedrinoECRodaVONicolettiMC. A hardware oriented ad-hoc computer-based method for binary structuring element decomposition based on genetic algorithms. Integrated Computer-Aided Engineering. 2016; 23(4): 369-383.
39.
KyriklidisCDouniasG. Evolutionary computation for resource leveling optimization in project management. Integrated Computer-Aided Engineering. 2016; 23(2): 161-172.
40.
AhnSLeeSBahnH. A smart elevator scheduler that considers dynamic changes of energy cost and user traffic. Integrated Computer-Aided Engineering. 2017; 24(2): 187-202.
41.
DavisL. Applying adaptive algorithms to epistatic domains. IJCAI, 1985; 162-164. Available from: http://ijcai.org/Proceedings/85-1/Papers/029.pdf.
42.
Van LaarhovenPAartsELenstraK. Job shop scheduling by simulated annealing. Operations Research. 1992; 40: 113-125.
43.
NowickiESmutnickiC. An advanced tabu search Algorithm for The job shop problem. Journal of Scheduling. 2005; 8: 145-159.
44.
ZhangCYLiPRaoYGuanZ. A very fast TS/SA algorithm for the job shop scheduling problem. Computers and Operations Research. 2008; 35: 282-294.
45.
AdamsJBalasEZawackD. The shifting bottleneck procedure for job shop scheduling. Managament Science. 1988; 34: 391-401.
46.
PapakostasNChryssolourisG. A scheduling policy for improving tardiness performance. Asian International Journal of Science and Technology. 2009; 2(3): 79-89.
47.
RossiFBeekPVWalshT. Handbook of constraint programming (foundations of artificial intelligence). New York, NY, USA: Elsevier Science Inc., 2006.
48.
ShawP. Using constraint programming and local search methods to solve vehicle routing problems. Maher MJ, Puget J, editors. Principles and Practice of Constraint Programming – CP98, 4th International Conference, Pisa, Italy, October 26-30, 1998, Proceedings. vol. 1520 of Lecture Notes in Computer Science. Springer; 1998; 417–431. Available from: https://doi.org/10.1007/3-540-49481-2_30.
49.
BrankeJNguyenSPickardtCWZhangM. Automated design of production scheduling heuristics: A review. IEEE Trans Evolutionary Computation. 2016; 20(1): 110-124. Avai- lable from: https://doi.org/10.1109/TEVC.2015.2429314.
PanLHeCTianYSuYZhangX. A region division based diversity maintaining approach for many-objective optimization. Integrated Computer-Aided Engineering. 2017; 24(3): 279-296.
52.
WangQLiuHYuanJChenL. Optimizing the energy-spectrum efficiency of cellular systems by evolutionary multi-objective algorithm. Integrated Computer-Aided Engineering. 2018; Pre-press: 1-14.
