arXiv:2403.03109v1 [math.OC] 5 Mar 2024

Abstract
We study Electric Vehicle (EV) charging from a scheduling perspective, aiming to minimize delays while respecting the grid constraints. A
network of parking lots is considered, each with a given number of charging stations for electric vehicles. Some of the parking lots have a roof with
solar panels. The demand that can be served at each parking lot is limited
by the capacity of the cables connecting them to the grid. We assume that
EVs arrive at the parking lots according to a known distribution. Upon
arrival, we learn the desired departure time, the amount of electrical energy it needs to charge its battery, and the range of rates that it can be
charged at. Vehicle arrival patterns, connection times, and charging volume are based on data collected in the city of Utrecht. The departure
time of an EV is delayed if it has not finished charging in time for its desired departure. We aim to minimize the total delay. We present a novel
approach, based on an online variant of well-known schedule generation
schemes. We extend these schemes and include them in a destroy-andrepair heuristic. This resulted in several scheduling strategies. We show
their effectiveness using a discrete event simulation. With this, we show
that applying scheduling approaches increases the amount of EVs that can
be charged at a site and reduces the average delay. Furthermore, we argue the importance of considering aspects of the grid layout in electricity
networks and show the benefits of using flexible charging rates.

1

Grid-constrained online scheduling of flexible
electric vehicle charging
Emily van Huffelen1 , Roel Brouwer1 , and Marjan van den Akker1
1

Department of Information and Computing Sciences, Utrecht
University, Utrecht, The Netherlands
March 6, 2024

1

Introduction

The number of electric vehicles (EVs) has rapidly increased in recent years. This
trend is likely to continue, as policies aiming to reduce greenhouse gas emissions
encourage their sale to replace vehicles that run on fossil fuels. The increasing
number of EVs requires charging stations to be installed in many locations. At
parking lots where many EVs congregate, such as one near a large office building
for example, managing the demand for charging the batteries of all these EVs
concurrently is a challenge. Such parking lots often have clear peaks in demand,
and are relatively quiet at other times. For parking lots outside of residential
neighborhoods, this peak in demand often occurs during the day, which matches
well with the peak in production of solar panels. Therefore, the installation of
a large number of charging stations is often paired with the installation of solar
panel arrays on roofs over these parking lots. Although the peaks in supply and
demand do not line up as nicely for parking lots in residential areas, solar panels
are commonly installed in these areas as well. The servicing of EVs at these
parking lots will benefit from smart scheduling of the charging jobs to align well
with the availability of power at the parking lot.
In this work, we consider a network of parking lots operated by the same
provider, who offers the service of parking and charging electric vehicles (EVs).
Each parking lot has a given number of charging stations for EVs. The demand
that can be served at each parking lot is limited by the amount of available
power. The power supply is constrained by the capacity of the cables connecting
the parking lots to the grid. Some parking lots are covered by a roof with solar
panels on it, supplying additional power under the right weather conditions.
We assume that EVs arrive at the parking lots according to a known distribution. As soon as a vehicle arrives, we learn its desired departure time, the
amount of electrical energy it needs to charge its battery before that time, and
the range of rates that it can be charged at. The charging of these EVs must
be scheduled in such a way that the total delay is minimized, while the network
constraints are respected. This means that the summed difference between the
desired departure time and the actual departure time, which is delayed if an EV
has not finished charging in time, must be minimal across all vehicles.
2

The charging of electric vehicles is a widely studied subject across multiple
disciplines, even if we limit ourselves to the (optimal) scheduling of charging
jobs. Many surveys aim to provide an overview of aspects of this problem.
Wang et al. [17] make a classification of EV charging control algorithms based
on their perspective and objective. They identify three categories: smart grid
oriented, aggregator oriented and customer oriented EV charging, describing
the perspective from which the problem is considered. Although the objectives
discussed in the review are mainly cost optimization objectives, we could consider our problem setting to align with the aggregator oriented model, as we aim
to provide the best possible service within the limited capacity of the network.
The control of EV charging can be considered on several ‘levels’, or time
scales [1]. The lowest level of control is reactive, and mainly concerns stabilization of the grid. Arif et al. [1] describe that EVs can be used at that level
to provide ancillary services by controlling the charging (grid-to-vehicle, G2V)
or discharging (vehicle-to-grid, V2G) at a very small time scale. Such time
scales make scheduling intractable. We focus on higher levels of control: aligning demand well with forecasts of solar panel output and the demand of other
EVs within the same network. The importance of the uncertainty of demand is
emphasized by Al-Ogaili et al. [14]. This implies that offline scheduling methods may struggle to account for the uncertainty surrounding the arrival times
and charging demands of EVs at charging locations. Therefore, we consider an
online scheduling approach.
Most surveys conclude that coordinated charging strategies, where some
centralized decision making is involved, yield the best results. Hussain et al.
[9], for example, states that “it is found that centralized coordination is best
strategy to handle all issues effectively.” Liu et al. [11] also find that centralized
approaches have better performance, but prefer decentralized approaches due
to the communication overhead of centralized approaches.
We will be looking at a centralized control strategy, from the perspective of
an aggregator. We aim to schedule the demand in a network of parking places as
well as possible, given the limited resources available. In this sense, the problem
we consider is closely related to the Resource-Constrainted Project Scheduling
Problem (RCPSP). The surveys by Hartmann and Briskorn [7, 8] give a good
overview of the RCPSP and its variants. The RCPSP with flexible resource
profiles (FRCPSP) such as studied by Naber [13] and the General Continuous
Energy-Constrained Scheduling Problem (GCECSP) [3]
The approaches we develop in this work are inspired by priority rule based
scheduling heuristics commonly employed for finding solutions to RCPSP and its
variants. Kolisch [10] provides a good overview of the application of schedule
generation schemes to the classical RCPSP. Lova et al. [12] apply schedule
generation schemes to the multi-mode RCPSP, where tasks can be processed
in a number of different modes, which can be seen as a discretized variant
of the flexible model we are considering. More recently, priority rule based
approaches that are similar to schedule generation schemes have been applied
to the stochastic RCPSP [4] and in the context of genetic algorithms, where
compound priority rules are learned for the generation of schedules [5].
Our contribution: We present a novel approach, based on an extension
of traditional schedule generation schemes to an online setting with flexible
charging rates. We consider single-pass methods, where we apply a scheme
once, as well as more advanced methods, where we include the schemes in a
3

