# Scheduling electric vehicle regular charging tasks: A review of deterministic models

Alexandre Dolgui, Sergey Kovalev, Mikhail Kovalyov

► To cite this version:

Alexandre Dolgui, Sergey Kovalev, Mikhail Kovalyov. Scheduling electric vehicle regular charg-
ing tasks: A review of deterministic models. European Journal of Operational Research, 2024,
10.1016/j.ejor.2024.11.044. hal-04925485

HAL Id: hal-04925485

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

Submitted on 21 Feb 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>
<figure><img src="image_2.png" /></figure>

Invited review

# Scheduling electric vehicle regular charging tasks: A review of deterministic models

Alexandre Dolgui<sup>a, ∗</sup>, Sergey Kovalev<sup>b, c</sup>,<sup>∗</sup>, Mikhail Y. Kovalyov<sup>c</sup>

ARTICLE INFO

Keywords:

Charging scheduling

Parallel machine scheduling

Electric vehicle operations

Time windows

A B S T R A C T

We formulate a fairly general deterministic problem of scheduling electric vehicle (EV) regular charging tasks on parallel chargers over time. Charging task is called regular if it is performed at the same time and in the same place. The charging time and place can be fixed or selectable. The scheduling decision time range can be an interval or a circle. Charging tasks may or may not be preemptive. Each charging preemption may imply a setup time and a cost. Each task requires a given amount of energy to be received from the chargers. This energy determines the charging time requirement. The chargers consume electric power which can be limited from above. The objective is to minimize the cost of the chargers and their locations, received energy, maximum power and setups, or a function of task completion times. The problem is typical for urban electric buses with fixed timetables and charging points at depots or along the route. It can also be a part of a more general EV routing and charging scheduling problem, which is often decomposed into the routing and charging scheduling parts in order to reduce computational complexity. Various special cases of this problem have been studied in the literature, in the theoretical and practical contexts. We review and analyze these special cases using traditional scheduling terminology, thereby creating a bridge between theoretical machine scheduling and practical charging scheduling research.

# 1. Introduction and general problem setting

The demand for charging electric vehicles (EVs) permanently increases in the last years. The EV charging devices (chargers) are expensive equipment with significant space requirements, and charging processes contribute significantly to the power load of electrical networks. The efficient usage of vehicle chargers and optimal scheduling of charging processes can reduce the number of chargers and energy cost, make charging service more convenient for transport workers and passengers, and decrease peak power loads of electrical networks.

