# Complexity analysis for the EVCSP with active charger Constraints

Arthur Mazeyrat, Ammar Oulamara, Tifenn Rault, Ameur Soukhal

► To cite this version:

Arthur Mazeyrat, Ammar Oulamara, Tifenn Rault, Ameur Soukhal. Complexity analysis for the EVCSP with active charger Constraints. PMS2026, LAAS-CNRS, Toulouse, France, Apr 2026, Toulouse, France. hal-05414651

HAL Id: hal-05414651

https://hal.science/hal-05414651v1

Submitted on 13 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Complexity analysis for the EVCSP with active charger Constraints

Arthur Mazeyrat¹, Ammar Oulamara², Tifenn Rault¹ and Ameur Soukhal¹

¹ University of Tours, LIFAT EA 6300, 64 avenue Jean Portalis, 37200 Tours, France
athur.mazeyrat@etu.univ-tours.fr
tifenn.rault,ameur.soukhal@univ-tours.fr

² University of Lorraine, LORIA - UMR 7503, Campus Scientifique - BP 239, 54506 Vandoeuvre-les-Nancy, France
ammar.oulamara@loria.fr

**Keywords:** Scheduling, Electric Vehicles, Complexity, Heuristic.

## 1 Introduction

The Electric Vehicle Charging Scheduling Problem (EVCSP) can be stated as follows: we consider a charging station with $m$ identical chargers, each delivering a power $w$, and a global grid capacity $w_G$ that limits the total power that can be supplied simultaneously by all chargers. Each electric vehicle (EV) charging request is represented by an interval $[r_i, d_i]$, where $r_i$ is the EV arrival time and $d_i$ its departure time, together with a required energy $e_i$ expressed as charging duration $p_i = \frac{e_i}{w}$. The objective is to maximize the number of accepted charging requests. This problem is known to be NP-hard (Zaidi et al. 2022) when several chargers may be activated simultaneously. However, the complexity of the special case in which at most one charger can be activated at any time remains open (Zaidi et al. 2022), i.e. $w \le w_G < 2w$.

When at most one charger can be activated at each time, we study both cases: the case where the number $m$ of chargers is a part of the instance and the case with fixed $m$. The charging may be preemptive and we also suppose that any charged vehicle occupies a charger during its whole interval.

We prove that this problem is NP-hard via a reduction to the Equal-Size Partition Problem (ESPP). We also provided an algorithm for the case where the number of chargers $m$ may vary over time but never exceeds a given fixed $m$. Finally, we develop an heuristic to solve the NP-hard version, achieving excellent results.

Using Grahams three-field notation (Graham et al. 1979), the problem $1 \mid pmtn, r \mid \sum U$ is very close to ours, except that it does not incorporate active charger constraints. For this case, polynomial-time algorithms are known: Lawler's algorithm of complexity $O(n^5)$ (Lawler 1990), Baptiste's improvement to $O(n^4)$ (Baptiste 1999), and Vakhania's $O(n^3 \log n)$ algorithm (Vakhania 2009).

## 2 NP-hardness of the EVCSP with active charger constraints

We show that the problem EVCSP when the number $m$ of chargers is a part of the instance and at most one charger can be activated at each time is NP-hard. The proof is given by reduction from the Equal-Size Partition Problem.

### Equal-Size Partition Problem (ESPP):

Given a set $I$ of $2n$ distinct integers $a_i$, $i = 1, \dots, 2n$, and an integer $B$ where $\sum_i a_i = 2B$. The ESPP consists in finding a partition of $I$ into two subsets $I_1$ and $I_2$, such that: $|I| = |I_1 \cup I_2|$, $|I_1| = |I_2| = n$ and $\sum_{i \in I_1} a_i = B$. This problem is NP-hard (Garey & Johnson 1979).
Reduction to EVCSP:

We now reduce any instance of ESPP to an instance of EVCSP. Given an instance $I$ of ESPP, we build an instance $I'$ of EVCSP consisting in $4n$ charging requests defined in Table 1. A visual representation of a typical instance for $2n = 10$ is shown in Figure 1. We fix the number of chargers to $m = n$.

<table><caption>**Table 1.** Instance of EVCSP</caption><thead><tr><th>∀i ∈ [1, 2n]</th><th>L-jobs</th><th>R-jobs</th></tr></thead><tbody><tr><td>r<sub>i</sub></td><td>0</td><td>(n + 1)B + n - i</td></tr><tr><td>d<sub>i</sub></td><td>(n + 1)B + n - i</td><td>(n + 1)B + (n + 1)<sup>2</sup>B</td></tr><tr><td>p<sub>i</sub></td><td>(n + 1)a<sub>i</sub></td><td><sup>2(n+1)B</sup>&frasl;<sub>n</sub> - (n + 1)a<sub>i</sub> + (n + 1)B</td></tr></tbody></table>

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Instance of EVCSP for $2n = 10$</figcaption></figure>

Key Properties

* Any feasible EVCSP solution selecting $2n$ requests must pick exactly $n$ requests in the L-jobs part and $n$ requests in the R-jobs part due to the number of chargers.

* Any Equal-Size Partition $I_1, I_2$ yields an optimal solution of our problem. In other words, if $a_i \in I_1$, then requests $i$ and $(i + 2n)$ in $I'$ are selected for charging.

* The sum of the selected L-jobs charging duration requests cannot exceed $(n + 1)B$, as all L-jobs charging duration are multiple of $(n + 1)$ and that $\epsilon_1 \le n - 1$.