P2
80
0.15
P1
60
0.15

P5
60
0.15

200
200

200
200

P3
60
0.15

200

200

P4
70
0.20

Transformer

P6
60
0.10

200

200

P7
50
0.10

200

Figure 1: Network layout
destroy-and-repair heuristic. In this way, we develop a number of variants of the
approach for the generation of efficient schedules for charging EVs on a network
of parking lots. As far as we are aware, similar approaches have not been applied
to this problem yet. We show the effectiveness of these approaches using a
discrete event simulation. Furthermore, we argue the importance of considering
aspects of the grid layout in electricity networks and show the benefits of using
flexible charging rates.
The work presented here is a continuation of earlier work by van Huffelen
[16]. The specific case is loosely based on an assignment used in the master’s course ‘Optimization for sustainability’ at Utrecht University [15]. The
data used for the distribution of arrival times, charging volumes and connection
times is based on real-world data from the city of Utrecht, and was provided by
Brinkel et al. [2]. The distribution of solar output is based on a forecast of the
production of solar panels in the Netherlands in 2025 [6].
The rest of this work is structured as follows. In Section 2, we give a detailed
problem description, followed by an explanation of the developed scheduling
approaches in Section 3. We present the results of evaluating our approaches
using that simulation in Section 4. Finally, we will draw some conclusions and
discuss avenues for future work in Section 5.

2

Problem description

We consider an online problem, where a schedule for the charging of EVs needs
to be generated with the objective to minimize the average delay. EVs arrive
over time, which implies that the schedule needs to be updated regularly. We
will discuss strategies for these updates in Section 3.
We consider a network that consists of a number of interconnected parking
lots, that share a grid connection. An example network is shown in Figure 1.
Each parking lot has:
• a number of parking spots, where EVs can be parked and charged;
• the fraction of EVs pPi that will select parking lot Pi;
4

• (optionally) an array of solar panels, producing a variable amount of
power.
These parking lots are connected by cables with a given maximum capacity.
The cable capacity limits the amount of power that can be transported to each
parking lot. We use this a simple approximation of the limits imposed by the
network.
The amount of power generated by the solar panels is based on the so-called
availability vector. This expresses the average production of solar panels at any
given time as a fraction of their peak power. The production of the solar panels
is revealed at the start of every hour, and treated as a constant production rate
for the entire hour.
The EVs arrive at this location according to a Poisson process. The arrival
rate is not constant, but changes every hour. Each EV j has a number of
properties, which are revealed when the vehicle arrives. Here, EV j is the jth
vehicle in the order of arrival:
• a connection time dj − rj , the amount of time between its arrival time rj
and its desired time of departure dj ;
• a charging volume Ej : the amount of energy required to fully charge its
battery before departure (in kWh);
• charging rates [Pj− , Pj+ ], a range of rates between a lower (Pj− ) and an
upper (Pj+ ) bound that can be used to charge it, in kW;
• a parking preference: a ordered list of three parking lots, where the EV
will try to park. If all three parking lots in the parking preference of an
EV are full, it will leave the area.
For each EV, we determine a start and completion time for the charging process.
The start time must be after its arrival, which implies that the EV may not start
charging immediately. After its start, we determine a charging profile that will
be followed. It completes when its full energy demand is served, which will be
earlier than or, if that is not possible, as close to its preferred departure time
as possible. Note that we guarantee that the connection time is never smaller
than the time it takes to charge an EV at its minimum rate, i.e. Ej /Pj− .
In addition, note that the existence of a lower bound implies that preemption
is not allowed: as soon as an EV has started charging, it cannot drop below the
lower bound on its charging rate before it completes. A reason for this is that
interruption of the charging process comes with some loss of efficiency caused
by startup and shutdown effects.
P
In this setting, we want to minimize the total tardiness j max(0, Cj − dj )
over all EVs that parked at the network of parking lots.
In this work, we use a case study for the evaluation of our approaches,
loosely based on an assignment used in the master’s course ‘Optimization for
sustainability’ at Utrecht University [15]. It uses the network depicted in Figure
1. All cables have a capacity of 200 kW. We use the availability factor predicted
for solar panels in summer in the Netherlands in 2025 [6], which we provide
in Appendix B.1. We assume the average hourly power output to follow a
normal distribution, with the value from the availability vector as its mean, and
a standard deviation of 15%. All solar panel arrays installed have a peak power
5

of 200 kW, unless explicitly stated otherwise. We assume an average arrival
rate of 1125 EVs per day. We use hourly arrival rates, charging volumes, and
connection times based on data from Brinkel et al. [2]. These distributions are
provided in Appendix B.2, B.4 and B.5. The distribution of charging ranges
can be found in Appendix B.3.

3

Scheduling

As EVs keep arriving continuously, we use an online scheduling approach. Only
the characteristics of the EVs that have already arrived have been revealed,
and the amount of power produced by the solar panels is only known for the
current hour. The available information will serve as the basis for a schedule
that determines when and at what rate each EV charges. In this section, we
will first introduce the methods that are used to find schedules based on this
information. After that, we will discuss a strategy for replacing these schedules
when new information is revealed.

3.1

Schedule generation schemes

In this chapter, we consider priority rule based scheduling heuristics. These are
made up of two components: a schedule generation scheme and a priority rule.
Priority rules will be discussed in Section 3.2. The schedule generation scheme
is a constructive heuristic that adds jobs to the schedule one by one, until a
feasible schedule is obtained.
There are two main variants of schedule generation schemes that are often
considered in literature: serial and parallel [10]. A convenient way to characterize the difference is that the serial scheme iterates over jobs, while the parallel
scheme iterates over points in time. The serial scheme aims to schedule the
highest priority job as early as possible, and the parallel scheme tries to fill the
current time with as high-priority jobs as possible. Both variants construct a
schedule by adding jobs, until all jobs have been placed. In simple schedule generation schemes, the schedule that results from this procedure is not adapted
further. These schemes are considered to be single-pass schedule generation
schemes, since they place all jobs in a single loop over jobs (serial) or time
(parallel).
At any stage in the construction, the serial scheme will select the unscheduled
job with highest priority (according to the priority rule) and schedule it as early
as possible. It will then repeat this until all jobs are scheduled. The parallel
scheme, in contrast, will select the highest priority job (or jobs, if enough power
remains available after the scheduling of the first one) that fits in the gap at the
current time in the schedule, which is not necessarily the highest priority job
available overall.
We extended these schemes in the following ways to apply them to our case:
Composite resource To check whether enough resource (power) is available
to process a job at a given rate, we need to check the load of all cables
and parking lots along the path from its source to the lot where the EV is
located. The residual capacity at a parking lot can be determined by an
elementary flow computation from the load at other parking lots, including
the contribution of solar panels, and the cable capacities.
6