This review is inspired by the results of the project “Planning Process and Tool for Step-by-Step Conversion of the Conventional or Mixed Bus Fleet to a 100% Electric Bus Fleet” (PLATON) of the Electric Mobility Europe initiative (https://service.ifak.eu/PLATON-Web/home.html). The public transport operators involved in this project are faced with the challenge of efficiently using charging equipment and electricity for on-board battery electric buses operating on a fixed timetable. This challenge reduces to the parallel machine scheduling problem discussed in this review.

Public transport operators usually own electric buses and charging equipment. They possess all the data to make appropriate routing and

charging scheduling decisions. The real charging scheduling decisions for city public electric transport mainly follow the first-come, first-served rule, and the number of chargers at a charging station is simply determined by the maximum number of electric buses simultaneously present at the station between their trips. Recently, an increasing number of publications have appeared that provide deeper research into the modeling, optimization and algorithmic aspects of charging scheduling for city public electric buses and EVs in general.

Scheduling of EV charging tasks is often part of the studies on routing and charging scheduling of EVs. A popular approach to efficiently solving this combined problem is to decompose it into routing and charging scheduling sub-problems, such that a potential solution to the routing sub-problem provides input to the charging scheduling sub-problem, the solution of which is used to evaluate the combined decision.

We focus on deterministic problems that are adequate for the operation of city public electric buses according to fixed timetables, in which each bus travels along the same route each day or each shift and requires *regular* battery charging. We call battery charging regular

<footnote><sup>a</sup> IMT Atlantique, LS2N-CNRS, La Chanterie, 4, rue Alfred Kastler - B.P. 20722, F-44307 Nantes Cedex 3, France</footnote>

<footnote><sup>b</sup> INSEE - Omnes Education, 25, rue de l'Université, 69007 Lyon, France</footnote>

<footnote><sup>c</sup> United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova, 6, 220012 Minsk, Belarus</footnote>

<footnote>* Corresponding author.</footnote>

<footnote>E-mail addresses: alexandre.dolgui@imt-atlantique.fr (A. Dolgui), skovalev@inseec.com (S. Kovalev), kovalyov_my@newman.bas-net.by (M.Y. Kovalyov).</footnote>
if it occurs at the same time and in the same place. Other examples of regular charging include airport and intercity shuttles, schoolbuses, electric battery railcars (trains, tramways) and ferry boats. “Regular charging tasks” mentioned in the title of this article are opposed to “irregular charging tasks”, for which charging locations, times and power consumptions may vary.

In some routing and charging scheduling applications, a vehicle may need to take a detour to visit a charging station, which is called a deadheading. If a deadheading decision (to take a charging detour or not) needs to be made, then the corresponding charging task is obviously irregular. Kullman et al. (2021) consider irregular charging tasks with EV deadheading for charging. Their model includes a fixed sequence of stops to be visited by a single EV and a charging station between any two consecutive stops that can be visited or not. The only decision to make is whether to visit each charging station or not. In this article we do not study decisions of this kind.

In a two-stage decomposition approach to the EV routing and charging scheduling problem, the first stage allows for fixing not only the EV routes but also the actual charging locations. This ensures that the charging tasks in the second-stage sub-problem become regular, even if they were initially irregular in the original problem. Battaia et al. (2023) call the sequence of actual charging points for a bus route a charging scenario and enumerate these scenarios to solve the more general problem of designing electric bus services.

In reality, arrival and departure times and energy requirements of electric buses are subject to small uncertain variations. These variations can be compensated for by adopting a robustness approach, such as reducing charging time windows to guaranteed sizes and increasing energy requirements to maximum values. Recent reviews of uncertain, stochastic and queue-theoretic formulations of the charging scheduling problems are provided by Ji et al. (2023), Mahyari et al. (2023), Yan et al. (2023) and Lai and Li (2024). These problems mainly concern irregular charging of EVs of different owners at charging stations of different owners. We do not address problems of EV fleet composition, routing, and infrastructure design unless they relate to charging schedules. Recent results on such problems can be found, for example, in Mahmutoğulları and Yaman (2023), Su et al. (2023), Vichitkunakorn et al. (2024), Lera-Romero et al. (2024), Havre et al. (2024) and Park and Lee (2024).

A sufficiently general regular charging scheduling problem is formulated in the next section. We classify deterministic EV regular charging scheduling models based on their assumptions such as linear or circular time, prohibiting charging task preemptions or not, tightness of the charging time windows, cost structure, and energy and power constraints. In order to facilitate the classification, we use the traditional scheduling three-field notation $\alpha|\beta|\gamma$. It is described in Section 3. In the classical scheduling models, it is assumed that the time is linear, and operations cannot extend beyond the end of a given linear time interval. Models with linear time are reviewed in Sections 4 and 5 with the assumptions of no charging task preemptions and allowed preemptions, respectively.

We focus on computational complexity of the classical parallel machine scheduling problems with job release dates and deadlines, i.e., on NP-hardness or optimal polynomial time algorithms. Scheduling models with circular time are discussed in Section 6. Practical regular charging scheduling problems in Sections 4–6 are classified by means of the $\alpha|\beta|\gamma$ notation. For each initial, more general EV routing and charging scheduling problem, we specify whether the charging tasks are regular or not and whether deadheading decisions need to be made. Existing research trends, challenges and suggestions for future research are given in the last section.

## 2. General problem statement

In the classical scheduling terminology, the chargers can be viewed as parallel machines and the charging events (tasks) as jobs. There exist

numerous parallel machine scheduling models that can be appropriate for EV regular charging scheduling. We propose a review of charging scheduling models and relevant theoretical parallel machine scheduling models, which can provide new solution ideas for the public transport decision makers, and new practical motivations for the scheduling theorists. The common aspects of the reviewed models can be described in the traditional machine scheduling terminology as follows. We stress that these models are approximations of the real processes.

Jobs of a set $N = \{1, ..., n\}$ (EV regular charging tasks) have to be processed on parallel machines (chargers) of a set $M = \{1, ..., m\}$ installed in locations (charging stations) of a set $L$. The machine set $M$ is partitioned into subsets $M_q, q \in L$, such that machines of the same subset $M_q$ are installed in the same location. Each job $j$ and location $q$ are associated with a fixed time window $[r_{qj}, \bar{d}_{qj}]$, initial energy level $e_{qj}^0$, required energy level $e_{qj} \ge e_{qj}^0$ and concave charging functions $f_{ij}(\Delta)$ for chargers $i \in M_q$. In city electric bus routing and charging applications, the initial and required energy levels depend on the charging location due to the energy consumption when driving from a stop to a charging location and from a charging location to the next stop. Likewise, different travel times to different charging locations explain the dependence of time windows on charging locations.

The shape of the function $f_{ij}(\Delta)$ mainly depends of the charger's electric power and EV's battery. Times $r_{qj}$ and $\bar{d}_{qj}$ are called release date and deadline of job $j$, respectively, in location $q$. The value of $f_{ij}(\Delta)$, $i \in M_q$, is the amount of energy that is received by job $j$ with $e_{qj}^0 = 0$ from charger $i$ during charging time $\Delta$. By this definition, the processing (charging) time of job $j$ on charger $i$ from an energy level $e_j^{(1)}$ to an energy level $e_j^{(2)}$, so that $e_j^{(2)} > e_j^{(1)}$, is equal to $f_{ij}^{-1}(e_j^{(2)}) - f_{ij}^{-1}(e_j^{(1)})$, where $f_{ij}^{-1}(\cdot)$ denotes the inverse function of $f_{ij}$. It is assumed that the inverse functions exist. This assumption implies that there is no job with zero processing requirements in the problem input. Each job $j$ must be processed (EV must be charged from the initial level $e_{qj}^0$ to the required level $e_{qj}^0$) within one of its time windows $[r_{qj}, \bar{d}_{qj}]$ on one of the machines in a location $q \in L$.

The machines (chargers) differ by their processing (charging) speeds (velocities) $v_{ij}$ that may depend on the machine and the job. These speeds are relative to some, perhaps abstract, machine with unit speed, which we denote as $i^*$. If job $j$ is completely processed on a machine $i^* \in M_q$ with unit speed, then its processing time requirement on this machine is denoted as $p_{qj}$ and it is calculated as $p_{qj} = \int_{i^*}^{-1}(e_{qj}) - \int_{i^*}^{-1}(e_{qj}^0)$. If job $j$ is completely processed on an arbitrary machine $i \in M_q$, then its processing time requirement on this machine is denoted as $p_{qij}$ and it satisfies $p_{qij} = p_{qj}/v_{ij} = \int_{i^*}^{-1}(e_{qj}) - \int_{i^*}^{-1}(e_{qj}^0)$.

Preemptions of job processing (charging process) can be permitted or not. Irrespectively of the preemptions, all parts of the same job (EV charging task) must be performed in the same location (charging station), i.e., on machines of the same set $M_q, q \in L$. Each uninterrupted part of job $j$ on machine $i$ is preceded by a machine setup time $s_{ij}$, and it is associated with a cost $c_{ij}^{\text{set}}$. Setup times are non-anticipated, that is, they must start and complete inside one of the respective job time windows. Therefore, relations $\bar{d}_{qj} - r_{qj} \ge s_{ij}(q) + p_{ij}(q), j \in N$, must be satisfied for a machine $i(q) \in M_q$ with the maximal speed in each location $q \in L$. In the public EV charging applications, the setup time is needed for a current EV to leave the charger and for a new EV to approach the charger and connect to it. Typically, the first (post-processing) setup operation takes much less time and effort than the second (pre-processing) operation, which depends on the job (EV to be charged) and the machine (charger). Therefore, setup time $s_{ij}$ and cost $c_{ij}^{\text{set}}$ are assumed to be sequence independent (they do not depend on the job preceding job $j$). The setup cost can be associated with the workload dependent salary of the personnel that is responsible for vehicle movements in the charging location.

It is restrictively assumed that no job (EV battery) loses its energy during setup or downtime during which the battery is not charged for any reason. For a given job $j$, denote by $(I_1, ..., I_k)$ all its maximal
uninterrupted processing (charging) time intervals on machines of the same set $M_q, q \in L$, in a given schedule. Assume that the intervals occur on the machines $i_1, \dots, i_k$ in the increasing order of their start times. The machines can repeat in this sequence, i.e., an EV can be charged several times by the same charger during the same visit of a charging station. Denote by $\Delta_{q_{i_j}}, c_{q_{i_j}}^0$ and $e_{q_{i_j}}$ processing time (charging time duration), initial energy level and final energy level, respectively, of job $j$ in the interval $I_j, r = 1, \dots, k$. For each job $j$ and location $q$, it is required that $e_{q_{1j}}^0 = e_{q_j}^0, e_{q_{r-1j}} = e_{q_{rj}}^0, r = 2, 3, \dots, k, e_{q_{kj}} = e_{q_j}$, and $\sum_{r=1}^k \Delta_{q_{i_j}} v_{i_j} = p_{q_j}$, which means that $j$ is completely processed (feasibly charged) in $q$.

No job or setup can be performed by more than one machine simultaneously and no machine can perform more than one job or setup simultaneously. We call a machine that processes some job at a time $t$ as an *active machine* at this time. No machine is active during its setup or downtime. Each machine $i$ is associated with a fixed purchase and installation cost $c_i^{mac}$, which is paid if this machine is active at least once, and a fixed electric power $w_i$, which is consumed at any time when the machine is active. The total power supply functions $W_q(t), q \in L$, can be given, where $W_q(t)$ is an upper bound on the total power consumed by all active machines at time $t$ in location $q$. The maximum consumed power is associated with the unit cost $c^{pwr}$. Each location $q \in L$ is associated with a fixed cost $c_q^{loc}$, which is paid if at least one job $j$ is processed in the time window $[r_{qj}, \bar{d}_{qj}]$.

The time horizon can be an interval or a circle $[0, T]$ (with time moving clockwise). If time is *circular*, then times 0 and $T$ are the same time point. Each time instant $t$ and location $q \in L$ can be associated with the unit energy cost $c_q^{ene}(t)$. The problem is to find a feasible charging schedule such that some of the equipment and location costs, operational costs, power and energy costs and costs dependent of job completion times are minimized. We denote this problem as the *Regular Charging Scheduling Problem (RCSP)*.

Our main practical motivation is charging scheduling of city electric buses running on a fixed timetable, where each bus takes the same route. In this case, deadheading is not required if charging stations are located at a depot and the buses charge there only at night, or if charging stations are located at terminal stations or intermediate stops with sufficient idle time that can be used by buses to recharge. This occurs in many urban public electric transport applications, as well as in other applications where electric vehicles make regular trips and have regular charging events with charging stations located directly along their routes.

City electric buses are typically charged once per day at the depot or once per trip (return or one way) at a terminus. In our terminology, the corresponding charging event is a job. If an electric bus needs to be charged along its route, it is usually assigned a charging location, which must be selected from a given set of bus stops. Arrival and departure times are determined by the fixed passenger timetable for each such stop. Given the fact that the bus is charged once and at the same location on each trip, this information determines the charging time interval, the initial and desired energy levels and the energy cost for the respective job. Energy costs can vary depending on location. For each job, the charging scheduling decision includes the selection of a charging station (if two or more are available) and the charging time slots at that station's chargers in the appropriate time window.

**Remark 1.** If there is a single machine location ($|L| = 1$), then we omit location index $q$, and if $|L| = 1$ and the machines are identical, then we omit machine index $i$ in the notation of problem parameters.

**Remark 2.** Scheduling problems with circular time should not be mixed with cyclic, rotating and periodic scheduling problems, in which jobs must complete in a linear time interval (often called cycle), and their schedule repeats an infinite number of times.

### 3. Three-field notation

We adapt the traditional scheduling notation $\alpha|\beta|\gamma$. In all the studied problems, there are $m$ parallel machines (chargers) and $n$ jobs with release dates and deadlines. The number of machines $m$ can be a given constant (part of the problem type), it can be a part of the problem instance and it can be a decision variable. In the EV routing and charging scheduling research, vehicle charging under the assumption that the number of chargers $m$ is limited (bounded from above by a constant) is called *capacitated charging*. In this case, it is not guaranteed that there will be an appropriate free charger at the time when an EV arrives to the charging station.

In 2017, Montoya et al. (2017) cited no literature on capacitated charging and mentioned it as an interesting topic for future work. Six years later, de Vos et al. (2024) considered capacitated charging and reviewed several relevant papers. There exist different opinions about the need to study capacitated charging. In particular, for the problem of scheduling and charging electric tow trains Diefenbach et al. (2023) assume that all charging stations have sufficient space and capacity. They write “Clearly, this may not always be the case in practice, where charging capacities can be limited by space or the charging infrastructure’s capacity. Nevertheless, it presents a common assumption in the literature”. To support the consideration of capacitated charging, Froger et al. (2022) argue that in practice each charging station has a fixed and often small number of chargers. An important reason for this are high purchase, installation and operation costs of the chargers. Perumal et al. (2022) state that slow chargers have a low installation cost and a low charging power, whereas fast chargers have a high installation cost and a high charging power.

**Remark 3.** The $m$ machines each of which is supposed to be active at least once must be distinguished from the machines that are simultaneously active at time $t$. Denote number of the latter machines as $m(t)$. They alone contribute to the power consumption at time $t$. Denote maximum number of machines that are active at each time instant, $\max_t\{m(t)\}$, as $m_{max}$. It is clear that $m_{max} \le m$. If the supplied power is limited by the same value $W$ and the power of all machines is equal to $w$, then $m_{max} \le \min\{m, |W/w|\}$.

The first field is $\alpha \in \{1, P, Q, R\}$, where 1 means that $m = 1$, $P$ denotes identical machines, $Q$ states for uniform machines, and $R$ denotes the most general case of unrelated machines. Values of $\alpha$ other than $\alpha = 1$ imply that there are two or more machines. If the machines are identical, then the charging functions, processing (charging) speeds, setup times and costs, machine costs and powers are the same for all machines: $f_{ij}(\Delta) = f_j(\Delta), v_{ij} = 1, s_{ij} = s_j, c_{ij}^{set} = c_j^{set}, c_{i}^{mac} = c^{mac}, w_i = w$ for all $i \in M$. If the machines are uniform, then $v_{ij} = v_i$, that is, the processing speed depends of the machine (charger) and it does not depend of the job (EV's battery). The setup times and costs may remain arbitrarily dependent of the job and the machine. In the unrelated machine case, the job processing time on a machine depends on the job and the machine. Notations $Pm, Qm$ and $Rm$ are used instead of $P, Q$ and $R$ to show that the number of machines $m$ is fixed (it is a part of the problem type and not part of the problem instance or decision variable). Notations $P_\infty, Q_\infty$ and $R_\infty$ are used if there is an unlimited number of copies of each of the $m$ machines. In this case, all jobs can be processed in parallel on copies of any machines.

The second field is a subset of the union of eight sub-fields: $\beta \subseteq \cup_{s=1}^8 \beta_s$. Notation $\circ$ is used if respective sub-field is not present in the second field. The sub-fields are the following.

* $\beta_1 \in \{\circ, circ\}$. If $\beta_1 = \circ$, then time is linear. If $\beta_2 = circ$, then time is circular.

* $\beta_2 \in \{\circ, pmtn\}$. If $\beta_2 = \circ$, then no preemption is allowed. If $\beta_2 = pmtn$, then preemptions are allowed.

* $\beta_3 \in \{\circ, M_q\}$. If $\beta_3 = \circ$, then there is a single machine location ($|L| = 1$). Notation $M_q$ indicates that there are several locations.
• $\beta_4 \subset \{o, r_j, r_j, r_j = r, \bar{d}_{q_j}, \bar{d}_j, \bar{d}_j = \bar{d}\}$. If $\beta_4 = o$, then the (charging) time window is the same for all jobs and it is unrestricted. Notation $\beta_4 \in \{r_{q_j}, r_j\}$ specifies that the release dates are arbitrary for the respective machine environment (with several locations and single location), and notation $\beta_4 \in \{\bar{d}_{q_j}, \bar{d}_j\}$ specifies that the deadlines are arbitrary. Notations $r_j = r$ and $\bar{d}_j = \bar{d}$ are used if all the release dates are equal and all the deadlines are equal, respectively.

• $\beta_5 \in \{o, s_{ij}, s_j, s_j = s\}$. If $\beta_5 = o$, then the setup times are all equal to zero. If $\beta_5 = s_{ij}$, then arbitrary non-zero setup times are given. Notations $s_j$ and $s_j = s$ are used if setup times are job (EV) dependent and machine (charger) independent, and they are all the same, respectively.

• $\beta_6 \in \{o, W_q(t), W(t), W_q(t) = W_q, W(t) = W\}$. If $\beta_6 = o$, then the power supply in unlimited. If $\beta_6 \in \{W_q(t), W(t)\}$ then a dynamic upper bound $W_q(t)$ or $W(t)$ on the total power of the simultaneously active machines (chargers) is given in each location $q \in L$ or in the single location. Notations $W_q(t) = W_q$ and $W(t) = W$ are used if this upper bound is time-independent.

• $\beta_7 \subset \{o, c_i^{mac}, c_i^{mac} = c_i^{mac}, c_i^{ene}(t), c_i^{ene}(t), c_i^{ene}(t) = c_i^{ene}, c_i^{ene}(t), c_i^{ene}(t) = c_i^{ene}, c_i^{pur}, c_{ij}^{set}, c_{ij}^{set} = c_{ij}^{set}, c_q^{loc}, c_q^{loc} = c_{q}^{loc}\}$. If $\beta_7 = o$, then machine, energy, supplied power, setup and location costs are all equal to zero. If $\beta_7 \neq o$, then the respective costs are non-zero and they are arbitrary or characterized by the given equality.

• $\beta_8 \in \{o, p_{ij} = p_i, p_{ij} = p_q, p_{qj} = \bar{d}_{qj} - r_{qj}, p_{qij} \in S\}$. If $\beta_8 = o$, then the processing time $p_{qij}$ can be any number according to the machine environment. Notations $p_{ij} = p_i$ and $p_{qj} = p_q$ are used to indicate that times $p_{ij}$ depend only on the machine and, in the case of identical or uniform machines, only on the location, respectively. Notation $p_{qj} = \bar{d}_{qj} - r_{qj}$ means that if job $j$ is processed on a machine in location $q$, then it occupies time window $[r_{qj}, \bar{d}_{qj}]$ completely. Respective models are studied under the name fixed interval scheduling in the literature. If $\beta_8 = (p_{qij} \in S)$, then $p_{qij}$ are restricted to take values from the set $S$ that has to be explicitly given. Each value $p \in S$ is associated with a subset of machines $M(p) \neq \emptyset$ and a subset of jobs $N(p) \neq \emptyset$ such that if job $j \in N(p)$ is processed on machine $i \in M(p)$ then its processing time is equal to $p$.

The third field specifies the goal of the charging scheduling decision, $\gamma \in \{-, MinCost(f), F(C_1, ..., C_n)\}$, where $C_j$ denotes job $j$ completion time, $f \subseteq \{L, m, m_{max}, E, W, W_{max}, Setup, \sum T_j\}$, and notations in the latter set represent locations ($L$), number of required machines ($m$), maximum number of simultaneously active machines ($m_{max}$), energy ($E$), power ($W$), power of simultaneously active machines ($W_{max}$), setups (Setup), and total tardiness ($\sum T_j$), respectively. Tardiness is defined as $T_j = \max\{0, C_j - \bar{d}_j\}$. If $\gamma = -$, then the goal is to find a feasible charging schedule or determine that it does not exist. If $\gamma$ is equal to $MinCost(f)$ then the goal is to find a feasible charging schedule that minimizes the sum of the costs associated with the objects given by $f$. If $\gamma = F(C_1, ..., C_n)$, then the goal is to minimize a function of job completion times. The following remarks can be useful in classifying and solving a charging scheduling problem.

**Remark 4.** An algorithm for the decision problem $\alpha|r_j, \bar{d}_j, \beta|$, $\alpha \in \{Pm, Qm, Rm\}$, can be used to solve the respective problem $\alpha|r_j, \bar{d}_j, \beta, c_i^{mac} = c_i^{mac} | MinCost(m), \alpha \in \{P, Q, R\}$, of minimizing the number of active machines, by applying a bisection search over the range $m \in \{1, ..., n\}$, in which the problem $\alpha|r_j, \bar{d}_j, \beta|$, $\alpha \in \{Pm, Qm, Rm\}$, with fixed number of machines $m$ is solved $O(\log n)$ times.

**Remark 5.** The energy minimization is not trivial only if there are different locations ($|L| \ge 2$) or the energy cost function $c^{ene}(t)$ is not constant ($c^{ene}(t) \neq c^{ene}$). If it is constant and $|L| = 1$, then the total energy cost is equal to $c^{ene} \sum_{j \in N} (e_j - e_j^0)$.

**Remark 6.** If preemptions are prohibited, then there is a single setup preceding the uninterrupted job processing. In this case, the total setup cost is equal to $\sum_{i \in M} \sum_{j \in N} c_{ij}^{set}$, where $x_{ij} = 1$ if job $j$ is processed on machine $i$ and $x_{ij} = 0$, otherwise. For the case of identical machines and no preemptions, the total setup cost is equal to $\sum_{j \in N} c_{j}^{set}$.

**Remark 7.** The no energy loss assumption for the setups can be partly relaxed by assuming that the time of restoration of the energy level at the end of the setup to that in the beginning of the setup is included into the setup time. Machines must be considered as active during setups in this case.

**Remark 8.** The no preemption case can be appropriate for modeling the situation in which EV re-charging is realized by the battery exchange. In this case, the machines are the battery exchange points, and the processing times $p_{qij}$ are independent of the energy levels.

**Remark 9.** The problem $\alpha|r_j, \bar{d}_j, \text{circ}, \beta|-$ with circular time reduces to the problem $\alpha|r_j, \bar{d}_j, \beta|-$ with linear time if there is a point in time $t$ that is not strictly inside any time window, $t \notin \cup_{j \in N}(r_j, \bar{d}_j)$. If $[0, T]$ is the time circle, then any time point $\tau \neq t$ in an instance of the problem $\alpha|\text{circ}, r_j, \bar{d}_j, \beta|-$ corresponds to the point $\tau^0 = \begin{cases} \tau - t, & \text{if } t < \tau \le T \\ T - t + \tau, & \text{if } 0 \le \tau < t \end{cases}$ in the respective instance of the problem $\alpha|r_j, \bar{d}_j, \beta|$. Consideration of the time point $t \notin \cup_{j \in N}(r_j, \bar{d}_j)$ is specific. If $t \notin \cup_{j \in N}\{r_j, \bar{d}_j\}$, then $t$ can be removed from the input of both problems. Release dates $r_j = t$ in $\alpha|\text{circ}, \beta, r_j, \bar{d}_j|-$ turn into $r_j = 0$ in $\alpha|\beta, r_j, \bar{d}_j|-$, and deadlines $\bar{d}_j = t$ in $\alpha|\text{circ}, \beta, r_j, \bar{d}_j|-$ turn into $\bar{d}_j = T$ in $\alpha|\beta, r_j, \bar{d}_j|-$.

# 4. Linear time, no preemptions

In this section, time is assumed to be linear. In Section 4.1, we review existing computational complexity and algorithmic results for the non-preemptive parallel machine scheduling problems and their special cases. EV routing and non-preemptive charging scheduling problems are reviewed in Section 4.2.

## 4.1. Non-preemptive parallel machine scheduling

Note that any of the algorithms described below can generate an infeasible schedule. In this case, no feasible schedule exists for the respective problem instance. The classical scheduling problems $\alpha|r_j, \bar{d}_j|-$, $\alpha \in \{1, P, Q, R\}$, with no preemptions are special cases of the regular charging scheduling problem RCSP, in which there is a single machine location ($|L| = 1$), all costs are equal to zero ($c_q^{loc} = c_i^{mac} = c_i^{ene}(t) = c_{ij}^{set} = 0$), and the power supply is unlimited ($W(t) = \infty$).

The easiest non-preemptive single-machine problem with arbitrary job processing times, release dates and deadlines, $1|r_j, \bar{d}_j|-$, is already NP-hard in the strong sense (Lenstra et al., 1977). This problem is solvable in $O(n \log n)$ time if $r_j$ and $\bar{d}_j$ are agreeable such that $r_j < r_h$ implies $\bar{d}_j \le \bar{d}_h$ for any jobs $j$ and $h$, or if $p_j = p$ and $r_j$ and $d_j$ are multiples of $p$, or equivalently, $p_j = 1$ and $r_j$ and $d_j$ are integer, $j \in N$. The algorithm is described by the following Earliest Deadline First (EDF) rule: At any time when the machine is ready for job processing, schedule job with the earliest deadline of all jobs available at this time (see for example, Lawler, 1994). Problems $1|r_j, \bar{d}_j = \bar{d}|-$ and $1|r_j = 0, \bar{d}_j|-$ with equal deadlines and equal release dates, respectively, can be solved in $O(n \log n)$ time by sequencing the jobs in the Earliest Release Date First (ERDF) order (first-come, first-served rule) and the Earliest Deadline First (EDF) order, respectively.

The problem $1|r_j, \bar{d}_j, p_j = p|-$ cannot be solved by the above rule because $r_j$ and $\bar{d}_j$ are not necessarily multiples of $p$. Garey et al. (1981) proposed a specialized $O(n \log n)$ time algorithm for this problem that
is based on the concepts of “forbidden regions”, “backscheduling algo-
rithm” and “task load tree”. Simons and Warmuth (1989) generalized
ideas of Garey et al. (1981) to develop an *O(mn²)* time algorithm
for the problem *P|r*<sub>j</sub>, *d̄*<sub>j</sub>, *p*<sub>j</sub> = *p*|−. Dourado et al. (2009) presented
an *O*(*n*² log *m* / (*n* + log *n*)) time graph-theoretic algorithm for a problem
more general than *P|r*<sub>j</sub>, *d̄*<sub>j</sub>, *p*<sub>j</sub> = 1|−, see also Brucker and Shakhle-
vich (2016). Demaine et al. (2013), Angel et al. (2014) and Brauner
et al. (2021) propose polynomial time algorithms for the problem
*P*<sub>∞</sub>|*r*<sub>j</sub>, *d̄*<sub>j</sub>, *p*<sub>j</sub> = 1, *c*<sub>i</sub><sup>mac</sup> = *c*<sub>i</sub><sup>mac</sup> | *MinCost*(*m*) with an extra constraint that
no machine can stand idle between its start and completion times.

The problem $P|r_j = 0, \bar{d}_j = \bar{d}|-$ is the classical strongly NP-hard problem whose special case is 3-Partition, and the problem $P2|r_j = 0, \bar{d}_j = \bar{d}|-$ is the classical ordinary NP-hard problem equivalent to Partition (Garey & Johnson, 1979). Therefore, problems $Q|r_j = 0, \bar{d}_j = \bar{d}|-$ and $R|r_j = 0, \bar{d}_j = \bar{d}|-$ are NP-hard in the strong sense and problems $Qm|r_j = 0, \bar{d}_j = \bar{d}|-$ and $Rm|r_j = 0, \bar{d}_j = \bar{d}|-$, $m \ge 2$, are NP-hard in the ordinary sense. Kravchenko and Werner (2011) solve the problem $P_\infty|r_j, \bar{d}_j, p_j = p|MinCost(m_\max)$ in polynomial time. Their approach is a reduction to a *Linear Programming (LP)* problem.

The uniform machine scheduling problem $Q|r_j = r, \bar{d}_j, p_j = p|-$ can be solved in $O(n \log n)$ time by the following algorithm of Dessouky et al. (1990): Determine non-decreasing sequence of earliest job completion times $t_1, \dots, t_n$ on $m$ uniform machines, provided that the jobs start after the common release date $r$. Then, assuming $\bar{d}_1 \le \dots \le \bar{d}_n$, match job $j$ and the earliest completion time $t_j$, $j \in N$. This matching is equivalent to assigning job with the earliest deadline to the machine where it will be completed the earliest if all jobs start after the common release date $r$. The following modification of this algorithm is an $O(n \log n)$ algorithm for the “mirror” problem $Q|r_j, \bar{d}_j = \bar{d}, p_j = p|-$: Determine the non-decreasing sequence $t_1, \dots, t_n$. Calculate non-decreasing sequence of latest job start times $\bar{d}-t_n, \bar{d}-t_{n-1}, \dots, \bar{d}-t_1$ on $m$ machines. Assuming $r_1 \le \dots \le r_n$, match job $j$ and the latest start time $\bar{d}-t_{n+1-j}, j \in N$. This matching defines job sequences on the machines in the non-decreasing order of release dates. Finally, determine common machine start time as $\max_{j \in N}\{r_j - \bar{d} + t_{n+1-j}\}$. Discussion of other mirror scheduling problems can be found in Chen et al. (2021). Computational complexity of the problems $Q|r_j, \bar{d}_j, p_j = p|-$ and $Qm|r_j, \bar{d}_j, p_j = p|-$ for $m \ge 2$ is unknown. The problem $Q|r_j, \bar{d}_j, p_j = 1|-$ is solved by the optimal flow algorithm of Federgruen and Groenevelt (1986) that is designed for the preemptive problem $Q|pmtn, r_j, \bar{d}_j|-$.

The case $R|r_j, \bar{d}_j, p_{ij} \in \{1, 3\}|-$ is NP-hard in the strong sense, and the cases $R|r_j, \bar{d}_j, p_{ij} \in \{1, 2\}|-$ and $R|r_j, \bar{d}_j, p_{ij} \in \{1, \infty\}|-$ are polynomially solvable by a matching technique (Lenstra et al., 1990). Vakhania et al. (2014) proposed a two-phase method to solve the problem $R|r_j, \bar{d}_j, p_{ij} \in \{p, 2p\}|-$ in polynomial time. Lin and Li (2004) designed an $O(n^3 \log nv)$ time network flow algorithm for the problem $R|r_j = r, \bar{d}_j = \bar{d}, p_{ij} \in \{p/\nu_i, \infty\}|-$, in which $\nu$ is the least common multiple of the machine speeds $v_1, \dots, v_m$, and each job $j$ can be processed only on an admissible subset of the machines defined by $p_{ij} \neq \infty$. A simpler $O(mn)$ time algorithm is proposed in Lin and Li (2004) for the latter problem if the family of admissible machine subsets is convex. Results on fixed interval scheduling problems $\alpha|r_j, \bar{d}_j, p_{ij} = \bar{d}_{\alpha} - r_{\alpha}|\gamma$ have been reviewed by Kolen et al. (2007) and Kovalyov et al. (2007) in 2007. Recent publications in this area can be found in Muir and Toriello (2023). Computational complexity of the problems in this section and respective references are summarized in Table 1.

## 4.2. EV routing and non-preemptive charging scheduling

As in most previous studies, we assume that EV routing includes
the assignment of EVs to the service trips in space and time. Due to the
limited driving range, EVs need to be re-charged during their services.
We additionally assume that EV routing includes visiting charging
stations. If the routing decision is fixed, then each EV visits a specified
charging station in the specified time window to replenish its battery. A

non-preemptive charging event during such a visit is a non-preemptive
job in our terminology.

**Non-preemptive capacitated charging.** The vast majority of publications on routing and non-preemptive capacitated charging of EVs are devoted to the case of multiple charging station locations. Each charging event $j \in N$ on charger $i \in M_q$ in location $q \in L$ is characterized by the time interval $[r_{aj}, \bar{d}_{aj}]$. The release date $r_{aj}$ is determined by the EV's earliest possible arrival time to location $q$ and the deadline $\bar{d}_{aj}$ is determined by the EV's latest possible departure time from $q$ between two consecutive service trips associated with the charging event $j$. We first review papers studying single location and then multiple charging locations. Papers of each of the two types are reviewed in chronological order.

**Single charging location.** A pure regular charging scheduling problem with soft deadlines to minimize total tardiness, $P|r_j, \bar{d}_j| \sum T_j$, is described by Hernández-Arauzo et al. (2015). It is modeled as a constraint satisfaction problem. Chen et al. (2018) consider regular charging tasks of electric buses at a single fast charging station, equipped with an energy storage system that accommodates energy at cheaper times. The charging scheduling sub-problem is close to $P|r_j, \bar{d}_j, c^{ene}(t), c^{pwr}|MinCost(E, W_{max})$. Nguyen et al. (2018) consider identical parallel machine scheduling problem with a single additional resource and mentioned charging scheduling as an application. If the resource represents the number of active identical chargers, then this problem is the regular non-preemptive charging scheduling problem $P|r_j, \bar{d}_j, W(t)| \sum C_j$, with the dynamic limited power supply and the objective of minimizing the total (or average) job completion time.

A mixed fleet of hybrid and electric buses with irregular charg-
ing and no deadheading is considered by Rinaldi et al. (2020). The
regular charging scheduling sub-problem can be expressed as
$P|r_j, \bar{d}_j, p_j = 1, c^{ene}(t)|MinCost(E)$. Alvo et al. (2021) study the problem
of dispatching diesel and electric buses. The charging is regular and
the corresponding scheduling model is $P|r_j, \bar{d}_j, W(t) = W|-$.
Zhang et al. (2021) assume that the trip schedule of electric buses is predetermined
and a charging event occurs between two consecutive trips, which leads
to the simple regular charging scheduling sub-problem $P|r_j, \bar{d}_j|$. The
same sub-problem appears in Nolz et al. (2022) where pickup and deliv-
ery of parcels by EVs is studied. Minimizing total energy and power cost
is the objective of the charging scheduling sub-problem in Duan et al.
(2023), which can be denoted as $P|r_j, \bar{d}_j, c^{ene}(t)|MinCost(E, W)$. In the
initial problem, the charging tasks are regular and no deadheading
is needed. He J. Yan et al. (2023) consider a situation in which an
electric bus is charged at a given terminal and historical data is used to
determine time windows for regular charging. The charging scheduling
sub-problem is $P|r_j, \bar{d}_j, p_j = p, c^{ene}(t)|MinCost(E)$.

**Multiple charging locations.** Li (2014) proposes a vehicle scheduling and charging model for electric transit buses with irregular battery swapping or fast charging at several stations. Once the bus route is determined, bus charging tasks become regular. The regular charging scheduling sub-problem is $P|M_q, r_{aj}, \bar{d}_{aj}, p_{aj} = p_q|-$, van Kooten Niekerk et al. (2017) mention charging station location costs, capacitated charging and limited electric power in their study of EV scheduling. Charging is irregular with possible deadheading, and it becomes regular once a route decision has been made. The corresponding regular charging scheduling sub-problem could be $R|M_q, r_{aj}, \bar{d}_{aj}, W(t), c^{ene}(t), c^{pwr}, c^{loc}|MinCost(L, E, W_{max})$. However, it is not part of the studies in van Kooten Niekerk et al. (2017), Janovec and ani (2019) consider public EVs and their irregular charging without deadheading at depot and terminal stops. The regular charging part of their research concerns $P|M_q, r_{aj}, \bar{d}_{aj}|-$, Although Tang et al. (2019) study a stochastic problem of scheduling electric buses with irregular charging and deadheading, they present a robust deterministic model whose regular charging scheduling part is $P|M_q, r_{aj}, \bar{d}_{aj}, p_{aj} = \bar{d}_{aj} - r_j|-$.

A problem of routing and charging alternative fuel vehicles is stud-
ied by Bruglieri et al. (2019, 2021). Charging is irregular with possible
deadheading. If the routing decision is fixed, then the problem boils
<table><caption>**Table 1**

Linear time and no preemptions: computational complexity.</caption><thead><tr><th>Problem</th><th>Complexity, algorithm</th><th>Reference</th></tr></thead><tbody><tr><td>1|r<sub>j</sub>, ⃗d<sub>j</sub>|-</td><td>strongly NP-hard</td><td>Lenstra et al. (1977)</td></tr><tr><td>1|r<sub>i</sub> &lt; r<sub>j</sub> ⇒ ⃗d<sub>i</sub> ≤ ⃗d<sub>j</sub>|-</td><td>O(n log n), EDF rule</td><td>Lawler (1994)</td></tr><tr><td>1|r<sub>j</sub>, ⃗d<sub>j</sub>, p<sub>j</sub> = 1|-</td><td>O(n log n), EDF rule</td><td>Lawler (1994)</td></tr><tr><td>1|r<sub>j</sub>, ⃗d<sub>j</sub> = ⃗d|-</td><td>O(n log n), ERDF order</td><td>Lawler (1994)</td></tr><tr><td>1|r<sub>j</sub> = 0, ⃗d<sub>j</sub>|-</td><td>O(n log n), EDF order</td><td>Lawler (1994)</td></tr><tr><td>1|r<sub>j</sub>, ⃗d<sub>j</sub>, p<sub>j</sub> = p|-</td><td>O(n log n), forbidden regions</td><td>Garey et al. (1981)</td></tr><tr><td>P|r<sub>j</sub>, ⃗d<sub>j</sub>, p<sub>j</sub> = p|-</td><td>O(mm<sup>2</sup>), forbidden regions</td><td>Simons and Warmuth (1989)</td></tr><tr><td>Generalized P|r<sub>j</sub>, ⃗d<sub>j</sub>, p<sub>j</sub> = 1|-</td><td>O(n<sup>2</sup> log m + n log n), graph-theoretic</td><td>Dourado et al. (2009)</td></tr><tr><td>P<sub>∞</sub>|r<sub>j</sub>, ⃗d<sub>j</sub>, p<sub>j</sub> = 1, c<sup>mac</sup> = c<sup>max</sup>|MinCost(m) with machine no-idle</td><td>polynomial</td><td>Angel et al. (2014), Brauner et al. (2021), Demaine et al. (2013)</td></tr><tr><td>a2|r<sub>j</sub> = 0, ⃗d<sub>j</sub> = ⃗d|-, α ∈ {P, Q, R}</td><td>NP-hard</td><td>Garey and Johnson (1979)</td></tr><tr><td>a|r<sub>j</sub> = 0, ⃗d<sub>j</sub> = ⃗d|-, α ∈ {P, Q, R}</td><td>strongly NP-hard</td><td>Garey and Johnson (1979)</td></tr><tr><td>P<sub>∞</sub>|r<sub>j</sub>, ⃗d<sub>j</sub>, p<sub>j</sub> = p|MinCost(m<sub>max</sub>)</td><td>polynomial, LP</td><td>Kravchenko and Werner (2011)</td></tr><tr><td>Q|r<sub>j</sub> = r, ⃗d<sub>j</sub>, p<sub>j</sub> = p|-</td><td>O(n log n), matching</td><td>Dessouky et al. (1990)</td></tr><tr><td>Q|r<sub>j</sub>, ⃗d<sub>j</sub> = ⃗d, p<sub>j</sub> = p|-</td><td>O(n log n), matching</td><td>Dessouky et al. (1990)</td></tr><tr><td>Q|r<sub>j</sub>, ⃗d<sub>j</sub>, p<sub>j</sub> = p|-</td><td>unknown</td><td></td></tr><tr><td>Qm|r<sub>j</sub>, ⃗d<sub>j</sub>, p<sub>j</sub> = p|-, m ≥ 2</td><td>unknown</td><td></td></tr><tr><td>Q|r<sub>j</sub>, ⃗d<sub>j</sub>, p<sub>j</sub> = 1|-</td><td>O(mm<sup>3</sup>), max-flow</td><td>Federgruen and Groenevelt (1986), Karzanov (1974)</td></tr><tr><td>R|r<sub>j</sub>, ⃗d<sub>j</sub>, p<sub>j</sub> ∈ {1, 3}|-</td><td>strongly NP-hard</td><td>Lenstra et al. (1990)</td></tr><tr><td>R|r<sub>j</sub>, ⃗d<sub>j</sub>, p<sub>j</sub> ∈ {1, 2}|-</td><td>polynomial, matching</td><td>Lenstra et al. (1990)</td></tr><tr><td>R|r<sub>j</sub>, ⃗d<sub>j</sub>, p<sub>j</sub> ∈ {1, ∞}|-</td><td>polynomial, matching</td><td>Lenstra et al. (1990)</td></tr><tr><td>R|r<sub>j</sub>, ⃗d<sub>j</sub>, p<sub>j</sub> ∈ {p, 2p}|-</td><td>polynomial, two-phase</td><td>Vakhania et al. (2014)</td></tr><tr><td>R|r<sub>j</sub> = r, ⃗d<sub>j</sub> = ⃗d, p<sub>j</sub> ∈ {p/v<sub>i</sub>, ∞}|-</td><td>O(n<sup>3</sup> log nv), v = LCM(v<sub>1</sub>, ..., v<sub>m</sub>)</td><td>Lin and Li (2004)</td></tr><tr><td>"Convex" R|r<sub>j</sub> = r, ⃗d<sub>j</sub> = ⃗d, p<sub>j</sub> ∈ {p/v<sub>i</sub>, ∞}|-</td><td>O(mm)</td><td>Lin and Li (2004)</td></tr><tr><td>a|r<sub>j</sub>, ⃗d<sub>j</sub>, p<sub>j</sub> = ⃗d<sub>qj</sub> - r<sub>qj</sub>|γ</td><td>various</td><td>Kolen et al. (2007), Kovalyov et al. (2007), Muir and Toriello (2023)</td></tr></tbody></table>

down to $P|M_q, r_{qj}, \vec{d}_{qj}, p_{qj} = p_q|-$. Abdelwahed et al. (2020) consider regular fast-charging of electric buses at several stations, with a station dependent setup time preceding a single charging event of each bus. The charging scheduling part of their problem can be described as $P|M_q, r_{qj}, \vec{d}_{qj}, p_j = p, c^{ene}(t)|MinCost(E, W)$. Minimizing energy cost and peak power are the objectives in a multi-depot EV routing and charging scheduling problem of Wu et al. (2022). Charging is irregular and deadheading for charging may be needed. The respective regular charging scheduling sub-problem is $P|M_q, r_{qj}, \vec{d}_{qj}, p_j = p, c^{ene}(t)|MinCost(E, W_{max})$.

Lam et al. (2022) extend the classical vehicle routing problem with time windows by considering EVs and capacitated charging stations, charging decisions and deadheading for charging. The regular charging sub-problem is $P|M_q, r_{qj}, \vec{d}_{qj}|-$. Similar problems and the same charging sub-problem are considered in Froger et al. (2022), de Vos et al. (2024) and Gkiotsalitis et al. (2023). Alam Md and Guo (2023) investigate the problem of routing and charging electric freight vehicles that employ the platoon driving protocol. Charging events have to be decided (they are irregular) and occur along the route without involving a deadheading. The regular charging scheduling sub-problem is the problem $P|M_q, r_{qj}, \vec{d}_{qj}, c^{ene}(t)|MinCost(E)$.

Similar to Nguyen et al. (2018), An et al. (2023) consider total completion time minimization in their study of a regular charging scheduling problem, although, for multiple charging locations. The respective problem is $P|M_q, r_{qj}, \vec{d}_{qj}| \sum C_j$. Bragin et al. (2024) study a joint routing, goods delivery and charging scheduling problem for electric heavy trucks to minimize the total labor, charging, and tardiness costs with respect to the goods delivery times. Charging decisions have to be made (implying irregular charging) and deadheading is possible. If trucks are assigned to the trips and actual charging places are fixed, then the (regular) charging scheduling sub-problem is $P|M_q, r_{qj}, \vec{d}_{qj}, c^{ene}(t)|MinCost(E, \sum T_j)$.

The remaining literature on deterministic routing and non-preemptive charging scheduling concerns non-capacitated charging, for which the number of chargers (machines) of the same type (with the same speed)

can be limited from above by the maximum number of intersecting charging time windows.

**Non-preemptive non-capacitated charging.** As for capacitated charging, we first review studies considering single location and then multiple locations.

**Single charging location.** Leou and Hung (2017) study a pure regular charging scheduling problem $P_{\infty}|r_j, \vec{d}_j, W(t), c^{ene}(t)|MinCost(E, W_{max})$ with three distinct energy cost periods. Rogge et al. (2018) suggest that initially irregular charging becomes regular when the vehicle schedule is fixed. In addition, each charging event is accompanied by a pre-processing and a post-processing setup time of 15 min. Their regular charging scheduling sub-problem can be written as $P_{\infty}|r_j, \vec{d}_j, c^{mac}, c^{ene}(t) = c^{ene}, s_j = s|MinCost(m, E)$. The original charging scheduling models developed by Zhou et al. (2020) and Zhou et al. (2022) include irregular charging and deadheading, and their regular counterparts are $P_{\infty}|r_j, \vec{d}_j, c^{ene}(t)|MinCost(E)$ (with three distinct energy cost periods) and $Q_{\infty}|r_j, \vec{d}_j, c^{ene}(t) = c^{ene}|MinCost(E)$, respectively.

Masone et al. (2021) and Boccia et al. (2023) focus on the problem of optimizing electric Automated Guided Vehicle (AGV) transfer and charging operations in a production environment. The aim is to speed up the production process. It is assumed that, for each AGV, a set of its transfer operations is followed by a charging operation to be performed in the same location. Any number of charging operations of different AGVs can be performed in parallel, which implies that the number of chargers is equal to the number of AGVs. Charging operations need to be timed, so they are irregular, but charging deadheadings are not required. A regular charging sub-problem of this problem in which the assignment of the transfer operations to the charging operations of each AGV is fixed, can be modeled by the problem $P_{\infty}|s_{ij} = s_j, p_j = p|C_{max}$, in which the setup time $s_j$ plays the role of the total duration of the transfer operations assigned to the charging operation $j$.

**Multiple charging locations.** Mak et al. (2013), Adler (2014), Adler and Mirchandani (2017) and Verma (2018) study a problem of routing EVs through a network where EVs irregularly recharge or swap their batteries at the battery recharging and exchange stations. All but Verma
(2018) assume that recharging the battery takes the same time $p$ and swapping the battery takes the same time $p/v$, $v > 1$. This problem contains uniform machine scheduling problem $Q_\infty | M_q, r_{qj}, \bar{d}_{qj}, p_j = p | MinCost(L)$ as a sub-problem. Verma (2018) assumes that the time of recharging the battery depends on the battery and that the charging time window constraints can be violated at a cost.

Wang et al. (2017) developed and tested a model to optimize electric bus regular recharging schedules. The model can be represented in a simplified form as $P_\infty | M_q, r_{qj}, \bar{d}_{qj}, p_{qij} = p, c_i^{mac} = c^{mac}, c_q^{loc} = c^{loc} | MinCost(m, L)$. Goekе and Schneider (2015) study a problem of routing a mixed fleet of electric and conventional vehicles, with irregular EV charging. If the routing decision is fixed, then their charging scheduling problem is $P_\infty | M_q, r_{qj}, \bar{d}_{qj}|$. The same charging scheduling sub-problem appears in EV routing problem of Wang and Zhao (2023). There are electric buses of different types and multiple charging stations each dedicated to a specific bus type in Li et al. (2019). The regular charging scheduling sub-problem of the general problem with irregular charging can be described as $R_\infty | M_q, r_{qj}, \bar{d}_{qj}, p_{qij} \in \{p_{qj}, \infty\}, c_i^{mac} | MinCost(m)$.

Olsen and Kliewer (2020) and Olsen et al. (2022) explore the nonlinear charging process of EVs in the context of routing, irregular charging and deadheading decisions for public electric buses. They assume unbounded capacities of the charging stations and identical chargers. Their experiments with real data demonstrate that the assumptions of linear and constant charging times underestimates and overestimates, respectively, sizes of actual time windows for charging. Diefenbach et al. (2023) present a similar EV scheduling problem with multiple charging stations in an in-plant logistics setting. They explicitly consider common charging setup times. Since preemptions are prohibited, the setup applies once for each visit of the charging station. A regular charging scheduling sub-problem of these problems is the problem $P_\infty | M_q, r_{qj}, \bar{d}_{qj}, s_{qij} = s|$. Li et al. (2020) integrate EV scheduling, charger quantification, and assigning them to EVs for irregular charging. Deadheadings are possible. The respective regular charging scheduling sub-problem is $P_\infty | M_q, r_{qj}, \bar{d}_{qj} | MinCost(m, E)$.

Wen et al. (2016), Yao et al. (2020) and He et al. (2020) do not consider charging setup times in their EV routing problems with deadheadings for charging. The regular charging scheduling sub-problems can be viewed as $P_\infty | M_q, r_{qj}, \bar{d}_{qj}|$, $P_\infty | M_q, r_{qj}, \bar{d}_{qj} | MinCost(m)$ and $P_\infty | M_q, r_{qj}, \bar{d}_{qj} | MinCost(E, W)$, respectively. A charging scheduling sub-problem in Ferro et al. (2020) is $R_\infty | M_q, r_{qj}, \bar{d}_{qj}, c_q^{ene} = c^{ene}, W_q(t) = W_q | MinCost(E)$, and in van Oosterom et al. (2023) it is $R_\infty | M_q, r_{qj}, \bar{d}_{qj}, p_{qij} \in \{p_{qj}, \infty\}|$. Liu and Ceder (2020) minimize the number of chargers as the secondary criterion. The regular charging sub-model of their model is the problem $R_\infty | M_q, r_{qj}, \bar{d}_{qj} | MinCost(m)$. The original problems in the last three studies suggest irregular charging and deadheadings.

Similar to Alam Md and Guo (2023), Scholl et al. (2023) study the problem of routing and irregular charging electric freight vehicles that employ the platoon driving protocol. Their regular charging scheduling sub-problem is $P_\infty | M_q, r_{qj}, \bar{d}_{qj}, c_q^{ene}(t) = c_q^{ene} | MinCost(E)$. The difference from Alam Md and Guo (2023) is the unlimited number of chargers in each location. The solution to the problem in Zhou et al. (2024) includes the assignment of electric buses to the trips, as well where, when and for how long to recharge them. The respective charging is irregular and permits deadheading. If the assignment of trips to buses is fixed, then the problem reduces to $P_\infty | M_q, r_{qj}, \bar{d}_{qj}, c_q^{ene}(t) = c_q^{ene} | MinCost(E)$.

## 5. Linear time, preemptions allowed

Computational complexity and algorithmic results for classical preemptive parallel machine scheduling problems are reviewed in Section 5.1. EV routing and preemptive charging scheduling problems are reviewed in Section 5.2.

### 5.1. Preemptive parallel machine scheduling

Similar to the non-preemptive case, classical preemptive scheduling problems $\alpha | pmtn, r_j, \bar{d}_j|$, $\alpha \in \{1, P, Q, R\}$, are special cases of the regular charging scheduling problem RCSP, in which there is a single machine location ($|L| = 1$), all costs are equal to zero, and the power supply is unlimited. Each preemption can be associated with a machine setup. We firstly consider the case of no setups (zero setup times and costs) and then the case with setups.

No setups. The problem $1|pmtn, r_j = r, \bar{d}_j|$ with a common job release date is solved in $O(n \log n)$ time by the Earliest Deadline First rule (Moore, 1968). For this problem, if there exists a feasible schedule, then there exists a feasible schedule with no preemptions. The problem $1|pmtn, r_j, \bar{d}_j|$ with arbitrary release dates and deadlines is solved in $O(n^2)$ time by a straightforward implementation of the following algorithm (Horn, 1974): at a decision time point, assign a job with the earliest deadline among all available jobs. The decision time point is such that a new job becomes available or the currently assigned job is completed. A new available job with an earlier deadline than the current one preempts the current uncompleted job, whose (remaining) processing time is updated accordingly. Schwan and Zhou (1992) and Kim (1994) proposed $O(n \log n)$ implementations of this algorithm based on efficient data structures such as balanced binary tree in Schwan and Zhou (1992) and a heap in Kim (1994). A feasible solution for the problem $1|pmtn, r_j, \bar{d}_j|$ can have at most $n-1$ preemptions and this bound is tight (Baker et al., 1983).

The well-known Wrap Around rule of McNaughton (1959) solves the problem $P|pmtn, r_j = r, \bar{d}_j = \bar{d}|$ with the same release dates and the same deadlines in $O(n)$ time. The rule is: If $p_j > \bar{d}$ for some job $j \in N$ or $\sum_{j \in N} p_j > m\bar{d}$, then no feasible schedule exists. Otherwise, consider machines in any order and consider jobs in any order. Assign jobs to the current machine one after another starting from the common release date (time zero) until the common deadline $\bar{d}$ is reached. If the current job is not completed at time $\bar{d}$, then preempt it and assign its remaining part to the next machine starting from time zero. The process stops when all jobs are completed. If a feasible solution is found, then it has no more than $m-1$ preemptions and it can be easily modified to have at most $n-2$ preemptions.

Problems $P|pmtn, r_j, \bar{d}_j = \bar{d}|$ and $P|pmtn, r_j = r, \bar{d}_j|$ are mirror images of each other with respect to the time direction (release dates of the former problem determine deadlines for the latter problem if time goes from the future time $\bar{d}$ towards the past times $r_j$). The problem $P|pmtn, r_j = r, \bar{d}_j|$ with a common release date is solved in $O(n \log nm)$ time by an efficient implementation of the following algorithm of Sahni (1979): Consider machines in any order and consider jobs in the Earliest Deadline First order. Partition the job set $N$ into disjoint subsets $N_1, \dots, N_k$ such that jobs in the same subset $N_i$ have the same deadline denoted as $\bar{d}^{(i)}$, and the subsets are numbered in the increasing order of the distinct deadlines. The algorithm consists of at most $k$ stages. In stage $l$, jobs of the set $N_l$ are scheduled in the time intervals $[T_l, \bar{d}^{(l)}]$ on machines $i \in M$, where $T_l$ is the completion time of machine $i$ after processing jobs of the subsets $N_1, \dots, N_{l-1}$. The jobs from $N_l$ are considered in any order. If $p_j > \max_{i \in M} (\bar{d}^{(i)} - T_l)$ for $j \in N_l$, then there is no feasible schedule and algorithm stops. If $p_j \le \max_{i \in M} (\bar{d}^{(i)} - T_l)$ for $j \in N_l$, then job $j$ is scheduled on the machine with the least available capacity $\bar{d}^{(i)} - T_l$, $i \in M$. If neither of the two conditions is satisfied, then job $j$ is assigned to fully occupy interval $[T_x, \bar{d}^{(i)}]$ on machine $x$ with the largest available capacity not exceeding $p_j$. If job $j$ is not completely processed on machine $x$, then its remaining part is assigned to start at time $T_y$ on machine $y$ with the smallest available capacity that exceeds $p_j$. The process continues with the next job. The efficient implementation of this algorithm employs a balanced search tree data structure.

As it has been shown by Shioura et al. (2018), the problem $P|pmtn, r_j, \bar{d}_j|$ with arbitrary release dates and deadlines is solved in $O(n^3)$ time through the max-flow type formulation of Horn (1974) and
the max-flow algorithm of Karzanov (1974) (see also Ahuja et al., 1994). The simplest uniform machine problem $Q|pmtn, r_j = r, \bar{d}_j = \bar{d}|-$ with common release date and common deadline is solved in $O(n+m \log m)$ time by the algorithm of Gonzales and Sahni (1978). The algorithm is a series of five procedures. If a feasible schedule exists, then it generates a feasible schedule with at most $2(m-1)$ preemptions.

Sahni and Cho (1980) presented a proof of a necessary and sufficient condition for the existence of a feasible schedule in the problem $Q|pmtn, r_j = r, \bar{d}_j|-$ with equal release dates and arbitrary deadlines. The proof is constructive and leads to an $O(nm+n \log n)$ time algorithm for this problem. The algorithm generates at most $k(m-1)+n$ preemptions, where $k$ is the number of distinct deadlines. The algorithm can be used to solve the “mirror” problem $Q|pmtn, r_j, \bar{d}_j = \bar{d}|-$ with arbitrary release dates and equal deadlines. The problem $Q|pmtn, r_j, \bar{d}_j|-$ with arbitrary release dates and deadlines is solved by a reduction to the max-flow problem in a network with $O(n)$ nodes and $O(mn^2)$ arcs (Federgruen & Groenevelt, 1986). Therefore, it can be solved in $O(mn^3)$ time by the algorithm of Karzanov (1974).

Lawler and Labetoulle (1978) reduce the unrelated machine problem $R|pmtn, r_j = r, \bar{d}_j = \bar{d}|-$ with equal release dates and equal deadlines to a linear programming problem. The respective solution has at most $O(m^2)$ preemptions. Gonzales et al. (1990) propose an $O(n)$ time algorithm for the problem $R2|pmtn, r_j = r, \bar{d}_j = \bar{d}|-$. It generates at most two preemptions. The algorithm is claimed to be generalized to solve the problem $Rm|pmtn, r_j = r, \bar{d}_j = \bar{d}|-$ in $O(n^m)$ time. For the latter case the number of preemptions is not mentioned. Dondeti and Emmons (1993) propose polynomial-time algorithms for two special cases of the linear-time problem $R|pmtn, r_j, \bar{d}_j, p_j \in \{\bar{d}_j - r_j, \infty\}, c_i^{mac}|MinCost(m)$, and adapt them for the same cases of the circular-time problem $R|circ, pmtn, r_j, \bar{d}_j, p_{ij} \in \{\bar{d}_j - r_j, \infty\}, c_i^{mac}|MinCost(m)$.

Setups. There exist studies of preemptive parallel machine scheduling problems, in which the number of preemptions is limited. These problems are decision versions of the problem $\alpha|pmtn, r_j, \bar{d}_j|MinCost(Setup)$ to minimize the number of setups because the number of setups is equal to the number of preemptions plus $n$.

Soper and Strusevich (2022) recall that the number of preemptions in an optimal schedule is at most one for $P2|pmtn|C_{max}$, and at most two for $\alpha|pmtn|C_{max}, \alpha \in \{Q2, R2\}$. In Soper and Strusevich (2019), they solve the problem $Q2|pmtn|C_{max}$ with at most one preemption in polynomial time and prove that the same problem for $R2|pmtn|C_{max}$ is NP-hard. Shchepin and Vakhania (2008) prove ordinary NP-hardness of the problem $P|pmtn|C_{max}$ with at most $m-2$ preemptions. They propose a linear programming solution approach for the problem $R|pmtn|C_{max}$ with restricted processing times and no more than $2m-3$ preemptions, and prove ordinary NP-hardness of this problem if the number of preemptions does not exceed $2m-4$.

Monma and Potts (1989) prove that the problem $P2|pmtn, s_j|C_{max}$ is NP-hard in the ordinary sense. Haned et al. (2024) prove ordinary NP-hardness of the special cases $P2|pmtn, p_j = 1, s_j|C_{max}$ and $P2|pmtn, s_j = 1|C_{max}$. They also propose an $O(\log m)$ algorithm for the problem $P|pmtn, p_j = p, s_j = s|C_{max}$, and a pseudo-polynomial dynamic programming algorithm for the problem $P2|pmtn, s_j|C_{max}$. Boudhar et al. (2024) correct this algorithm and prove strong NP-hardness of the problems $P|pmtn, p_j = 1, s_j|C_{max}$ and $P|pmtn, s_j = 1|C_{max}$. Results in this section and respective references are summarized in Table 2.

## 5.2. EV routing and preemptive charging scheduling

When considering EV charging, an important question is whether charging preemptions of the same EV are allowed or not. If they are allowed, then each preemption must be associated with a non-zero setup time and cost. Ignoring these requirements may lead to infeasible charging schedules in public transport applications because each preemption needs a worker and a time to remove a previous EV from the charger and attach a new EV to it. The setup may take several minutes, which cannot be neglected in real applications and discrete

time models such as in de Vos et al. (2024), where the time unit in test instances is set to 1, 2, 5, 10 or 30 min.

Literature on preemptive charging scheduling is scarce. We review it in chronological order. Sassi and Oulamara (2016) study a joint problem of assigning EVs and conventional vehicles to a set of fixed tours and of regular scheduling EV charging tasks in the same location. The supplied power is limited that implies a limited number of simultaneously active chargers. The primary objective is to maximize the weighted number of used EVs, and the secondary objective is to minimize the energy cost. The charging scheduling sub-problem is $P_\infty|pmtn, r_j, \bar{d}_j, W(t), c^{ene}(t)|MinCost(E)$. Fernandes et al. (2017) consider regular charging scheduling of EVs at the same charging station, subject to a constant power upper bound. Their problem can be represented as $P_\infty|pmtn, r_j = 0, \bar{d}_j, W(t) = W|-$. The only control over the charging process is to switch on or off any charger. They propose a discrete time model in which at each time instant the EVs (jobs) with the smallest time slacks $\bar{d}_j - x_j$ are charged, where $x_j$ is the remaining charging time of EV $j$.

Pelletier et al. (2018) study the problem of routing and charging scheduling electric freight vehicles. Charging is regular and the corresponding charging scheduling sub-problem is $R|pmtn, r_j, \bar{d}_j, c^{ene}(t), c^{pwr}, W(t) = W|MinCost(E, W_{max})$, in which the number of charging preemptions is limited by a given constant for each job. Liu et al. (2021) consider a limited number of chargers located in the same place for regular EV charging. They write that the EV must charge continuously within certain time intervals, but do not write whether switching between chargers is possible or not. If switching is possible then their problem can be expressed as $P|pmtn, r_j, \bar{d}_j, W(t) = W, c^{ene}(t)|MinCost(E)$ with the additional constraint of “continuous job processing”. Zaidi et al. (2023, 2024) consider regular EV charging and assume that each EV occupies its charging time window completely on the same charger, but the charging process can be interrupted and resumed at any time. In Zaidi et al. (2023), the required energy levels are flexible, and the objective is to minimize the total deviation below “ideal” energy levels. The problem does not fit into the framework of the RCSP problem. It is similar to $Q|pmtn, r_j, \bar{d}_j, p_j = \bar{d}_j - r_j, W(t) = W|-$ in Zaidi et al. (2024), the required energy levels are fixed, and the objective is to minimize the number chargers and the maximum power. The problem in Zaidi et al. (2024) is similar to $Q|pmtn, r_j, \bar{d}_j, p_j = \bar{d}_j - r_j|MinCost(m, W)$. Only Guschinsky et al. (2023) explicitly model charging preemption setup times and costs for a city electric bus application. This paper is reviewed in the next section because it deals with the circular time.

## 6. Circular time

There is a fairly rich literature on cyclic, rotating and periodic scheduling. Basic models of this kind can be found in Baker (1976), Serafini and Ukovich (1989), Laporte (1999) and Brucker and Kampmeyer (2008). However, we have not found publications on scheduling with circular time, with the exception of Dondeti and Emmons (1993) who proposed polynomial-time algorithms for two special cases of the circular-time problem $R|circ, pmtn, r_j, \bar{d}_j, p_j \in \{\bar{d}_j - r_j, \infty\}, c_i^{mac}|MinCost(m)$, and Guschinsky et al. (2023), whose charging scheduling sub-problem can be expressed as $P_\infty|circ, pmtn, r_j, \bar{d}_j, s_{ij} = s, c_i^{mac} = c^{mac}, c_{ij}^{set} = c^{set}|MinCost(m, Setup)$.

There are results on coloring circular-arc graphs that are relevant to the non-preemptive problems $P|circ, r_j, \bar{d}_j, p_j = \bar{d}_j - r_j|$- and $P_\infty|circ, r_j, \bar{d}_j, p_j = \bar{d}_j - r_j, c^{mac} = c^{mac}|MinCost(m)$. The circular-arc graph coloring problem, which we denote as CAGC, is to find a minimum number of colors for a set of open arcs on a circle so that overlapping arcs have different colors. Arcs correspond to the nodes and any two overlapping arcs correspond to an edge in the respective circular-arc graph. In charging scheduling applications, open charging time window $(r_j, \bar{d}_j)$ plays the role of the open arc, arcs colored with the same color represent jobs assigned to the same machine, and the number of legally used colors equals the number of active machines.
<table><caption>**Table 2**
Linear time and preemptions: computational complexity and number of preemptions.</caption><thead><tr><th>Problem</th><th>Complexity, algorithm</th><th>#<sub>pmtn</sub> (number of preemptions)</th><th>Reference</th></tr></thead><tbody><tr><td>1|<sub>pmtn</sub>, r<sub>j</sub> = r, <span style="text-decoration: overline;">d</span><sub>j</sub>|-</td><td>O(n log n), EDF rule</td><td>0</td><td>Moore (1968)</td></tr><tr><td>1|<sub>pmtn</sub>, r<sub>j</sub>, <span style="text-decoration: overline;">d</span><sub>j</sub>|-</td><td>O(n<sup>2</sup>), EDF rule</td><td>n - 1</td><td>Horn (1974)</td></tr><tr><td>1|<sub>pmtn</sub>, r<sub>j</sub>, <span style="text-decoration: overline;">d</span><sub>j</sub>|-</td><td>O(n log n), EDF rule + data structure</td><td>n - 1</td><td>Kim (1994), Schwan and Zhou (1992)</td></tr><tr><td>P|<sub>pmtn</sub>, r<sub>j</sub> = r<sub>j</sub>, <span style="text-decoration: overline;">d</span><sub>j</sub> = <span style="text-decoration: overline;">d</span>|-</td><td>O(n), Wrap Around rule</td><td>max{m-1, n-2}</td><td>McNaughton (1959)</td></tr><tr><td>P|<sub>pmtn</sub>, r<sub>j</sub> = r, <span style="text-decoration: overline;">d</span><sub>j</sub> = <span style="text-decoration: overline;">d</span>|-</td><td>O(n log nm), EDF rule + data structure</td><td>unknown</td><td>Sahni (1979)</td></tr><tr><td>P|<sub>pmtn</sub>, r<sub>j</sub>, <span style="text-decoration: overline;">d</span><sub>j</sub> = <span style="text-decoration: overline;">d</span>|-</td><td>O(n log nm), EDF rule + data structure</td><td>unknown</td><td>Sahni (1979)</td></tr><tr><td>P|<sub>pmtn</sub>, r<sub>j</sub>, <span style="text-decoration: overline;">d</span><sub>j</sub>|-</td><td>O(n<sup>3</sup>), max-flow</td><td>unknown</td><td>Shioura et al. (2018)</td></tr><tr><td>Q|<sub>pmtn</sub>, r<sub>j</sub> = r, <span style="text-decoration: overline;">d</span><sub>j</sub> = <span style="text-decoration: overline;">d</span>|-</td><td>O(n + m log m), series of procedures</td><td>2(m - 1)</td><td>Gonzales and Sahni (1978)</td></tr><tr><td>Q|<sub>pmtn</sub>, r<sub>j</sub> = r, <span style="text-decoration: overline;">d</span><sub>j</sub> = <span style="text-decoration: overline;">d</span>|-</td><td>O(mn + n log n), feasibility conditions</td><td>k(m - 1) + n</td><td>Sahni and Cho (1980)</td></tr><tr><td>Q|<sub>pmtn</sub>, r<sub>j</sub>, <span style="text-decoration: overline;">d</span><sub>j</sub> = <span style="text-decoration: overline;">d</span>|-</td><td>O(mn + n log n), feasibility conditions</td><td>k(m - 1) + n</td><td>Sahni and Cho (1980)</td></tr><tr><td>Q|<sub>pmtn</sub>, r<sub>j</sub>, <span style="text-decoration: overline;">d</span><sub>j</sub>|-</td><td>O(mn<sup>3</sup>), max-flow</td><td>unknown</td><td>Federgruen and Groenevelt (1986), Karzanov (1974)</td></tr><tr><td>Q2|<sub>pmtn</sub>, #<sub>pmtn</sub> ≤ 1|C<sub>max</sub></td><td>polynomial</td><td>1</td><td>Soper and Strusevich (2019)</td></tr><tr><td>R2|<sub>pmtn</sub>, #<sub>pmtn</sub> ≤ 1|C<sub>max</sub></td><td>strongly NP-hard</td><td>1</td><td>Soper and Strusevich (2019)</td></tr><tr><td>R1|<sub>pmtn</sub>, r<sub>j</sub> = r, <span style="text-decoration: overline;">d</span><sub>j</sub> = <span style="text-decoration: overline;">d</span>|-</td><td>polynomial, LP</td><td>O(m<sup>2</sup>)</td><td>Lawler and Labetoulle (1978)</td></tr><tr><td>R2|<sub>pmtn</sub>, r<sub>j</sub> = r, <span style="text-decoration: overline;">d</span><sub>j</sub> = <span style="text-decoration: overline;">d</span>|-</td><td>O(n)</td><td>2</td><td>Gonzales et al. (1990)</td></tr><tr><td>Special cases of R|<sub>pmtn</sub>, r<sub>j</sub>, <span style="text-decoration: overline;">d</span><sub>j</sub>, p<sub>j</sub> ∈ {<span style="text-decoration: overline;">d</span><sub>j</sub> - r<sub>j</sub>, ∞}, c<sup>mac</sup><sub>i</sub> | MinCost(m)</td><td>polynomial</td><td>unknown</td><td>Dondeti and Emmons (1993)</td></tr></tbody></table>

We denote the number of nodes and edges in a circular-arc graph as $n$ and $g$, respectively. Garey et al. (1980) proved that CAGC is NP-hard in the strong sense, implying strong NP-hardness of the above charging scheduling problems. If no edge is contained in another edge, then CAGC can be solved in $O(n^{1.5})$ time using the algorithm of Shih and Hsu (1989) and Teng and Tucker (1985). Gargano and Rescigno (2000) describe a polynomially solvable special case of CAGC, in which chromatic number of the circular-arc graph is equal to the maximum number of arcs intersecting at the same point. Chen et al. (2005) propose an $(gn^2)$ time algorithm if the circular-arc graph is perfect (which is not the case in general).

Integer linear programming models with consecutive ones and circular ones constraints can be appropriate for the problems $a|<sub>circ</sub>, r_j, <span style="text-decoration: overline;">d</span><sub>j</sub>|\gamma$ if time is discrete and time-indexed variables are used. Constraint names reflect the structure of the constraint matrix. For a charging scheduling problem $P|<sub>circ</sub>, r_j, <span style="text-decoration: overline;">d</span><sub>j</sub>|\gamma$, introduce 0–1 variables $x_{jt}$ such that $x_{jt} = 1$ if and only if job $j$ is processed in the unit-time interval $t$. Recall that the time circle is denoted as $[0, T]$ where 0 and $T$ are the same time point. We shall assume that the time units are $1, \dots, T$. If $T \notin (r_j, \bar{d}_j)$, then the consecutive ones covering constraint $\sum_{t=r_j}^{\bar{d}_j} x_{jt} \ge p_j$ must be satisfied for each job $j$, among other constraints. Else if $T \in (r_j, \bar{d}_j)$, then the circular ones covering constraint $\sum_{t=r_j}^{T} x_{jt} + \sum_{t=1}^{\bar{d}_j} x_{jt} \ge p_j$ must be satisfied for each job. Optimization problems with consecutive ones and circular ones constraints have been studied by Bartholdi et al. (1980), Gijswijt (2005) and Hochbaum and Levin (2006a, 2006b).

Mixed Integer Linear Programming models are the most popular instrument to solve charging scheduling problems. For circular time, we know only one MILP model, proposed by Guschinsky et al. (2023) for a special case of the problem with regular charging, which can be described as $P_\infty|<sub>circ</sub>, pmtn, r_j, <span style="text-decoration: overline;">d</span><sub>j</sub>, s_{ij} = s_j, c_i^{mac} = c^{mac}, c_i^{set} = c_j^{set}, c^{ene}(t), w_i = w, W(t)|MinCost(m, E, Setup)$. The model uses event-based variables.

## 7. Conclusions and challenges

Our review shows that studies of deterministic EV routing and charging scheduling problems are a popular topic in contemporary

transportation research. Many charging scheduling studies are inspired by real city electric bus applications with specific assumptions, constraints and decision preferences. They often ignore or reinvent existing computational complexity results, classical models and algorithms for parallel machine scheduling with job release dates and deadlines. On the other hand, charging specificity is rarely addressed in machine scheduling research. We hope that this paper will be a useful source of information and a stimulus for future research for both the EV operation planning and machine scheduling communities.

A limited number of studies assume capacitated or preemptive charging, and charging with preemption setups. These assumptions are natural and must be taken into account in order to reduce charging costs and minimize energy and power consumption for practical cases. Insufficient attention has been paid to scheduling with circular time. Circular time model is adequate for charging city electric buses due to its recurrent nature. Development of efficient mathematical models and algorithms for parallel machine scheduling problems with penalized or limited preemptions, circular time, energy and power constraints is essential for charging scheduling applications, and it is of interest for future research.

The main challenge is the computational complexity of practical charging scheduling problems. Instances with hundreds of charging tasks and up to ten chargers are often impossible to solve in a reasonable time frame. Therefore, there is a need for efficient mathematical programming models and algorithms able to solve practical-size instances. Another important challenge is the input data uncertainty. As EVs are used, more numerical data becomes available, providing a basis for the development of robust, stochastic, statistical and machine learning approaches for solving complex uncertain charging scheduling problems. A charging re-scheduling problem naturally arises when the fixed timetable of EVs changes. This important problem has never been studied in the charging scheduling literature and therefore represents a promising future research direction.

The proposed classification scheme is intended for regular charging. It does not directly concern problems with irregular charging. In the latter problems, deadheading for charging or charging itself is part of a
decision, which means that a set of the charging tasks is not given, as assumed in the classical scheduling models, but must be decided such that the overall solution is feasible and cost optimal, including deadheading and charger usage cost. It might also be the case that an EV can be charged more than once and in different places during the same trip. In this case, charging times and energy levels become decision variables, although they are fixed in the proposed classification scheme. These and other practical characteristics represent gaps in the current scheduling research that need to be filled in the future.

### CRediT authorship contribution statement

**Alexandre Dolgui:** Validation, Formal analysis, Conceptualization.
**Sergey Kovalev:** Writing – review & editing, Writing – original draft, Methodology, Formal analysis.
**Mikhail Y. Kovalyov:** Writing – review & editing, Writing – original draft, Resources, Methodology, Formal analysis, Conceptualization.

### References

Abdelwahed, A., van den Berg, P. L., Brandt, T., Collins, J., & Ketter, W. (2020). Evaluating and optimizing opportunity fast-charging schedules in transit battery electric bus networks. *Transportation Science*, *54*, 1601–1615.

Adler, J. D. (2014). *Routing and scheduling of electric and alternative-fuel vehicles*. (Ph.D. thesis), Arizona State University.

Adler, J. D., & Mirchandani, P. B. (2017). The vehicle scheduling problem for fleets with alternative-fuel vehicles. *Transportation Science*, *51*(2), 441–456.

Ahuja, R. K., Orlin, J. B., Stein, C., & Tarjan, R. E. (1994). Improved algorithms for bipartite network flow. *SIAM Journal on Computing*, *23*, 906–933.

Alam Md, R., & Guo, Z. (2023). Co-optimization of charging scheduling and platooning for long-haul electric freight vehicles. *Transportation Research Part C (Emerging Technologies)*, *147*, Article 104009.

Alvo, M., Angulo, G., & Klapp, M. A. (2021). An exact solution approach for an electric bus dispatch problem. *Transportation Research Part E: Logistics and Transportation Review*, *156*, Article 102528.

An, Y., Gao, Y., Wu, N., Zhu, J., Li, H., & Yang, J. (2023). Optimal scheduling of electric vehicle charging operations considering real-time traffic condition and travel distance. *Expert Systems with Applications*, *213*, Article 118941.

Angel, E., Bampis, E., & Chau, V. (2014). Low complexity scheduling algorithms minimizing the energy for tasks with agreeable deadlines. *Discrete Applied Mathematics*, *175*, 1–10.

Baker, K. R. (1976). Workforce allocation in cyclical scheduling problems: a survey. *Journal of the Operational Research Society*, *27*(1), 155–167.

Baker, K. R., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1983). Preemptive scheduling of a single machine to minimize maximum cost subject to release dates and precedence constraints. *Operations Research*, *26*, 111–120.

Bartholdi, J. J., Orlin, J. B., & Ratliff, H. D. (1980). Cyclic scheduling via integer programs with circular ones. *Operations Research*, *28*, 1074–1085.

Battaia, O., Dolgui, A., Guschinsky, N., & Kovalyov, M. Y. (2023). Designing fast-charge urban electric bus services: An integer linear programming model. *Transportation Research Part E: Logistics and Transportation Review*, *171*, Article 103065.

Boccia, M., Masone, A., Sterle, C., & Murino, T. (2023). The parallel AGV scheduling problem with battery constraints: A new formulation and aetheuristic approach. *European Journal of Operational Research*, *307*, 590–603.

Boudhar, M., Dolgui, A., Haned, A., Kerdali, A., Kovalev, S., & Kovalyov, M. Y. (2024). A note on scheduling identical parallel machines with preemptions and setup times. *International Journal of Production Research*, 1–6. http://dx.doi.org/10.1080/00207543.2024.2362414.

Bragin, M. A., Ye, Z., & Yu, N. (2024). Toward efficient transportation electrification of heavy-duty trucks: Joint scheduling of truck routing and charging. *Transportation Research Part C (Emerging Technologies)*, *160*, Article 104494.

Brauner, N., Kovalyov, M. Y., Quilliot, A., & Toussaint, H. (2021). No-idle parallel-machine scheduling of unit-time jobs with a small number of distinct release dates and deadlines. *Computers & Operations Research*, *132*, Article 105315.

Brucker, P., & Kampmeyer, T. (2008). A general model for cyclic machine scheduling problems. *Discrete Applied Mathematics*, *156*(13), 2561–2572.

Brucker, P., & Shakhlevich, N. V. (2016). Necessary and sufficient optimality conditions for scheduling unit time jobs on identical parallel machines. *Journal of Scheduling*, *19*, 659–685.

Bruglieri, M., Mancini, S., & Pisacane, O. (2019). The green vehicle routing problem with capacitated alternative fuel stations. *Computers & Operations Research*, *112*, Article 104759.

Bruglieri, M., Mancini, S., & Pisacane, O. (2021). A more efficient cutting planes approach for the green vehicle routing problem with capacitated alternative fuel stations. *Optimization Letters*, *15*(8), 2813–2829.

Chen, X., Hu, Z., & Zhang, W. (2005). Perfect circular arc coloring. *Journal of Combinatorial Optimization*, *9*, 267–280.

Chen, H., Hu, Z., Zhang, H., & Luo, H. (2018). Coordinated charging and discharging strategies for plug-in electric bus fast charging station with energy storage system. *IET Generation, Transmission & Distribution*, *12*(9), 2019–2028.

Chen, X., Kovalev, S., Sterna, M., & Blazewicz, J. (2021). Mirror scheduling problems with early work and late work criteria. *Journal of Scheduling*, *24*(5), 483–487.

de Vos, M. H., van Lieshout, R. N., & Dollevoet, T. (2024). Electric vehicle scheduling in public transit with capacitated charging stations. *Transportation Science*, *58*(2), 279–294.

Demaine, E. D., Ghodsi, M., Hajiaghyi, M., Sayedi-Roshkhar, A. S., & Zadimoghadam, M. (2013). Scheduling to minimize gaps and power consumption. *Journal of Scheduling*, *16*, 151–160.

Dessouky, M. I., Lageweg, B. J., Lenstra, J. K., & van de Velde, S. L. (1990). Scheduling identical jobs on uniform parallel machines. *Statistica Neerlandica*, *44*, 115–123.

Diefenbach, H., Emde, S., & Glock, C. H. (2023). Multi-depot electric vehicle scheduling in in-plant production logistics considering non-linear charging models. *European Journal of Operational Research*, *306*, 828–848.

Dondeti, V. R., & Emmons, H. (1993). Algorithms for preemptive scheduling of different classes of processors to do jobs with fixed times. *European Journal of Operational Research*, *70*, 316–326.

Dourado, M. C., de Freitas Rodrigues, R., & Szwarcfiter, J. L. (2009). Scheduling unit time jobs with integer release dates to minimize the weighted number of tardy jobs. *Annals of Operations Research*, *169*, 81–91.

Duan, M., Liao, F., Qi, G., & Guan, W. (2023). Integrated optimization of electric bus scheduling and charging planning incorporating flexible charging and timetable shifting strategies. *Transportation Research Part C (Emerging Technologies)*, *152*, Article 104175.

Federgruen, A., & Groenevelt, H. (1986). Preemptive scheduling of uniform machines by ordinary network flow techniques. *Management Science*, *32*(3), 341–349.

Fernandes, X., Rebelo, J., Gouveia, J., Maia, R., & Silva, N. B. (2017). On-off scheduling schemes for power-constrained electric vehicle charging. *4OR. A Quarterly Journal of Operations Research*, *15*, 163–181.

Ferro, G., Paolucci, M., & Robba, M. (2020). Optimal charging and routing of electric vehicles with power constraints and time-of-use energy prices. *IEEE Transactions on Vehicular Technology*, *69*(12), 14436–14447.

Froger, A., Jabali, O., Mendoza, J. E., & Laporte, G. (2022). The electric vehicle routing problem with capacitated charging stations. *Transportation Science*, *56*(2), 460–482.

Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. In *Freeman*. San Francisco.

Garey, M. R., Johnson, D. S., Miller, G. L., & Papadimitriou, C. H. (1980). The complexity of coloring circular arcs and chords. *SIAM Journal on Algebraic Discrete Methods*, *1*, 217–227.

Garey, M. R., Johnson, D. S., Simons, B. B., & Tarjan, R. E. (1981). Scheduling unit-time tasks with arbitrary release times and deadlines. *SIAM Journal on Computing*, *10*, 256–269.

Gargano, L., & Rescigno, A. (2000). Coloring circular arcs with applications to WDM routing. In *Proc. of Workshop on Approximation and Randomization Algorithms in Communication Networks*. Switzerland: Geneva.

Gijswijt, D. (2005). Integer decomposition for polyhedra defined by nearly totally unimodular matrices. *SIAM Journal on Discrete Mathematics*, *19*(3), 798–806.

Gkiotsalitis, K., Iliopoulou, C., & Kepapsoglou, K. (2023). An exact approach for the multi-depot electric bus scheduling problem with time windows. *European Journal of Operational Research*, *306*(1), 189–206.

Goeke, D., & Schneider, M. (2015). Routing a mixed fleet of electric and conventional vehicles. *European Journal of Operational Research*, *245*(1), 81–99.

Gonzales, T. F., Lawler, E. L., & Sahni, S. (1990). Optimal preemptive scheduling of two unrelated processors. *ORSA Journal on Computing*, *2*(3), 219–224.

Gonzales, T. F., & Sahni, S. (1978). Preemptive scheduling of uniform processor systems. *Journal of the ACM*, *25*, 92–101.

Guschinsky, N., Kovalyov, M. Y., Pesch, E., & Rozin, B. (2023). Cost minimizing decisions on equipment and charging schedule for electric buses in a single depot. *Transportation Research Part E: Logistics and Transportation Review*, *180*, Article 103337.

Haned, A., Kerdali, A., & Boudhar, M. (2024). Scheduling on identical machines with preemption and setup times. *International Journal of Production Research*, *62*(1-2), 444–459.

Havre, H. F., Lien, U., Ness, M. M., Fagerholt, K., & Rø dseth, K. L. (2024). Network design with route planning for battery electric high-speed passenger vessel services. *European Journal of Operational Research*, *315*(1), 102–119.

He, Y., Liu, Z., & Song, Z. (2020). Optimal charging scheduling and management for a fast-charging battery electric bus system. *Transportation Research Part E: Logistics and Transportation Review*, *142*, Article 102056.

He J. Yan, N., Zhang J., Wang, T., Chen, Y.-Y., & Tang, T.-Q. (2023). Battery electricity bus charging schedule considering bus journey's energy consumption estimation. *Transportation Research, Part D*, *115*, Article 103587.

Hernández-Arauzo, A., Puente, J., Varela, R., & Sedano, J. (2015). Electric vehicle charging under power and balance constraints as dynamic scheduling. *Computers & Industrial Engineering*, *85*, 306–315.
Hochbaum, D. S., & Levin, A. (2006a). Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms. *Discrete Optimization*, **3**, 327–340.

Hochbaum, D. S., & Levin, A. (2006b). Optimizing over consecutive 1's and circular 1's constraints. *SIAM Journal on Optimization*, **17**(2), 311–330.

Horn, W. A. (1974). Some simple scheduling algorithms. *Naval Research Logistics Quarterly*, **21**, 177–185.

Janovec, M., & ani, M. Kohr. (2019). Exact approach to the electric bus fleet scheduling. *Transportation Research Procedia*, **40**, 1380–1387.

Ji, J., Bie, Y., & Wang, L. (2023). Optimal electric bus fleet scheduling for a route with charging facility sharing. *Transportation Research Part C (Emerging Technologies)*, **147**, Article 104010.

Karzanov, A. V. (1974). Determining the maximal flow in a network by the method of preflows. *Dokladi Akademii Nauk SSSR*, **15**, 434–437.

Kim, Y.-S. (1994). An optimal scheduling algorithm for preemptable real-time tasks. *Information Processing Letters*, **50**, 43–48.

Kolen, W. J. A., Lenstra, J. K., Papadimitriou, C. H., & Spieksma, F. C. R. (2007). Interval scheduling: A survey. *Naval Research Logistics*, **54**, 530–543.

van Kooten Niekerk, M. E., van den Akker, J. M., & Hoogeveen, J. A. (2017). Scheduling electric vehicles. *Public Transportation*, **9**, 155–176.

Kovaliyov, M. Y., Ng, C. T., & Cheng, T. C. E. (2007). Fixed interval scheduling: Models, applications, computational complexity and algorithms. *European Journal of Operational Research*, **178**, 331–342.

Kravchenko, S., & Werner, F. (2011). Parallel machine problems with equal processing times: A survey. *Journal of Scheduling*, **14**, 435–444.

Kullman, N. D., Froger, A., Mendoza, J. E., & Goodson, J. C. (2021). Frvcp: An open-source solver for the fixed route vehicle charging problem. *INFORMS Journal on Computing*, **33**(4), 1277–1283.

Lai, Z., & Li, S. (2024). Towards a multimodal charging network: Joint planning of charging stations and battery swapping stations for electrified ride-hailing fleets. *Transportation Research Part B (Methodological)*, **183**, Article 102928.

Lam, E., Desaulniers, G., & Stuckey, P. J. (2022). Branch-and-cut-and-price for the electric vehicle routing problem with time windows, piecewise-linear recharging and capacitated recharging stations. *Computers & Operations Research*, **145**, Article 105870.

Laporte, G. (1999). The art and science of designing rotating schedules. *Journal of the Operational Research Society*, **50**(10), 1011–1017.

Lawler, E. L. (1994). Knapsack-like scheduling problems, the Moore-Hodgson algorithm and the tower of sets property. *Mathematical and Computer Modelling*, **20**, 91–106.

Lawler, E. L., & Labetoulle, J. (1978). On preemptive scheduling of unrelated parallel processors by linear programming. *Journal of the ACM*, **25**(4), 612–619.

Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977). Complexity of machine scheduling problems. *Annals of Discrete Mathematics*, **1**, 343–362.