* For similar reasons, the sum of charging duration of the selected R-jobs cannot exceed $(n + 1)^2 B$.

* There exists a perfect matching between L-jobs and R-jobs in any optimal solution, such that the matching is decreasing on the right side: each selected L-job $i$ is matched to a selected R-job $(j + 2n)$ with $j \le i$, $j \in [1, 2n]$.

* Thanks to such a decreasing perfect matching, we can prove that the sum of charging duration of selected L-jobs must be bigger than $(n + 1)B$.

* Thus, any optimal solution of EVCSP corresponds exactly to a valid Equal-Size Partition of $I$, and vice versa.

**Theorem 1.** The EVCSP with $m$ chargers, where $m$ is part of the instance, and at most one charger can be activated at each time is NP-hard.
### 3 EVCSP under a fixed number of identical chargers

In real life applications, the number of chargers is limited to a certain fixed $m$. Moreover, it may happen that some chargers are unavailable during a certain period of time. We can consider this version of the problem as having variable charger constraints over time horizon. If we define a function $f$ that gives for any time $t$ the number of available chargers, we then have that $f(t) \le m, \forall t$.

Using advanced techniques, we showed that this problem is polynomial in $n$ for any fixed $m$. Hence, we developed an algorithm to solve this problem.

### 4 Heuristic approach

We propose to first select subsets of vehicles that can always be affected to chargers since the single-charger EVCSP without charger constraints can be solved in polynomial time. Once such a subset is selected, the instance can be solved using any polynomial-time algorithm from the literature (Lawler 1990), (Baptiste 1999), (Vakhania 2009).

To this end, we associate a score with each vehicle. By denoting $\ell_j = d_j - r_j$ the length of request $j$, we define the score function $S$ as:

$$S(j) = -\ell_j p_j$$

We now construct an instance $I'$ by selecting the highest-score request and adding it to $I'$ if it can be scheduled with the current $I'$; otherwise, it is discarded.

### 5 Computational experiments

We generated random instances as follows. For any number $n$ of vehicles, we first generated $n$ release dates $r_j$ uniformly in $[0, T-1]$, $n$ due dates $d_j$ uniformly in $[r_j+1, T]$, and then generated a charging duration $p_j$ uniformly in $[1, d_j - r_j]$, with $T = 10000$. The number of chargers was set to $m = \frac{n}{5}$. For each $n \in \{50, 100, 200, 300\}$, 100 instances were generated. In addition, we generated 100 hard instances of size $n = 100$ using our reduction to the ESPP.

For a given instance $I$, let $f_I^*$ denote the optimal objective value and $f_I^A$ the objective value obtained by the heuristic, and the absolute gap $g_I^A = f_I^* - f_I^A$ (axis $x$ in Figure 2).

On the random instances (Figure 2), the heuristic consistently achieves near-optimal solutions, with performance improving as $n$ increases. In Table 2, we report the relative gaps.

<table><caption>**Table 2.** Relative gap of random instances</caption><thead><tr><th>n</th><th>50</th><th>100</th><th>200</th><th>300</th></tr></thead><tbody><tr><td>Relative gap (%)</td><td>1.8</td><td>0.2</td><td>0.06</td><td>0.0</td></tr></tbody></table>

On the hard instances with $n = 100$, while the optimal objective value is $f_I^* = 2n$, the heuristic consistently returns $f_I^A = 2n-1$, providing strong performance even in challenging cases.
<figure><img src="image_3.png" /><figcaption>Fig. 2. Gap of 100 random instances generated for $n = \{50, 100, 200, 300\}$</figcaption></figure>

# 6 Conclusion and Perspectives

We have proved that the EVCSP with one active charger constraints and $m$ chargers is NP-hard when $m$ is part of the instance. In contrast, when $m$ is fixed, the problem can be solved in polynomial time, and we provided an algorithm for this case.

For the general case, we developed an efficient heuristic that achieves excellent results while remaining polynomial, with complexity $O(n^3 \log n)$ using Vakhania's algorithm (Vakhania 2009).

It would be interesting to adapt the heuristic to handle the *locality* of any request. It would also be interesting to investigate whether the proposed heuristic can be formally characterized as an approximation algorithm for the studied problem.

# Acknowledgements

We would like to thank the Région Centre-Val de Loire for its support.

# References

* Baptiste, P. (1999), “An $O(n^4)$ algorithm for preemptive scheduling of a single machine to minimize the number of late jobs”, *Discrete Applied Mathematics*, 24, pp. 175–180.

* Garey, M.R. and Johnson, D.S. (1979), *Computers and Intractability: A Guide to the Theory of NP-Completeness*, W. H. Freeman, San Francisco.

* Graham, R.L., Lawler, E.L., Lenstra, J.K. and Rinnooy Kan, A.H.G. (1979), “Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey”, *In: Hammer, P.L., Johnson, E.L. and Korte, B.H. (eds.), Discrete Optimization II*, Annals of Discrete Mathematics, vol. 5, Elsevier, pp. 287–326.

* Lawler, E.L. (1990), “A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs”, *Annals of Operations Research*, 26, pp. 125–133.

* Vakhania, N. (2009), “Scheduling jobs with release times preemptively on a single machine to minimize the number of late jobs”, *Operations Research Letters*, 37, pp. 405–410.

* Zaidi, I., Oulamara, A., Idoumghar, L. and Basset, M. (2022), “Maximizing the number of satisfied charging demands of electric vehicles on identical chargers”, *Omega*, 127, pp. 103–106.