Resilience against drops of solar power We need to guarantee the load on
the cables does not exceed the capacity, while using as much of the available power as we can. If, for whatever reason, the solar output should fall
away, we want to be able to guarantee that we can scale back charging on
some EVs to remain within the bounds of the cable capacity. Therefore,
we ensure that the EV’s that are currently charging, can charge at their
minimum rate without using solar power, i.e. solar power is only used to
increase the charging rate above the lower bound.
Flexible rate The jobs have a flexible resource consumption profile. This
means that we need to decide the consumption rate for each job for the
duration of its execution. When a job is selected to be added, it is placed
at the earliest possible time in the partial schedule, at the highest possible rate. It may start at any rate between its lower and upper bound.
From that point, it will always be scheduled to charge at the highest possible rate, until it completes. This rate is equal to its upper bound, or
the maximum rate allowed by the resource constraints, whichever is more
restrictive. This means the rate may change over time.
Avoid preemption Applying the schemes in an online setting means that we
need to take into account jobs that are already started when we reschedule. Recall that preemption is not allowed. When the construction of a
new schedule starts, these jobs are initialized as charging at their lowest
possible rate. As soon as they are encountered in the priority order, this
rate is scaled up where possible. In this way, preemption is avoided, while
respecting the priority order as much as possible.
Note that in the parallel schedule generation scheme, we do not need to
generate a complete schedule, but just one that lasts until the next time a
schedule will be generated in our strategy. We stop the construction as soon as
it advances to a time point beyond that. This is not true for the serial scheme,
as a lower priority job may still cause changes early in the schedule.

3.2

Priority rules

A schedule generation scheme uses a priority rule to assign a priority to each
job. A priority rule essentially is a formula that assigns a numerical value to a
job, that can be used to order them. Typically, jobs with a smaller value for
the priority rule’s formula have a higher priority. Many possible priority rules
exist, but we will only list the ones that will be used in the remainder of this
work:
FCFS First Come First Serve: rj .
EDD Earliest Due Date: dj .
ELSTu Updated Earliest Latest Starting Time: dj − Ej′ /Pj+ .
where Ej′ is the remaining charging volume, i.e. the original charging volume
Ej minus the amount charged up to the time of evaluation.

7

3.3

Destroy-and-repair

The single-pass schedule generation schemes described in Section 3.1 generate
reasonably good schedules. We want to investigate, however, if we can improve
them further by using an iterative heuristic.
Essentially, our approach boils down to a destroy-and-repair heuristic. We
remove parts of the schedule and replace them by parts that are generated using
a different priority rule. We repeat this a limited number of times to obtain an
improved schedule.
Algorithm 1 Global overview of the destroy-and-repair procedure. J is the set
of available jobs (of size n), t is the current time.
1: S ∗ ← InitialSchedule(J, PRIO1) ▷ Generate initial schedule with a parallel

or serial schedule generation scheme using the first priority rule
2: fails ← 0
3: while fails < f do

S ← S∗
J′ ← ∅
for iter ∈ {1, ..., r · n} do
▷ Randomly remove r · n jobs
j ← GetRandomJob(S)
J ′ ← J ′ ∪ {j}
S ← RemoveFromSchedule(S, j)
10:
end for
11:
for iter ∈ {r · n, ..., s · n} do
▷ Further removal based on adjacency
12:
j ← GetWeightedRandomJob(S)
13:
J ′ ← J ′ ∪ {j}
14:
S ← RemoveFromSchedule(S, j)
15:
end for
16:
for j ∈ J ′ : Sj < t do ▷ Reinsert already started jobs at minimum rate
17:
S ← ScheduleAtMinRate(S, j)
18:
end for
19:
for j ∈ SortBy(J ′ , PRIO2) do ▷ Reinsert (or adjust) jobs in order of
the second priority rule
20:
S ← AddToSchedule(S, j)
21:
end for
22:
if Score(S) < Score(S ∗ ) + imin then
▷ Above some minimum
improvement threshold imin , we count a success
23:
fails ← fails + 1
24:
else
25:
fails ← 0
26:
end if
27:
if Score(S) > Score(S ∗ ) then
▷ Keep the best result
28:
S∗ ← S
29:
end if
30: end whilereturn S ∗
4:
5:
6:
7:
8:
9:

A global overview of the procedure is given in Algorithm 1. From the initial
schedule, we remove a fraction s of jobs. First a fraction r < s is removed
randomly with uniform probability. For the remaining fraction s − r, jobs are
removed with a probability proportional to their weight. The weight is defined
8

as the number of jobs adjacent to the job in the original schedule that have
already been removed. In this way, the removal procedure aims to create some
large contiguous open areas in the schedule, rather than many small holes. For
two jobs to be considered adjacent, two conditions must be met: (1) part of
their processing windows must overlap or immediately follow each other, and
(2) they must be scheduled on two parking lots that compete for resources (i.e.
parking lots that share at least one cable along the path to the root node).
We start the repair phase by reinserting jobs that have a start time Sj before
the start of the schedule, i.e. jobs that are already being processed, to avoid
preemption. These are initially scheduled at the lowest possible rate. Then, we
reinsert (or adjust) all jobs, ordering them using a different priority rule than
the one used to generate the initial schedule.
The resulting schedule is compared to the best schedule we have seen so far.
If it is better, we continue the procedure with the new schedule. If it is better
by at least a minimum improvement imin , we say the procedure was successful.
If the procedure was not successful a number of f consecutive times, we stop.

3.4

Scheduling frequency