Lenstra, J. K., Shmoys, D. B., & Tardos, E. (1990). Approximation algorithms for scheduling unrelated parallel machines. *Mathematical Programming*, **46**, 259–271.

Leou, R. C., & Hung, J. J. (2017). Optimal charging schedule planning and economic analysis for electric bus charging stations. *Energies*, **10**(4), 483.

Lera-Romero, G., Miranda Bront, J. J., & Soulignac, F. J. (2024). A branch-cut-and-price algorithm for the time-dependent electric vehicle routing problem with time windows. *European Journal of Operational Research*, **312**(3), 978–995.

Li, J. Q. (2014). Transit bus scheduling with limited energy. *Transportation Research*, **48**(4), 521–539.

Li, L., Lo, H. K., & Xiao, F. (2019). Mixed bus fleet scheduling under range and refueling constraints. *Transportation Research Part C (Emerging Technologies)*, **104**, 443–462.

Li, X., Wang, T., Li, L., Feng, F., Wang, W., & Cheng, C. (2020). Joint optimization of regular charging electric bus transit network schedule and stationary charger deployment considering partial charging policy and time-of-use electricity prices. *Journal of Advanced Transportation*, Article 8863905.

Lin, Y., & Li, W. (2004). Parallel machine scheduling of machine-dependent jobs with unit-length. *European Journal of Operational Research*, **156**, 261–266.