We consider an online problem. This means that new information regularly
becomes available, either when the solar output is updated, or when a new EV
arrives at a parking lot. The most naive way to deal with this is to generate a new
schedule any time new information is revealed. However, since we use a rather
advanced scheduling algorithm, it is reasonable to generate a new schedule less
often. Therefore, we trigger the generation of a new schedule on a periodic
basis, e.g. every hour. Within an interval, no new schedules are generated,
unless a high-priority EV arrives. A high-priority EV is defined as an EV that
has a higher priority value (for the first priority rule) than 80% of the EVs in the
schedule at that time. If such an EV arrives, an additional schedule is generated
at its time of arrival. It does not change the timing of the next periodic schedule
generation, however.

4

Computational results

We have implemented a discrete-event simulation to evaluate our approach. A
brief description of the simulation is presented in Appendix A.
For the test runs reported below, average results over five runs are presented, each with a fixed seed used to generate the instance. Each individual
run contains nine days of simulated time, the first two of which are treated as a
warm-up period. This means that all reported results (except the runtime) are
over days 3-9. The simulator was written in the Python programming language.
The processor of the system used to run the tests on was an Intel(R) Xeon(R)
Gold 6130 CPU @ 2.10GHz.
The main performance metric of an approach is the resulting average delay,
or the average tardiness, of an EV that is charged at one of the parking lots in
the simulation. The other metrics that we will report on are maximum delay,
i.e. the largest delay a single EV encounters in the simulation, the fraction of
EVs that is delayed as a percentage of the total number of EVs that parked at
one of the parking lots, and the number of EVs that suffered a delay of more

9

than fifteen minutes. We present the number of EVs with a large delay rather
than a percentage, as we feel that the number of EVs that experience a large
delay is a relevant metric, even if the percentage is small.
In the remainder of this section, we first discuss the selected approaches and
parameter settings in 4.1. We continue with an analysis of the effects of considering elements of the grid topology (Section 4.2) and flexible charging rates
(Section 4.3). Then we will show the performance of the developed approaches
on different scheduling intervals in Section 4.4. We conclude this section with a
comparison of the most promising approaches in Section 4.5.

4.1

Approach selection and parameter settings

Based on their performance in initial test runs, we selected five variants that we
will use in our evaluation:
FCFS is a serial schedule generation scheme, using the First Come First Serve
priority rule.
S generates schedules using a serial schedule generation scheme, where the
planned departure of an e-vehicle is used as the priority (Earliest Due
Date/EDD).
P generates schedules using a parallel schedule generation scheme, where the
planned departure of an e-vehicle is used as the priority (Earliest Due
Date/EDD).
SR generates initial schedules using a serial schedule generation scheme, where
the planned departure of an e-vehicle is used as the priority (Earliest Due
Date/EDD). Improvements are generated using the destroy-and-repair
heuristic described in Section 3.3 with the Updated Earliest Latest Starting Time (ELSTu) priority rule.
PR generates initial schedules using a parallel schedule generation scheme,
where the planned departure of an e-vehicle is used as the priority (Earliest Due Date/EDD). Improvements are generated using the destroy-andrepair heuristic described in Section 3.3 with the Updated Earliest Latest
Starting Time (ELSTu) priority rule.
For the latter two, the values of the relevant parameters are as follows:
• Rescheduling fraction s = 0.5;
• Random removal fraction r = 0.05;
• Improvement threshold imin = 100;
• Unsuccessful iteration tolerance f = 4.
Other variants of the approaches have been tested, using different (combinations) of priority rules, parameter settings, and adjacency measures (in case
of weighted removal). The presented approaches and settings (except ‘FCFS’)
were chosen as they showed the most consistent good performance in the preliminary tests. Apart from these four main approaches, we also present results
from ‘FCFS’ when relevant.
10

Transformer

P1
440
1.00

400

Figure 2: Copperplate layout
Metric

S

P

SR

PR

Grid

Max. delay (s)
Avg. delay (s)
EVs delayed (%)
Delay ≥ 15 min

14236.27
121.19
1.75
65.20

13882.98
106.03
1.48
58.00

5033.37
88.14
1.47
52.60

4847.46
86.56
1.54
55.40

No Grid

Max. delay (s)
Avg. delay (s)
EVs delayed (%)
Delay ≥ 15 min

36.41
0.01
0.00
0.00

0.00
0.00
0.00
0.00

36.41
0.01
0.00
0.00

10.40
0.00
0.00
0.00

Table 1: Comparison of results taking the network layout into account and those
ignoring the grid

4.2

Network constraints

Where limitations exist in the transport capacity of the underlying electricity
network, it is important to take these into account when planning electricity
usage. To show the effects of ignoring the grid layout, we have implemented a
scenario that does so (see Figure 2). This network consists of a single parking
lot, with as many parking spots and solar panels as the seven parking lots in
our original grid combined. The results of running our four main approaches on
both grids are shown in Table 1.
We observe that delays almost disappear when we take away the grid layout. This indicates that the simplification of ignoring the grid layout gives a
significant and unrealistic advantage in the scheduling model. This difference
justifies the additional modeling effort required to account for the topology of
the network.

4.3

Flexible charging rates

The assumption that using the flexibility in rates that charging of EV batteries
may allow would be beneficial, is crucial for our model. To test this assumption,
we compared simulations with the flexible rates as we have described them so
far, to simulations with a fixed rate of 9 kW for all EVs. The value of 9 kW was
chosen, as this is the average upper bound in the flexible scenario, meaning that
the average potential for energy consumption is equal across both scenarios.
Additionally, we excluded the solar panels from this simulation. EVs cannot
scale down in the fixed rate scenario and their charging is not allowed to be
preempted. Because of this, using the power from solar panels in the schedule
means that the cable capacity may be violated if the amount of power they
provide changes. To make the comparison as fair as possible, therefore, the
solar panels are turned off. Note the absence of solar power causes markedly
11

Metric

FCFS

S

P

SR

PR

Max. delay (s)
Avg. delay (s)
EVs delayed (%)
Delay ≥ 15 min

68148.35 54599.73 54561.94 53366.20 56653.89
15142.88 14899.12 14894.50 15055.51 15103.98
61.30
85.83
85.89
85.83
85.01
2106.40 2950.80 2954.40 2958.80 2911.20

Max. delay (s)
Avg. delay (s)
Flexible
EVs delayed (%)
Delay ≥ 15 min

66068.74 62563.74 59144.77 61743.67 60528.36
14131.81 14600.97 14486.47 14327.40 14418.19
59.02
82.34
83.25
81.61
83.86
2055.60 2837.40 2870.60 2815.60 2886.60

Fixed

Table 2: Comparison of results for flexible and fixed rate charging
different results compared to e.g. Table 1, as less power is available for charging
overall. The results of these runs are presented in Table 2.
Here, we present the results of the ‘FCFS’ alongside our four main approaches, as it performs unexpectedly well in this scenario. It seems that planning according to the ‘first come first serve’ principle is fairly effective in a
strained network where all power flows from a single source.
We observe that the differences are not large, but the average delay is typically a few minutes shorter in the scenario with flexible charging rates. The
same is true for the amount of severe delays and the percentage of EVs that is
delayed.
Keep in mind that we excluded the solar panels from this comparison. Their
output can be incorporated safely in the scenario with flexible rates, whereas
it cannot be incorporated when using fixed charging rates without allowing
preemption. Therefore, one could say that flexible rates are very beneficial
when we want to use solar power. These results together show that the use of
flexible charging rates allows for better outcomes.

4.4

Scheduling frequency

In an online setting, regular updates of the schedule are performed. Each time
new information is revealed, the generation of a new schedule could be triggered. The results presented in the previous sections use this strategy, because
it provides the most clear environment for the comparison of elements of the
modeling. In practice, however, it is undesirable and unnecessary to generate new schedules that often, in particular for the more advanced scheduling
methods. Generating schedules less frequently is also more realistic in terms of
computation time, as new EVs arrive with high frequency during peak hours.
The more often a new schedule is generated, the better the results are expected to be. If the difference in quality is sufficiently small, however, it is
reasonable to update schedules with a lower frequency. We have tested three
scheduling frequencies:
1. Generate a new schedule whenever new information is revealed (i.e., when
the solar forecast is updated or a new EV arrives);
2. Generate a new schedule once every 15 minutes;

12

Metric

S

P

SR

PR

New information

Max. delay (s)
Avg. delay (s)
EVs delayed (%)
Delay ≥ 15 min
Runtime (s)

14236.27
121.19
1.75
65.20
20366.03

13882.98
106.03
1.48
58.00
12743.83

5033.37
88.14
1.47
52.60
70506.54

4847.46
86.56
1.54
55.40
40210.12

15 min.

Max. delay (s)
Avg. delay (s)
EVs delayed (%)
Delay ≥ 15 min
Runtime (s)

14706.39
123.94
1.75
65.20
8688.63

13167.38
115.11
1.63
58.00
7143.22

5293.81
106.39
1.73
52.60
27071.67

5237.77
95.23
1.60
55.40
15324.67

1 hour

Max. delay (s)
Avg. delay (s)
EVs delayed (%)
Delay ≥ 15 min
Runtime (s)

14889.79
127.69
1.77
65.20
7499.83

14027.18
103.22
1.47
58.00
7423.24

8399.59
136.22
1.94
52.60
19654.80

5135.09
96.95
1.61
55.40
14446.14

Table 3: Comparison of results for a number of scheduling intervals.
3. Generate a new schedule once every hour.
In the latter two cases, we keep track of the priority of newly arriving EVs,
according to the (first) priority rule used for scheduling. If an EV arrives with
a priority that is higher than 80% of the EVs that are currently scheduled, we
will trigger an additional schedule to be generated.
The results are presented in Table 3. Most approaches show a slight deterioration in the quality of the results when the scheduling frequency decreases.
Only the results for the parallel scheduling scheme (‘P’) are somewhat inconsistent with this observation. The performance of the ‘SR’ approach deteriorates
most of all.
We observe that the total runtime of the simulation is significantly reduced
for all approaches. Note that the reported runtime includes every aspect of
the simulation (not just the scheduling itself) for a total simulation time of nine
days. The runtime of all approaches is such that it is realistic to implement them
with a schedule generation interval of 15 minutes. In terms of the quality of
the schedules, we observe that the best performing (advanced) approach (‘PR’)
still outperforms the single-pass approaches on the main metric (average delay),
even with a large scheduling interval.

4.5

Overall performance

From the results in the previous sections, we observe that the parallel implementation of an approach seems to dominate the serial implementation of that
same approach. Based on the results of our preliminary tests, however, we must
say that this is not a general result. This is consistent with earlier findings by
e.g. Kolisch [10].
In this section we will give a final overview of the results. We present the best
performing single-pass approach and the best performing approach using our
13

Max. delay (s)
Avg. delay (s)
EVs delayed (%)
Delay ≥ 15 min
Runtime (s)

FCFS

P-EDD

PR-15min

31287.96
1114.21
11.72
470.20
16168.70

13882.98
106.03
1.48
58.00
12743.83

5237.77
95.23
1.60
55.40
15324.67

Table 4: Results for the most promising approaches
destroy-and-repair heuristic. We compare them to the ‘FCFS’ approach, which
we consider to be the most straight-forward application of scheduling using our
adapted schedule generation schemes. The best performing approaches are the
parallel schedule generation scheme using the Earliest Due Date (EDD) priority
rule, ‘P-EDD’, and the parallel ‘improved’ approach using the EDD and ELSTu
(Updated Earliest Latest Starting Time) priority rules, ‘PR-15min’. For the
latter approach, we use a scheduling interval of 15 minutes, while the other two
will continuously generate new schedules, any time new information is revealed.
The parallel ‘improved’ approach outperforms the other approaches on almost all metrics, while it is comparable in computational load. This seems to
be the most promising approach for our case study and similar scenarios.
Note that all approaches discussed above protect the network capacity and
apply scheduling techniques for charging decisions. We conclude with a note
on the effectiveness of scheduling in general. Therefore, we want to make a
comparison with a scenario where no control is exercised over the charging
at all. We ran simulations on the same network, under the same conditions,
where all EVs have a fixed charging rate of 9 kW. Rather than scheduling their
demand, any EV that arrives at a parking lot immediately starts charging, until
its battery is fully charged. In this scenario, we consider a 10% overload of
the cable capacity (i.e. a load of 200-220 kW) to be manageable. We consider
anything beyond 220 kW to be truly problematic. If we look at the two main
cables connecting the two groups of parking lots to the transformer, we find that
the cable on the left (connecting to P1, P2 and P3) suffers from a manageable
overload 4.4% of the time, and from a problematic overload 53.7% of the time.
The cable of the right (connecting to P4, P5, P6 and P7) has a manageable
overload 2.6% of the time, and a problematic overload 65.8% of the time. These
numbers indicate that it is absolutely necessary to manage the charging of EVs
on these parking lots, and show the usefulness and effectiveness of a scheduling
approach like ours.