Liu, T., & Ceder, A. A. (2020). Battery-electric transit vehicle scheduling with optimal number of stationary chargers. *Transportation Research Part C (Emerging Technologies)*, **114**, 118–139.

Liu, K., Gao, H., Liang, Z., Zhao, M., & Li, C. (2021). Optimal charging strategy for large-scale electric buses considering resource constraints. *Transportation Research Part D: Transport and Environment*, **99**, Article 103009.

Mahmutogullari, Ö., & Yaman, H. (2023). Robust alternative fuel refueling station location problem with routing under decision-dependent flow uncertainty. *European Journal of Operational Research*, **306**(1), 173–188.

Mahyari, E., Freeman, N., & Yavuz, M. (2023). Combining predictive and prescriptive techniques for optimizing electric vehicle fleet charging. *Transportation Research Part C (Emerging Technologies)*, **152**, Article 104149.

Mak, H.-Y., Rong, Y., & Shen, Z.-J. M. (2013). Infrastructure planning for electric vehicles with battery swapping. *Management Science*, **59**, 1557–1575.

Masone, A., Murino, T., Sterle, C., & Strazzullo, M. (2021). A MILP formulation for an automated guided vehicle scheduling problem with battery constraints. In A. Dolgui, A. Bernard, D. Lemoine, G. von Cieminski, & D. Romero (Eds.), *Advances in Production Management Systems. Artificial Intelligence for Sustainable and Resilient Production Systems* (pp. 15–23). Cham: Springer International Publishing.