5

Conclusions and future work

We have formulated an online scheduling problem dealing with the charging of
EVs. For this problem, we developed a scheduling approach that extends the
idea of schedule generation schemes to an online setting with flexible charging
jobs. In our case study, the application of schedules generated using this approach, allows for the serving of a large number of EVs with minimal delay,
while respecting the constraints imposed by the network. If no control over
the charging was exercised at all, cables in the network would be overloaded
14

around 60-70% of the time. Overload is completely avoided if our schedules
are followed, at the cost of an average delay of just over 1.5 minutes per EV
in a high-occupancy scenario. The quality of the generated schedules is such
that frequent updates are not necessary. Finally, the computational load of the
developed approach is reasonable for practical purposes, making it a promising
candidate for implementation in real-world cases.
In addition to this main result, our case study shows that it is essential to
take the network topology into account when deciding charging profiles. Furthermore, we have shown the benefits of considering a range of permissible
charging rates for EVs, rather than a single fixed value.
Many avenues for future research exist. Broadly, we see two main directions
for future research.
First, their are many opportunities for further development of the scheduling
approach. We have proposed a novel approach for generating schedules. Other
variants of this approach might be interesting. Examples include the use of
more than two priority rules in the improvement process and the application of
a more directed destroy-and-repair heuristic that aims to improve the schedule
at the points that cause the most delay.
Second, certain extensions of the model may be interesting to investigate.
For example, a more complex model could include the ability of EVs to discharge
as well (V2G), and contribute to the charging of other EVs with a higher priority.
A more detailed modeling of the uncertain power output of the solar panels can
be considered as well. Using a more detailed model of the power network (e.g.
an AC model) would be an interesting, but computationally heavy, extension.
Other objectives, such as cost minimization through consideration of electricity
prices, can also be investigated.

Acknowledgements
We would like to thank Philip de Bruin for providing the numbers for the simulation runs without any control or scheduling strategies, that we used in Section
4.5. We want to acknowledge the research program “Energie: Systeem Integratie en Big Data? with project number 647.003.005, which is financed by
the Dutch Research Council (NWO), for financing the machine used for the
computational experiments.

Declarations
Funding
No funding was received to assist with the preparation of this manuscript.

Competing interests
The authors have no competing interests to declare that are relevant to the
content of this article.

15

Data availability
The data used in this paper is provided in the form of tables in the appendix.

Code availability
The code used to generate the results presented in this paper is not available
publicly, as parts of it may be used for assignments in a course. Access to the
code can be requested from the corresponding author.

Author contributions
All authors contributed to the study conception and design. Coding and analysis
were performed by Emily van Huffelen under supervision of Marjan van den
Akker and Roel Brouwer. Further analysis was done by Roel Brouwer, who also
wrote the first draft of the manuscript. All authors commented on previous
versions of the manuscript. All authors read and approved the final manuscript.

Appendix A

Simulation model

We evaluated the developed scheduling approaches using a discrete-event simulation. We will briefly explain the simulation model using the event graph
displayed in Figure 3. Each box represents a type of event, where arcs between
events indicate that an event may schedule another. A dashed arc indicates that
the subsequent event happens instantaneously if it is triggered. The arcs labeled
with ‘(a)’ may or may not be present, depending on the scheduling approach
used (see Section 3). The simulation is run by repeatedly extracting the next
event from the event queue and executing its associated actions, until the end
simulation event is encountered.
We simulate the arrival, charging and departure of electric vehicles. The
charging is done according to the schedule we generate during the simulation,
using one of the approaches described in Section 3. The shaded boxes in Figure
3 indicate events that are contained in the schedule. A schedule is, in essence,
a series of provisional events of types EV changes charging rate and EV stops
charging. The inspect schedule event draws these events from the schedule and
enters them in the event queue. A brief description of each event is provided
below:
EV arrives happens when a new EV enters the simulation. This event handles
the selection of a parking lot (or removes the EV from the simulation if
all three parking lots from its preference are full). It schedules a planned
departure event for the EV at its due date dj and may schedule an immediate update schedule event, depending on the scheduling approach used.
Finally, it will schedule a EV arrives event for the next EV to arrive.
planned departure happens when an EV is supposed to leave, at the end of
its planned connection time. If the EV is fully charged, it will schedule an
immediate EV leaves event.
EV leaves happens when an EV actually leaves. This means that it leaves its
parking lot and is removed from the simulation.
16

EV arrives

planned
departure

EV leaves

EV stops
charging

EV starts
charging
or changes
charging rate

(a)

(a)

apply
scheduling
approach
to update
schedule

solar power
update

(a)

inspect
schedule

Figure 3: Event graph showing the relations between events in our simulation
model
EV starts charging or changes charging rate happens when an EV starts
charging for the first time, or changes its charging rate later on. It updates
all relevant values and rates, but schedules no additional events. This
event is dictated by the schedule.
EV stops charging happens when an EV stops charging, i.e. it has received
its requested charging volume Ej . It updates all relevant values and rates.
If the due date dj of the EV has already passed, it will schedule an immediate car leaves event. Depending on the scheduling approach used, it
may also trigger an immediate update schedule event.
solar power update is a regularly scheduled event, that happens on a given
interval: every hour of simulated time. This event retrieves the (expected)
power produced by the solar panels installed for the upcoming interval, and
updates the available power at each parking lot accordingly. It will trigger
an immediate update schedule event. Finally, it will schedule another
regular forecast update event at the end of the current forecast interval.
apply scheduling approach to update schedule happens when the schedule needs to be updated. A new schedule is generated using the relevant
scheduling approach. It schedules an inspect schedule event at the time of
occurrence of the first action in the generated schedule. Additionally, if
17

schedules are updated on an interval different from the regular forecast update, it schedules another update schedule event at the end of the current
scheduling interval.
inspect schedule will retrieve the next event from the schedule (either a EV
changes charging rate event or a EV stops charging event) and, if it happens at the current time, schedules the corresponding event. It will then
schedule an inspect schedule event at the (planned) time of occurrence of
the following event in the schedule.
At the start of the simulation, three events are scheduled:
1. ‘regular forecast update’ at time 0;
2. ‘car arrives’ at the first generated arrival time;
3. ‘end simulation’ at the end of the period of time we intend to simulate.
These correspond to the three arcs that do not originate at an event box in
Figure 3.

Appendix B
B.1

Distributions

Solar power

The power that a solar panel produces strongly depends on the time of day. In
Table 5, we list the average production of solar panels as a fraction of their peak
power. These will be used to determine the mean of the distribution (with a
standard deviation of 15%) from which the actual values are drawn during the
simulation. The values are based on a forecast of the production of solar panels
during the summer months in the Netherlands in 2025 [6].
Hour

Fraction

Hour

Fraction

Hour

Fraction

0
1
2
3
4
5
6
7

0.000000000
0.000000000
0.000000000
0.001548952
0.017126799
0.055567520
0.132034210
0.222931250

8
9
10
11
12
13
14
15

0.311153080
0.382618250
0.426692930
0.446001000
0.440104200
0.403637380
0.342447800
0.261458840

16
17
18
19
20
21
22
23

0.169520680
0.083306720
0.026936987
0.005260382
0.000000000
0.000000000
0.000000000
0.000000000

Table 5: Average solar panel revenues as a fraction of peak power

B.2

Arrival of EVs

EVs arrive in the simulation according to a Poisson process. The (average)
arrival rates for every hour of the day as a fraction of the total daily arrivals are
listed in Table 6.

18

B.3

Charging rates

Each EV has a minimum and maximum charging rate (kW), drawn with uniform
probability from the combinations listed in Table 7.

B.4

Charging volumes

Each EV has a demand for a given amount of energy to be added to its battery
over the duration of its connection. These are distributed in the range of 0 to
102 kWh according to the fractions given in Table 8. These fractions represent
the probability of the charging volume to be drawn from that particular range.
Within each group, values are distributed uniformly.

B.5

Connection times

Each EV has an intended time of departure, effectively a due date for the
charging to be complete. This is determined by adding a connection time (in
hours, distributed as in Table 9) to the arrival time. These fractions represent
the probability of the connection time to be drawn from that particular range.
Within each group, values are distributed uniformly.

References
[1]

Syed Muhammad Arif et al. “Review of electric vehicle technologies, charging methods, standards and optimization techniques”. In: Electronics 10.16
(2021). doi: 10.3390/electronics10161910.

[2]

Nico Brinkel, Tarek AlSkaif, and Wilfried van Sark. “The impact of transitioning to shared electric vehicles on grid congestion and management”.
In: Proceeding of the 2020 International Conference on Smart Energy Systems and Technologies (SEST). 2020, pp. 1–6. doi: 10.1109/SEST48500.
2020.9203241.

[3]

Roelof Jacob Jan Brouwer, J M van den Akker, and J A Hoogeveen.
“A hybrid optimization framework for the general continuous energyconstrained scheduling problem”. arXiv. 2024.

[4]

Zhi Chen et al. “Efficient priority rules for the stochastic resource-constrained
project scheduling problem”. In: European Journal of Operational Research 270.3 (2018), pp. 957–967. doi: 10.1016/j.ejor.2018.04.025.

[5]

Mateja Dumić and Domagoj Jakobović. “Ensembles of priority rules for
resource constrained project scheduling problem”. In: Applied Soft Computing 110 (2021). doi: 10.1016/j.asoc.2021.107606.

[6]

ENTSO-E. Mid-term adequacy forecast 2018. 2018. url: https://www.
entsoe.eu/outlooks/midterm/.

[7]

Sönke Hartmann and Dirk Briskorn. “A survey of variants and extensions of the resource-constrained project scheduling problem”. In: European Journal of Operational Research 207 (1 2010), pp. 1–14. doi: 10.
1016/j.ejor.2009.11.005.

19

[8]

Sönke Hartmann and Dirk Briskorn. “An updated survey of variants and
extensions of the resource-constrained project scheduling problem”. In:
European Journal of Operational Research 297 (1 2022), pp. 1–14. doi:
10.1016/j.ejor.2021.05.004.

[9]

Muhammad Tayyab Hussain et al. “Optimal management strategies to
solve issues of grid having Electric Vehicles (EV): a review”. In: Journal
of Energy Storage 33 (2021), pp. 102–114. doi: 10.1016/j.est.2020.
102114.

[10]

Rainer Kolisch. “Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation”. In: European Journal
of Operational Research 90.2 (1996), pp. 320–333. doi: 10.1016/03772217(95)00357-6.

[11]

Mingming Liu et al. “Residential electrical vehicle charging strategies: the
good, the bad and the ugly”. In: Journal of Modern Power Systems and
Clean Energy 3.2 (2015), pp. 190–202. doi: 10.1007/s40565-015-01222.

[12]

Antonio Lova, Pilar Tormos, and Federico Barber. “Multi-mode resource
constrained project scheduling: scheduling schemes, priority rules and
mode selection rules”. In: Inteligencia Artificial 10.30 (2006), pp. 69–86.
doi: 10.4114/ia.v10i30.947.

[13]

Anulark Naber. “Resource-constrained project scheduling with flexible resource profiles in continuous time”. In: Computers and Operations Research 84 (2017), pp. 33–45. doi: 10.1016/j.cor.2017.02.018.

[14]

Ali Saadon Al-Ogaili et al. “Review on scheduling, clustering, and forecasting strategies for controlling electric vehicle charging: challenges and
recommendations”. In: IEEE Access 7 (2019), pp. 128353–128371. doi:
10.1109/ACCESS.2019.2939595.

[15]