McNaughton, R. (1959). Scheduling with deadlines and loss functions. *Management Science*, **6**, 1–12.

Monca, C. L., & Potts, C. N. (1989). On the complexity of scheduling with batch setup time. *Operations Research*, **37**(5), 798–804.

Montoya, A., eret, C. Gu, Mendoza, J. E., & Villegas, J. G. (2017). The electric vehicle routing problem with nonlinear charging function. *Transportation Research Part B*, **103**, 87–110.

Moore, J. M. (1968). An n job, one machine sequencing algorithm for minimize the number of late jobs. *Management Science*, **15**(1), 102–109.

Muir, C., & Toriello, A. (2023). Interval scheduling with economies of scale. *Computers & Operations Research*, **150**, Article 106056.

Nguyen, N.-Q., Yalaoui, F., Amodeo, L., Chehade, H., & Toggenburger, P. (2018). Total completion time minimization for machine scheduling problem under time windows constraints with jobs' linear processing rate function. *Computers & Operations Research*, **90**, 110–124.

Nolz, P. C., Absi, D., & Seragiotto, C. (2022). The consistent electric-vehicle routing problem with backhauls and charging management. *European Journal of Operational Research*, **302**(2), 700–716.

Olsen, N., & Kliewer, N. (2020). Scheduling electric buses in public transport: Modeling of the charging process and analysis of assumptions. *Logistics Research*, **13**(1), 4.

Olsen, N., Kliewer, N., & Wolbeck, L. (2022). A study on flow decomposition methods for scheduling of electric buses in public transport based on aggregated time-space network models. *Central European Journal of Operations Research*, **30**, 883–919.

Park, H., & Lee, C. (2024). An exact algorithm for maximum electric vehicle flow coverage problem with heterogeneous chargers, nonlinear charging time and route deviations. *European Journal of Operational Research*, **315**(3), 926–951.

Pelletier, S., Jabali, O., & Laporte, G. (2018). Charge scheduling for electric freight vehicles. *Transportation Research, Part B (Methodological)*, **115**, 246–269.

Perumal, S. S. G., Lusby, R. M., & Larsen, J. (2022). Electric bus planning & scheduling: A review of related problems and methodologies. *European Journal of Operational Research*, **301**, 395–413.

Rinaldi, M., Picarelli, E., D'Ariano, A., & Viti, F. (2020). Mixed-fleet single-terminal bus scheduling problem: Modelling, solution scheme and potential applications. *Omega*, **96**, Article 102070.

Rogge, M., van der Hurk, E., Larsen, A., & Sauer, D. U. (2018). Electric bus fleet size and mix problem with optimization of charging infrastructure. *Applied Energy*, **211**, 282–295.

Sahni, S. (1979). Preemptive scheduling with due dates. *Operations Research*, **27**(5), 925–934.