J M van den Akker and J I Posthoorn. “Simulation assignment Optimization for Sustainability (INFOMOFS): Smart charging in Polderwijk”.
2021. url: https : / / osiris - student . uu . nl / onderwijscatalogus /
extern/cursus?cursuscode=INFOMOFS&taal=en&collegejaar=2020.

[16]

Emily van Huffelen. “Scheduling of flexible EV charging under grid constraints and uncertainty”. MA thesis. Utrecht University, 2023. doi: 20.
500.12932/45597.

[17]

Qinglong Wang et al. “Smart charging for electric vehicles: a survey from
the algorithmic perspective”. In: IEEE Communications Surveys & Tutorials 18.2 (2016), pp. 1500–1517. doi: 10.1109/COMST.2016.2518628.

20

Hour

Fraction

Hour

Fraction

Hour

Fraction

0
1
2
3
4
5
6
7

0.012926435
0.004938874
0.002042621
0.001188988
0.000304869
0.000518277
0.007560745
0.027072345

8
9
10
11
12
13
14
15

0.058748209
0.049114356
0.035456236
0.040120728
0.045181549
0.048108289
0.050913082
0.057254352

16
17
18
19
20
21
22
23

0.072223408
0.103899271
0.125453492
0.071156367
0.056217798
0.052467913
0.047315631
0.029816164

Table 6: Average fraction of arrivals at each hour

Min.

Max.

Probability

Min.

Max.

Probability

3
3
3
3
4
4
4
4

6
7
8
9
7
8
9
10

0.0625
0.0625
0.0625
0.0625
0.0625
0.0625
0.0625
0.0625

5
5
5
5
6
6
6
6

8
9
10
11
9
10
11
12

0.0625
0.0625
0.0625
0.0625
0.0625
0.0625
0.0625
0.0625

Table 7: Distribution of charging rates

21

kWh

Weight

kWh

Weight

kWh

Weight

0-1
1-2
2-3
3-4
4-5
5-6
6-7
7-8
8-9
9-10
10-11
11-12
12-13
13-14
14-15
15-16
16-17
17-18
18-19
19-20
20-21
21-22
22-23
23-24
24-25
25-26
26-27
27-28
28-29
29-30
30-31
31-32
32-33
33-34

0.029938112
0.026188226
0.035212341
0.032681930
0.043443797
0.050333831
0.071186854
0.055973903
0.048809488
0.032163654
0.021188378
0.023383433
0.020670102
0.019725008
0.018688455
0.018261638
0.018048230
0.017347032
0.017286058
0.018718941
0.018078717
0.018901863
0.017286058
0.017316545
0.017103137
0.016615347
0.014511753
0.015487333
0.014938569
0.013200817
0.011859395
0.013322765
0.010853328
0.011127710

34-35
35-36
36-37
37-38
38-39
39-40
40-41
41-42
42-43
43-44
44-45
45-46
46-47
47-48
48-49
49-50
50-51
51-52
52-53
53-54
54-55
55-56
56-57
57-58
58-59
59-60
60-61
61-62
62-63
63-64
64-65
65-66
66-67
67-68

0.009603366
0.008444864
0.008292430
0.008079022
0.006585165
0.007042468
0.006920521
0.006676626
0.006219323
0.005762019
0.005822993
0.005487638
0.005640072
0.005883967
0.005121795
0.004115728
0.004115728
0.004268163
0.003871833
0.004786439
0.003810859
0.003262096
0.003384043
0.003445017
0.003201122
0.002804793
0.002987714
0.002957227
0.002317003
0.002073108
0.002256029
0.001981647
0.001585318
0.001615804

68-69
69-70
70-71
71-72
72-73
73-74
74-75
75-76
76-77
77-78
78-79
79-80
80-81
81-82
82-83
83-84
84-85
85-86
86-87
87-88
88-89
89-90
90-91
91-92
92-93
93-94
94-95
95-96
96-97
97-98
98-99
99-100
100-101
101-202

0.001249962
0.001128014
0.000640224
0.000853633
0.000518277
0.000731685
0.000518277
0.000762172
0.000579251
0.000396329
0.000396329
0.000182921
0.000182921
0.000091500
0.000091500
0.000091500
0.000274382
0.000243895
0.000152434
0.000182921
0.000182921
0.000182921
0.000030500
0.000000000
0.000000000
0.000030500
0.000000000
0.000000000
0.000000000
0.000000000
0.000000000
0.000000000
0.000000000
0.000030500

Table 8: Distribution of charging volumes of EVs

22

Hours

Weight

Hours

Weight

Hours

Weight

0-1
1-2
2-3
3-4
4-5
5-6
6-7
7-8
8-9
9-10
10-11
11-12
12-13
13-14
14-15
15-16
16-17
17-18
18-19
19-20
20-21
21-22
22-23
23-24

0.075089174
0.089052163
0.084570592
0.069967379
0.053565440
0.036309869
0.025608975
0.028200360
0.041492637
0.037559830
0.037072040
0.040699979
0.046431511
0.055242218
0.049205817
0.034511143
0.026828450
0.022590775
0.019237218
0.016737295
0.013261791
0.010426511
0.008536325
0.006707113

24-25
25-26
26-27
27-28
28-29
29-30
30-31
31-32
32-33
33-34
34-35
35-36
36-37
37-38
38-39
39-40
40-41
41-42
42-43
43-44
44-45
45-46
46-47
47-48

0.005518124
0.004237676
0.002926740
0.001859699
0.001524344
0.001128014
0.000579251
0.000914606
0.001280449
0.001249962
0.001341423
0.001920673
0.002256029
0.003231609
0.003536478
0.002804793
0.002408463
0.002865766
0.001890186
0.002286516
0.001890186
0.001310936
0.001432883
0.001341423

48-49
49-50
50-51
51-52
52-53
53-54
54-55
55-56
56-57
57-58
58-59
59-60
60-61
61-62
62-63
63-64
64-65
65-66
66-67
67-68
68-69
69-70
70-71

0.000945093
0.000548764
0.000518277
0.000274382
0.000121948
0.000152434
0.000426816
0.000243895
0.000213408
0.000457303
0.000396329
0.000274382
0.000670711
0.000945093
0.000792659
0.000884119
0.000853633
0.000640224
0.000396329
0.000609738
0.000548764
0.000457303
0.007987561

Table 9: Distribution of connection times

23