Sahni, S., & Cho, Y. (1980). Scheduling independent tasks with due times on a uniform processor system. *Journal of the ACM*, **27**, 550–563.

Sassi, O., & Oulamara, A. (2016). Electric vehicle scheduling and optimal charging problem: complexity, exact and heuristic approaches. *International Journal of Production Research*, **55**(2), 519–535.

Scholl, J., Boysen, N., & Scholl, A. (2023). E-platooning: Optimizing platoon formation for long-haul transportation with electric commercial vehicles. *European Journal of Operational Research*, **304**(2), 525–542.

Schwan, K., & Zhou, H. (1992). Dynamic scheduling of hard real-time tasks and real-time threads. *IEEE Transcations on Software Engineering*, **18**(8), 736–748.

Serafini, P., & Ukovich, W. (1989). A mathematical model for periodic scheduling problems. *SIAM Journal on Discrete Mathematics*, **2**(4), 550–581.

Schchepin, E., & Vakhania, N. (2008). On the geometry, preemptions and complexity of multiprocessor and shop scheduling. *Annals of Operations Research*, **159**, 183–213.

Shih, W.-K., & Hsu, W.-L. (1989). An *O(n<sup>1.5</sup>)* algorithm to color proper circular arcs. *Discrete Applied Mathematics*, **25**, 321–323.

Shioura, A., Shakhlevich, N. V., & Strusevich, V. A. (2018). Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: A review of solution approaches. *European Journal of Operational Research*, **266**, 795–818.

Simons, B. B., & Warmuth, M. K. (1989). A fast algorithm for multiprocessor scheduling of unit-length jobs. *SIAM Journal on Computing*, **18**, 690–710.

Soper, A. J., & Strusevich, V. A. (2019). Schedules with a single preemption on uniform parallel machines. *Discrete Applied Mathematics*, **261**, 332–343.

Soper, A. J., & Strusevich, V. A. (2022). Preemptive and non-preemptive scheduling on two unrelated parallel machines. *Journal of Scheduling*, **25**, 659–674.

Su, Y., Dupin, N., & Puchinger, J. (2023). A deterministic annealing local search for the electric autonomous dial-a-ride problem. *European Journal of Operational Research*, **309**(3), 1091–1111.

Tang, X., Lin, X., & He, F. (2019). Robust scheduling strategies of electric buses under stochastic traffic conditions. *Transportation Research Part C (Emerging Technologies)*, **105**, 163–182.

Teng, A., & Tucker, A. (1985). An *O(qn)* algorithm to q-color a proper family of circular arcs. *Discrete Mathematics*, **55**, 233–243.

Vakhania, N., Hernandez, J. A., & Werner, F. (2014). Scheduling unrelated machines with two types of jobs. *International Journal of Production Research*, **52**(13), 1–9.

van Oosterom, S., Mitici, M., & Hoekstra, J. (2023). Dispatching a fleet of electric towing vehicles for aircraft taxiing with conflict avoidance and efficient battery charging. *Transportation Research Part C (Emerging Technologies)*, **147**, Article 103995.

Verma, A. (2018). Electric vehicle routing problem with time windows, recharging stations and battery swapping stations. *EURO Journal on Transportation Logistics*, **7**, 415–451.
Vichitkunakorn, P., Emde, S., Masae, M., Glock, C. H., & Grosse, E. H. (2024). Locating charging stations and routing drones for efficient automated stocktaking. *European Journal of Operational Research*, In press.

Wang, Y., Huang, Y., Xu, J., & Barclay, N. (2017). Optimal recharging scheduling for urban electric buses: A case study in davis. *Transportation Research Part E: Logistics and Transportation Review, 100*, 115-132.

Wang, W., & Zhao, J. (2023). Partial linear recharging strategy for the electric fleet size and mix vehicle routing problem with time windows and recharging stations. *European Journal of Operational Research, 308*(2), 929-948.

Wen, M., Linde, E., Ropke, S., Mirchandani, P., & Larsen, A. (2016). An adaptive large neighborhood search heuristic for the electric vehicle scheduling problem. *Computers & Operations Research, 76*, 73-83.

Wu, W., Lin, Y., Liu, R., & Jin, W. (2022). The multi-depot electric vehicle scheduling problem with power grid characteristics. *Transportation Research, Part B (Methodological)*, 155, 322-347.

Yan, P., Yu, K., Chao, X., & Chen, Z. (2023). An online reinforcement learning approach to charging and order-dispatching optimization for an e-hailing electric vehicle fleet. *European Journal of Operational Research, 310*(3), 1218-1233.

Yao, E., Liu, T., Lu, T., & Yang, Y. (2020). Optimization of electric vehicle scheduling with multiple vehicle types in public transport. *Sustainable Cities & Society, 52*, Article 101862.

Zaidi, I., Oulamara, A., Idoumghar, L., & Basset, M. (2023). Electric vehicle charging scheduling problem: Heuristics and metaheuristic approaches. *SN Computer Science, 4*(283).

Zaidi, I., Oulamara, A., Idoumghar, L., & Basset, M. (2024). Minimizing grid capacity in preemptive electric vehicle charging orchestration: Complexity, exact and heuristic approaches. *European Journal of Operational Research, 312*(1), 22-37.

Zhang, L., Wang, S., & Qu, X. (2021). Optimal electric bus fleet scheduling considering battery degradation and non-linear charging profile. *Transportation Research Part E: Logistics and Transportation Review, 154*, Article 102445.

Zhou, Y., Meng, Q., & Ong, G. P. (2022). Electric bus charging scheduling for a single public transport route considering nonlinear charging profile and battery degradation effect. *Transportation Research, Part B (Methodological)*, 159, 49-75.

Zhou, Y., Meng, Q., Ong, G. P., & Wang, H. (2024). Electric bus charging scheduling on a bus network. *Transportation Research Part C (Emerging Technologies)*, 161, Article 104553.

Zhou, G. J., Xie, D. F., Zhao, X. M., & Lu, C. R. (2020). Collaborative optimization of vehicle and charging scheduling for a bus fleet mixed with electric and traditional buses. *IEEE Access, 8*, 8056-8072.