Evolutionary one-machine scheduling in the context of electric vehicles charging

Abstract

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

Keywords

Scheduling one machine scheduling electric vehicles charging genetic algorithm local search

1. Introduction

Scheduling problems have received a considerable attention over the last decades, due to their wide range of practical applications and their high computational complexity (these are often NP-hard [1]). As a result, numerous scheduling problems with different constraints and objective functions have been studied in the literature, and a considerable number of solving methods have been proposed as well. A large body of research in scheduling has focused on one machine scheduling problems, in which a set of jobs must be scheduled on a single machine. This family of scheduling problems stands out due to having simple formulations and for serving as building blocks in the resolution of other more general problems. Sometimes, one machine scheduling problems appear as natural relaxations of more complex problems and so they are useful to obtain lower bounds [2]; while in other situations the resolution of a scheduling problem may be reduced to solving a number of instances of some one machine scheduling problem [3]. The latter is the case of the problem considered in this paper, in which a number of jobs must be scheduled on a single machine with capacity to process more than one job at a time, but with this capacity varying over time, with the goal of minimizing total tardiness. It was introduced in [4] in the context of scheduling the charging times of a large fleet of Electric Vehicles (EVs).

This problem may be denoted as $(1,\textit{Cap}(t)\|\sum T_{i})$ in the conventional $(\alpha|\beta|\gamma)$ notation proposed in [5]. In [4] it was solved by means of the well-known apparent tardiness cost priority rule (ATC), which is usually exploited to solve scheduling problems with tardiness minimization objective functions.

Recently, in [6] a genetic algorithm (GA) was proposed for solving the $(1,\textit{Cap}(t)\|\sum T_{i})$ problem. This algorithm exploits a schedule builder proposed therein in its decoding phase, which allows for restricting the search to the subset of the so-called left-shifted schedules. Although more time consuming than priority rules, the GA was shown to compute better solutions, while keeping the running times reasonably low.

Genetic algorithms constitute a representative example of population-based evolutionary algorithms, and are at the core of several other successful metaheuristics, such as memetic algorithms [7], that hybridize genetic algorithms and local search, or cultural algorithms [8], that extend genetic algorithms with a belief space shared by all the individuals and updated along the search process.

In this paper, we build on the work in [6] and extend it substantially towards solving the $(1,\textit{Cap}(t)\|\sum T_{i})$ problem efficiently.

The main original contribution in the paper is the development of a memetic algorithm that combines the GA with a local improvement algorithm that is also proposed in the paper. The local search method exploits a neighborhood structure that is studied in detail, as well as an efficient condition for improvement that makes it very efficient in practice. The results from an experimental study report significant improvements of the memetic algorithm over the GA, and show that the local search method is very effective in practice. In addition, this paper extends [6] with a detailed theoretical study of the search space and the schedule builder, which leads to a better understanding of the problem.

The remainder of the paper is organized as follows. In Section 2 we review some of the EV charging models proposed in the literature, including the model proposed in [4], that gives rise to the problem addressed in the paper. In Section 3 we give a formal definition of the $(1,\textit{Cap}(t)\|\sum T_{i})$ problem. Section 4 describes and analyzes the properties of the search space of so-called left-shifted schedules, and introduces a schedule builder, which restricts the search for solutions to the above space. In Section 5 we describe the main components of the GA. Then, in Section 6 we describe and analyze the proposed neighborhood strategy and its integration into the local search method. Section 7 describes the way GA and the local search procedure are combined, giving rise to the memetic algorithm. In Section 8 we report the results of the experimental study conducted to evaluate the proposed algorithms. Finally, in Section 9 we summarize the main conclusions and outline some ideas for future work.

2. Electric vehicle charging models

This section reviews recent literature on EVs charging models, and describes the setting that gives rise to the $(1,\textit{Cap}(t)\|\sum T_{i})$ problem studied in the paper.

The increasing adoption of EVs may have a significant impact on the environment. Although it could allow for a better use of alternative energy sources, it may also result in important issues on the distribution grid if no smart control strategy is used to distribute charging periods. According to the European Distribution System Operators’ Association [9], one of the challenges in EVs’ technology is the development of smart charging control systems to avoid increasing peak demand and satisfy user requirements. In this context, a number of charging control systems have been proposed (e.g. [10, 11, 12, 13, 14, 15]) that, in general, try to fill the overnight valley as a means to reduce daily cycling and operational costs of power plants. In many cases, these models pose challenging scheduling problems. For example, in [16] an EV charging problem is formalized as a scheduling problem with fixed duration and non-preemptive jobs with the objective of minimizing a weighted sum of the variance and peak of the aggregate load profile. The problem is solved by a real time greedy algorithm, which schedules EVs on arrival using dispatching rules.

The recent literature on EV charging systems and models is extensive, with different features and objectives to be satisfied. For instance, the model in [17] takes into consideration the price and source of energy used. Alternatively, other charging models consider that the charging periods may be interrupted [18] or that the charging power may be variable over time [19], while others require non interruption [16] or constant charging rate [20]. In addition, some models make estimations on the energy required for the day ahead [21], or consider charging/discharging schemes [22] or the use of storage units [23] as ancillary resources. Due to the above, there are many variants of EV charging scheduling problems, and in spite of the number of published models, to our knowledge there are yet neither standard problems nor benchmarks.

The EV charging scheduling problem (EVCSP) considered in [4] is motivated by a charging station, whose design is outlined in [24], to be installed in a community park where each user has their own space. Figure 1 shows the general structure and the main components of this charging station. Each space has a charging point which is connected to one of the three lines of a three phase feeder. The system is controlled by a central server and a number of masters and slaves. Each slave takes control of two charging points and each master controls up to eight slaves in the same line. The control system registers events as EVs arrivals and sends activation/deactivation signals to the charging points in accordance with a schedule.

Figure 1.

General structure of the charging station. (1) Three-phase electric power 400v AC, (2) lines, (3) charging points Type 2/AC IEC 62196-2 with V2G communication interface ISO 15118, (4) masters, (5) server, (6) communication Rs 485, (7) communication TCP/IP, (8) slaves, (9) active vehicles, (10) inactive vehicles.

Due to the EVs arrivals being not known in advance, the EVCSP is dynamic, and so schedules must be computed at different points over time. Furthermore, the physical characteristics and the operating mode of the charging station impose some restrictions to the EVCSP which make it hard to solve. In particular, the contracted power is limited and so it restricts the maximum in each line. Besides, the load in the three lines must be similar to avoid an excessive imbalance among the three phases. The EVCSP assumes two simplifications of the model: (1) the contracted power is constant over time, and (2) the EVs charge at constant rate in the so-called Mode 1 in accordance with the regulation UNE-EN 61851-1 [25]. Therefore, there is a maximum number $N$ of EVs that can be charging in each line simultaneously. These assumptions could be avoided, at the expense of making the scheduling problem harder to solve. For this purpose, the energy blocks scheme used in [19] could be adopted, so that EVs may be given different numbers of energy blocks in time, and the maximum number of energy blocks in each line may be variable over time.

Figure 2 shows a feasible schedule for a possible situation that may arise in the charging station represented in Fig. 1; dark bars represent the EVs that are charging at time $T_{k}$ and light bars represent EVs that are scheduled at a later time. In this example, the maximum number of active EVs in a line is 4 and the maximum difference in the number of active EVs in two lines is 2. For these reasons, none of the tasks 12 and 13 can be scheduled at $T_{k}$ because if some of them were scheduled at $T_{k}$ , lines 2 and 3 would be imbalanced after completion of task 8, as there would be 4 EVs charging in line 2 and only one (number 9) charging in line 3, so exceeding the maximum difference of two. The schedule built at $T_{k}$ allows the EVs in the system to complete their charging periods without violating the constraints of the system. However, if new EVs arrive at the charging station after $T_{k}$ , a new schedule must be built to accommodate them.

Figure 2.

A feasible schedule for a problem instance that may arise in the charging station in Fig. 1. Each Gantt chart corresponds to one line in the charging station. Tasks 1–10 are the active EVs in lines 1, 2 and 3 at time $T_{k}$ , while tasks 10–13 are the inactive EVs in lines 2 and 3, which are scheduled but not started to charge at $T_{k}$ .

To solve the EVCSP, in [4] the authors proposed an algorithm which considers at each scheduling time the active EVs in each line (which cannot be rescheduled), the demanding EVs (which have not yet started to charge), the maximum number of active EVs in a line, $N$ , and a profile of maximum load in each line $N_{i}(t),i=1,2,3$ , which is iteratively adapted to keep the imbalance among lines under control. The objective is to schedule all the EVs in the three lines such that all the constraints are satisfied and the total tardiness, i.e., the delay w.r.t. to the times the users want to take their EVs away, is minimized. The approach in [4] decomposes the EVCSP by considering each line separately, with maximum profiles given by the active EVs and constraints that are enforced to fix possible imbalances among lines. If two of the obtained schedules are imbalanced at some time point, some of the maximum profiles $N_{i}(t)$ must be recalculated and a new schedule obtained for line $i$ . Although this decomposition scheme does not guarantee finding a global optimal schedule, it simplifies the resolution of the EVCSP, and the results in [4] show the suitability of the approach in practice.

This paper focuses on the problem of scheduling the EVs on each line, subject to the maximum load and taking into account the active EVs, which may be viewed as the problem of scheduling a set of tasks on a machine with variable capacity over time. The calculation of the capacity of the machine from the active EVs and the maximum load profile is illustrated in Fig. 3. Note that this example does not follow the one depicted in Fig. 2. It is worth remarking that the capacity of the machine is always a unimodal function. It is increasing at the beginning as long as the active EVs complete charging, and decreasing towards the end due to the way the maximum profiles are updated. Furthermore, it finally gets stabilized at a value greater than 0, what guarantees that the scheduling problem is solvable. This problem was introduced in [4] and referred to as the $(1,\textit{Cap}(t)\|\sum T_{i})$ problem, that we study herein. For a detailed explanation of the setting described above, we refer the interested reader to [4].

Figure 3.

Definition of the capacity of the machine $\textit{Cap}(t)$ from the maximum profile $N_{j}(t)$ and the active EVs at time $T_{k}.$

3. Problem formulation

This section formulates the $(1,\textit{Cap}(t)\|\sum T_{i})$ problem.1 studied in the paper. The problem consists in scheduling a set of $n$ jobs $\mathcal{J}=\{1,\dots,n\}$ on a machine with varying capacity over time. For an instant $t\geqslant 0,\textit{Cap}(t)$ denotes the capacity of the machine in the time interval $(t,t+1)$ . Each of the jobs $i\in\mathcal{J}$ has a duration $p_{i}$ and a due date $d_{i}$ , and is available for being processed from time $t=0$ on (i.e., the problem does not consider release dates). All the values above are non-negative integers.

Scheduling a job $i\in\mathcal{J}$ amounts to assigning it a starting time $st_{i}$ , so that it is processed during the time interval $(st_{i},st_{i}+p_{i})$ on the machine. Processing a job results in the consumption of one unit of the machine’s capacity while it is being processed. Throughout, for any given instant $t\geqslant 0,X(t)$ will denote the number of jobs that are being processed in parallel at that instant, that is, the total consumption along the interval $(t,t+1)$ due to the jobs scheduled. Feasible schedules to the problem correspond to a total assignment of starting times to the jobs in $\mathcal{J}$ such that the following constraints are satisfied:

i.
[Capacity constraints] The consumption $X(t)$ due to jobs scheduled in parallel cannot exceed the capacity of the machine at any instant, i.e.,

$\displaystyle X(t)\leqslant\textit{Cap}(t),t=0,1,2,\ldots$ (1)
ii.
[Non-preemption constraints] Jobs cannot be preempted during their processing; i.e.,

$\displaystyle C_{i}=st_{i}+p_{i},\forall i\in\mathcal{J}$ (2)

where $C_{i}$ denotes the completion time of job $i$ .

For a given problem instance, $\mathcal{S}$ represents the set of all feasible schedules. In a feasible schedule $S\in\mathcal{S}$ , each job $i\in\mathcal{J}$ incurs in a tardiness $T_{i}$ defined as:

$\displaystyle T_{i}=\max\{0,C_{i}-d_{i}\}.$ (3)

This measure represents a penalization whenever the job is completed after its due date, with no reward otherwise (in contrast with the related notion of lateness).

Leaning on the definitions above, the $(1,\textit{Cap}(t)\|$ $\sum T_{i})$ problem consists in finding a feasible schedule $S^{}\in\mathcal{S}$ such that its total tardiness, $T(S)$ , defined as:

$\displaystyle T(S)=\sum_{i\in\mathcal{J}}T_{i}$ (4)

is minimized. Therefore, $S^{}\in\mathcal{S}$ will be an optimal schedule iff $T(S^{*})\leqslant T(S),\forall S\in\mathcal{S}$ .

Example 1. Consider a problem instance, with a set of jobs $\mathcal{J}=\{1,\dots,7\}$ , whose durations and due dates are given the following table:

$i$ 1 2 3 4 5 6 7

$p_{i}$ 7 7 12 14 6 3 11

$d_{i}$ 8 18 12 15 14 13 20

The capacity of the machine over time, $\textit{Cap}(t)$ , is shown in the two feasible schedules depicted in Fig. 4, each representing the starting times of the jobs and the total machine consumption $X(t)$ as well. Due dates are not shown in the Gantt charts for the sake of clarity. As we can observe, in both cases, $X(t)\leqslant\textit{Cap}(t)$ for all $t\geqslant 0$ . The first schedule, shown in Fig. 4a, exhibits a total tardiness of 9, to which only jobs 4 and 6 contribute, with $T_{4}=2$ and $T_{6}=7$ (the other jobs do not incur in a positive tardiness). The schedule shown in Fig. 4b is optimal, with a total tardiness of 2, and only differs from to the first schedule in the allocation of job 6.

Figure 4.
Two feasible schedules for an instance of the $(1,$ $\textit{Cap}(t)$ $\|\sum T_{i})$ problem with 7 jobs and a machine with capacity varying between 2 and 5. The two schedules differ in only the starting time of job 6.

Without loss of generality, we consider that $\textit{Cap}(t)$ is defined as a unimodal step function, as occurs in the EV charging scenario that motivates the problem. Thus, $\textit{Cap}(t)$ will grow non-decreasingly on $t$ until reaching a peak, from which it will decrease eventually getting stabilized at a value greater than 0, which guarantees the existence solutions to the problem.

The $(1,\textit{Cap}(t)\|\sum T_{i})$ generalizes other scheduling problems, such as the $(1\|\sum T_{i})$ problem, where the machine has a constant capacity of one unit (i.e. $\textit{Cap}(t)=1$ ), or the $(P\|\sum T_{i})$ problem [26], which generalizes the former by considering an arbitrary capacity $m$ that is constant over time ( $\textit{Cap}(t)=m$ ). Both problems are known to be NP-hard. Note that both of them can be straightforwardly reduced to the $(1,\textit{Cap}(t)\|\sum T_{i})$ problem by a specific definition of $\textit{Cap}(t)$ . Therefore, it follows that the $(1,\textit{Cap}(t)\|\sum\\ T_{i})$ is NP-hard as well.

Machine availability constraints have been extensively considered in the literature as a means to represent disruptions or maintenance operations [27]. In this context, most single machine formulations consider a machine with unary capacity that may be unavailable for some time periods. This model acts as a building block in formulations with parallel machines or in flow shop and job shop environments, which have been mostly studied for objective functions different than total tardiness minimization. To this respect, it is worth mentioning the $(P,NC_{inc}\|\sum T_{i})$ problem, where a set of parallel machines, each with unary capacity, get increasingly available over time. Other availability patterns have been considered as well for the case of parallel machines, as decreasing, zigzag or staircase availabilities. In contrast, the $(1,\textit{Cap}(t)\|\sum T_{i})$ problem considers a single machine with an arbitrary capacity that varies over time, and it cannot be modeled by using parallel machines.
4. Search space

$i$	1	2	3	4	5	6	7
$p_{i}$	7	7	12	14	6	3	11
$d_{i}$	8	18	12	15	14	13	20

Scheduling problems, as the one studied herein, often exhibit a high computational complexity [28]. Although tractable classes and relaxations exist which can be solved by ad-hoc polynomial time procedures [1], in general solving a scheduling problem requires searching for solutions in a (potentially large) search space.

The nature of the search space, its size and properties, has an impact in both the performance and the effectiveness of the underlying solving algorithm. Therefore, procedures for defining suitable search spaces often constitute a key element in the development of successful algorithms.

To this respect, in scheduling a wide range of solving algorithms rely on the so-called schedule builders, also referred to as schedule generation schemes in the literature (e.g. [29, 30, 31]). These are constructive methods that implicitly define a subset of the feasible schedules that will be considered in the lookout for optimal solutions, thus conforming a search space.

4.1 Left-shifted schedules

In this section, we define a search space for the $(1,$ $\textit{Cap}(t)\|\sum T_{i})$ problem, comprising a subset of the feasible schedules termed left-shifted schedules [32]. Left-shifted schedules are such that it is not possible to process a job earlier without delaying the starting times of some other jobs, without violating the constraints of the problem. A formal definition of such schedules relies on the notion of left-shift movements:

(Left-shift movement).

Let $S$ $\in$ $\mathcal{S}$ be a feasible schedule, determined by starting times $st_{1},$ $st_{2},$ $\ldots,st_{n}$ . A left-shift movement on job $k$ is an operation that results in the feasible schedule $S^{\prime}\in\mathcal{S}$ with starting times $st^{\prime}_{1},st^{\prime}_{2},\ldots,st^{\prime}_{k},\ldots,st^{\prime}_{n}$ , such that $st^{\prime}_{k}<st_{k}$ and $st^{\prime}_{i}=st_{i}$ for $i\neq k$ .

So, the application of a left-shift movement in a feasible schedule results in a different feasible schedule where a given job is moved earlier without any side effects on the starting times of any other jobs. Based on this operation, left-shifted schedules are defined:

(Left-shifted schedule).

Let $S$ be a feasible schedule. $S$ is said to be a left-shifted schedule if it does not admit any left-shift movement.

The following example illustrates the two definitions above.

Example 2. Following the problem instance in Example 3, we apply a left-shift movement on job 6 in the schedule shown in Fig. 4a, scheduling it earlier at time 7. This operation results in the schedule shown in Fig. 4b. Figure 4b is an example of a left-shifted schedule, since no job can be scheduled earlier without changing the starting time of some other jobs.

Compared to the set of all possible feasible schedules $\mathcal{S}$ , the subset of the left-shifted schedules exhibits some interesting properties. First, from a theoretical point of view, although exponential in $n$ (more concretely, the number of different left-shifted schedules is bounded by $\mathcal{O}(n!)$ ) this subset is much smaller than $\mathcal{S}$ . Indeed, note that, since the machine ends up getting stabilized in a capacity greater than 0, there are infinitely many elements in $\mathcal{S}$ . In addition, the average quality of the left-shifted schedules can be expected to be higher than that of the feasible schedules.

.

Let $S\in\mathcal{S}$ be a non-left shifted schedule and $S^{\prime}\in S$ a feasible schedule that results from the application of a left-shift movement on a job $k\in\mathcal{J}$ . It holds that $T(S^{\prime})\leqslant T(S)$ .

Proof..

Let $st_{i}$ and $T_{i}$ (resp. $st^{\prime}_{i}$ and $T^{\prime}_{i}$ ) denote the starting time and tardiness of job $i\in\mathcal{J}$ in $S$ (resp. in $S^{\prime}$ ). By Definition 1, $st^{\prime}_{i}=st_{i}$ for $i\neq k$ and $st^{\prime}_{k}<st_{k}$ . So, by Eqs (2) and (3), $T^{\prime}_{i}=T_{i}$ for $i$ $\neq$ $k$ and $T^{\prime}_{k}$ $\leqslant$ $T_{k}$ . Therefore, $T(S^{\prime})=\sum_{j\in\mathcal{J}}T^{\prime}_{j}\leqslant\sum_{j\in\mathcal{% J}}T_{j}=T(S)$ . ∎

Example 3. To illustrate the properties mentioned above, we have generated all possible left-shifted schedules for the problem instance with 7 jobs from Example 3. There are 1834 different schedules, with minimum, average and maximum total tardiness of 2, 15.08 and 26 respectively.

Applying a left-shift movement never results in a schedule with total tardiness greater than the original one. As a consequence, we can conclude that the search space consisting of the left-shifted schedules is dominant for the $(1,\textit{Cap}(t)\|\sum T_{i})$ problem, i.e., it is guaranteed to contain at least one optimal solution for any problem instance.

.

Let $\mathcal{S}^{*}$ be the set of all optimal schedules for a given $(1,\textit{Cap}(t)\|\sum T_{i})$ problem instance $\mathcal{P}$ . There exists a left-shifted schedule $S\in\mathcal{S}^{*}$ .

Proof..

Let $S^{\prime}$ $\in$ $\mathcal{S}^{*}$ be a non left-shifted optimal schedule. $S^{\prime}$ is not left-shifted, so it admits a sequence of left-shift movements, each resulting in a feasible schedule $S^{\prime}_{1},\ldots,S^{\prime}_{k}$ , where $S^{\prime}_{k}$ is left-shifted. By Proposition 1, each left-shift movement results in a schedule with at most the same total tardiness. The resulting left-shifted schedule $S^{\prime}_{k}$ has the same total tardiness than that of $S^{\prime}$ , which is optimal. Therefore, $S^{\prime}_{k}\in\mathcal{S}^{*}$ . ∎

4.2 Schedule builder

Algorithm 1 depicts the schedule builder proposed in this paper for computing left-shifted schedules. It operates in an iterative fashion, scheduling one job at a time at the earliest possible starting time so that all the constraints in the problem are satisfied. The algorithm maintains a set $U S$ with the unscheduled jobs as well as the consumption $X(t)$ due to the jobs scheduled so far. Initially, $U S$ contains all the jobs in $\mathcal{J}$ , and $X(t)$ is initialized to 0 for all time instants. At each iteration, the algorithm selects a job $u\in US$ , and assigns it the earliest starting time $st_{u}$ from which the machine has enough capacity left during the whole processing time of $u$ . After scheduling $u, U S$ and $X(t)$ are updated: the job $u$ is removed from $U S$ and $X(t)$ is increased in one unit for all instants $t\in(st_{u},st_{u}+p_{u})$ .

[!h] Schedule BuilderA $(1,\textit{Cap}(t)\|\sum T_{i})$ problem instance $\mathcal{P}$ . A feasible schedule $S$ for $\mathcal{P}$ . $US\leftarrow\{1,2,\ldots,n\}$ ;

$X(t)\leftarrow 0,\forall t\geqslant 0$ ;

$US\neq\emptyset$ Non-deterministically pick job $u\in US$ ;

Assign $st_{u}=\min\{t^{\prime}|\forall t$ with $t^{\prime}\leqslant t<t^{\prime}+p_{u}:$ $X(t)<\textit{Cap}(t)\}$ ;

Update $X(t)\leftarrow X(t)+1,\forall t$ with $st_{u}\leqslant t<st_{u}+p_{u}$ ;

$US\leftarrow US-\{u\}$ ; Feasible schedule $S=(st_{1},st_{2},\ldots,st_{n})$ ;

The selection of the job to be scheduled at each iteration is non-deterministic, so the resulting schedule depends on the sequence of choices made. For example, the sequence of choices $(1,3,4,5,6,7,2)$ would lead to building the schedule in Fig. 4b. Regardless of this, the application of Algorithm 1 always produces a feasible left-shifted schedule, as proved next.

.

Algorithm 1 always results in a left-shifted schedule.

Proof..

At each iteration, a job $u\in US$ is assigned the earliest possible starting time so that the total consumption $X(t)$ does not exceed the capacity of the machine at any time instant. Along subsequent iterations of the algorithm, $X(t)$ cannot decrease for any $t$ , so no job can be scheduled earlier than it was scheduled without delaying the processing of some other jobs. Hence, the resulting schedule is left-shifted. ∎

The non-deterministic nature of Algorithm $∼{}1$ allows for defining a search space, i.e. a subset of the feasible schedules, by considering all possible choices in the selection of the job to be scheduled at each step. We prove that all left-shifted schedules for any given problem instance are contained in the search space defined by the schedule builder.

.

Let $S$ be a feasible left-shifted schedule. There exists a sequence of choices $\sigma\!=\!(\sigma_{1},\ldots,$ $\sigma_{n})$ that leads Algorithm 1 to build $S$ .

Proof..

It suffices to define $\sigma$ as the sequence of jobs sorted non-decreasingly by their starting times in $S$ , breaking ties arbitrarily, that is, $\sigma_{i}$ corresponds to the job with the $i$ th smaller starting time. This way, if led by $\sigma$ , the schedule built by Algorithm 1 would be $S$ . ∎

The two propositions above prove that the schedule builder defines exactly the subset of the left-shifted schedules for any given problem instance. The schedule builder could also be instantiated by using any priority rule or heuristic. Besides, it can be used to transform a given permutation of the set of jobs (representing a sequence of choices) into a schedule. This enables using the schedule builder as a decoder in a genetic algorithm, as we will see in the next section.

5. Genetic algorithm

Genetic algorithms (GAs) have been used to solve hard combinatorial optimization problems with notable success (e.g. [33, 34, 35, 36, 37, 38], including scheduling problems [31, 39, 40]).

In this section, we review the main components of the GA used in this work for the $(1,\textit{Cap}(t)\|\sum T_{i})$ problem. Algorithm 2 shows its main structure: it is a generational genetic algorithm with random selection and replacement by tournament among parents and offsprings, which confers the GA an implicit form of elitism. We describe its main components:

[!h] Genetic AlgorithmA $(1,\textit{Cap}(t)\|\sum T_{i})$ problem instance $\mathcal{P}$ and a set of parameters: crossover probability $P_{c}$ , mutation probability $P_{m}$ , number of generations $\#gen$ and population size $\#popsize$ . A feasible schedule for $\mathcal{P}.$ Generate and evaluate the initial population $P(0)$ ;

$t=1$ to #gen $-$ $1$ Selection: organize the chromosomes in $P(t-1)$ into pairs at random

Recombination: mate each pair of chromosomes and mutate the two offsprings in accordance with $P_{c}$ and $P_{m}$ ;

Evaluation: evaluate the resulting chromosomes;

Replacement: make a tournament selection among every two parents and their offsprings to complete $P(t)$ ; The best schedule built so far;

Coding schema

Individuals are defined each by a permutation of the jobs without repetition, i.e. a chromosome $c$ is such that $c=(c_{1},\ldots,c_{n})$ , where $c_{i}\in\{1,\ldots,n\}$ and $c_{i}\neq c_{j}$ for all $i\neq j$ . Permutation-based encodings are common in scheduling, and allow for a number of effective genetic operators.

Crossover and mutation

The GA uses the well-known Order Crossover operator (OX) [41]. Given two parents, an offspring inherits a sub-sequence (selected at random) in the same positions from the first parent and its other positions are filled in accordance with their relative order in the second parent. The second offspring is computed in the same way, but swapping the role of the parents. The mutation operator simply swaps two random elements in the chromosome.

Decoding algorithm

The GA searches for an optimal solution in the search space defined by the schedule builder presented in Section 4.2. Given a chromosome, the decoder builds a schedule using Algorithm 1, scheduling jobs in the order they appear in the chromosome, i.e. at the $i$ -th iteration it schedules job $c_{i}$ . For example, the chromosome $(1,3,4,5,6,7,2)$ would result in the schedule shown in Fig. 4b. The chromosome $(3,1,4,5,6,7,2)$ would lead to the same schedule. So, the mapping is many-to-one. Once a schedule has been built, its total tardiness is taken as the fitness value of the corresponding chromosome.

6. Local search algorithm

Local search stands out as one of the most effective approaches for solving combinatorial optimization problems in a wide range of application domains, including scheduling (e.g. [42, 43, 44]). Although several variants of local search algorithms have been proposed in the literature (e.g. hill climbing, simulated annealing, tabu search, etc.), all of them exploit the same underlying principle: starting from a feasible solution, iteratively apply local perturbations to it, moving to a close solution in the search space, with the expectation of improving its quality.

In this section, we present the local search algorithm proposed for the $(1,\textit{Cap}(t)\|\sum T_{i})$ problem herein. This method has been designed to be deployed in combination with a genetic algorithm, i.e. giving rise to a memetic algorithm. This way, we focus on two desirable properties: it needs to be efficient to keep a low computational overhead and, at the same time, it needs to be effective, leading to improvements along the search process and helping the genetic algorithm to converge to high-quality solutions.

The local improvement algorithm is based on the notion of consecutive jobs in a feasible schedule:

Definition 3. Let $S\in\mathcal{S}$ be a feasible schedule for a given $(1,\textit{Cap}(t)\|\sum T_{i})$ problem instance. Jobs $i$ and $j$ are said to be consecutive in $S$ iff $st_{i}=st_{j}+p_{j}\lor st_{j}=st_{i}+p_{i}$ .

That is, two jobs are consecutive in a schedule if one of them starts exactly after the other one is completed. Noticeably, two consecutive jobs in a schedule can be swapped, resulting in a new schedule with no side-effects on the starting times (and so on the tardiness) of any other jobs.

.

Let $S\in\mathcal{S}$ be a schedule for a given problem instance, and $(i,j)$ a pair of consecutive jobs in $S$ . Swapping $i$ and $j$ results in a feasible schedule $S^{\prime}$ where $st^{\prime}_{k}=st_{k}$ for $k\not\in\{i,j\}$ .

Proof..

W.l.o.g. lets assume that $st_{i}<st_{j}$ in $S$ , i.e., $st_{j}=st_{i}+p_{i}$ . In $S$ , the jobs $i$ and $j$ incur in the consumption of one unit of the machine’s capacity along the interval $(st_{i},C_{j})=(st_{i},st_{i}+p_{i}+p_{j})$ . Swapping these jobs results in new starting times $st^{\prime}_{j}=st_{i}$ and $st^{\prime}_{i}=st^{\prime}_{j}+p_{j}=st_{i}+p_{j}$ , and completion times $C_{j}=st_{i}+p_{j}$ and $C^{\prime}_{i}=st_{i}+p_{j}+p_{i}$ . In this case, jobs $i$ and $j$ incur in a consumption of one unit along the interval $(st^{\prime}_{j},C^{\prime}_{i})=(st_{i},st_{i}+p_{i}+p_{j})$ . So, the total machine consumption due to jobs $i$ and $j$ remains the same as in $S$ after swapping them, with no effect in any other time instants. Hence, keeping $st^{\prime}_{k}=st_{k}$ for $k\not\in\{i,j\}$ in the schedule does not violate any constraints and the resulting schedule $S^{\prime}$ is feasible. ∎

This result enables the definition of a neighborhood structure for the problem. Given a feasible schedule $S$ , each pair $(i,j)$ of consecutive jobs gives rise to a neighbor $S^{\prime}$ of $S$ that results from swapping $i$ and $j$ . Since $S$ and $S^{\prime}$ only differ in the starting times of $i$ and $j$ , the total tardiness of $S^{\prime}$ , i.e. $T(S^{\prime})$ , can be computed beforehand without the need of building $S^{\prime}$ , as follows:

$\displaystyle T(S^{\prime})=T(S)-(T_{i}+T_{j})+(T^{\prime}_{i}+T^{\prime}_{j}),$ (5)

where

$\displaystyle\begin{split}&\displaystyle T^{\prime}_{i}=\max\{0,(st_{i}+p_{i}+% p_{j})-d_{i}\}\quad\textnormal{and}\\ &\displaystyle T^{\prime}_{j}=\max\{0,(st_{i}+p_{j})-d_{j}\}.\end{split}$ (6)

Equations (5) and (6) allow for establishing a necessary and sufficient condition for improvement, which we state without proof.

.

Let $S\in\mathcal{S}$ be a feasible schedule, and $(i,j)$ a pair of consecutive jobs in $S$ . The feasible schedule resulting from swapping the jobs $i$ and $j$ improves $S$ if and only if $(T^{\prime}_{i}+T^{\prime}_{j})<(T_{i}+T_{j})$ .

Assuming that $T(S)$ and $T_{k}$ with $k\in\mathcal{J}$ are known in advance, it is obvious that the condition above can be checked in constant time.

It is possible to design a local search algorithm fully exploiting the neighborhood structure above, i.e., at each iteration, consider all pairs of consecutive jobs in the schedule, and move to a neighboring schedule when the improvement condition is fulfilled.

However, we observe that, in a feasible schedule, jobs with earlier (later) starting times can be expected to contribute to the total tardiness to a lesser (greater) extent. This observation allows us to integrate the neighborhood structure inside an efficient procedure that aims at delaying jobs with low tardiness and scheduling earlier jobs with high tardiness. This procedure relies on the concept of C-path in a feasible schedule:

Definition 4. Given $S\in\mathcal{S}$ a feasible schedule for a given problem instance, a C-path is a maximal sequence of pair-wise consecutive jobs in $S$ .

Note that several C-paths can exist in a feasible schedule, not necessarily disjoint or the longest ones, that is, we refer to set-wise maximality. We prove that the jobs in a C-path can be reorganized without altering the starting times of any other jobs outside it.

.

Let $S\in\mathcal{S}$ be a schedule for a given problem instance, and $P$ a C-path in $S$ . Applying any permutation to $P$ does not alter the starting times of the jobs $j\not\in P$ .

Proof..

Any permutation of the jobs in $P$ can be performed by a sequence of swap operations between consecutive jobs in $P$ . By Proposition 5, each of these operations only affects the starting times of the two jobs involved. Since only jobs in $P$ are swapped in the process, all jobs $j\not\in P$ keep their original starting times. ∎

The result above can be exploited in different ways. Note that the jobs in a C-path $P$ define an instance of a version of the $(1\|\sum T_{i})$ problem where the machine is available from a time instant given by the starting time of the first job in $P$ . This way, a specialized solver could be used to compute optimal solutions for the jobs in $P$ , reorganizing them into the schedule with no effects on any other jobs; hence allowing for developing approaches based on the well-known shifting bottleneck heuristic [45]. This represents a promising line for future work.

At the same time, we can establish an upper bound of the improvement that can be achieved by reorganizing the jobs in $P$ , as $\sum_{j\in P}{T_{j}}$ .

Finally, Proposition 7 serves to prove the soundness of the local improvement procedure proposed herein, whose pseudo-code is shown in Algorithm 3.

[!t] A feasible schedule $S$ A feasible schedule $S^{\prime}$ with $T(S^{\prime})\leqslant T(S)$ . $S^{\prime}\leftarrow S$ ;

$P\leftarrow\textit{ComputeCPath}(S^{\prime})$ ;

$i\in(1,\ldots,|P|-1)$ $j\leftarrow i$ ;

$j<|P|\land\textit{Improves}(P[j],P[j+1],S^{\prime})$ $\textit{Swap}(P[j],P[j+1],S^{\prime})$ ;

$j\leftarrow j+1$ ; $S^{\prime}$ Local Search

The local search algorithm works on a feasible schedule $S^{\prime}$ , initialized as a copy of the input schedule $S$ . As a first step, a random C-path $P$ in $S^{\prime}$ is computed. In this context, $i$ and $j$ refer to integer indices, and $P[i]$ represents the i-th job in $P$ . Then, the C-path $P$ is traversed from left to right, at each step considering a job $P[i]$ , which is iteratively swapped with the next job in the sequence until no improvement is made. To this aim, $\textit{Improves}(P[j],P[j+1],S^{\prime})$ is a function that checks whether swapping the jobs $P[j]$ and $P[j+1]$ in $S^{\prime}$ fulfill the improvement condition in Proposition 6; and $\textit{Swap}(P[j],P[j+1],S^{\prime})$ swaps the jobs $P[j]$ and $P[j+1]$ in $S^{\prime}$ . The algorithm terminates returning $S^{\prime}$ , with the guarantee that $T(S^{\prime})\leqslant T(S)$ .

It is easy to see that Algorithm 3 performs at most $O(|P|^{2})$ swap operations. Since computing a random C-path can be done in $\mathcal{O}(n^{2})$ , $n$ being the number of jobs, and Improve and Swap both take constant time, its complexity is bounded by $\mathcal{O}(n^{2})$ .

Figure 5.

Main structure of the memetic algorithm.

7. Memetic algorithm

Memetic algorithms are hybrid metaheuristics that combine genetic algorithms and local search (see [7] for a general description). This combination is often well suited for hard optimization problems with large search spaces, since it favors an appropriate intensification/diversification balance. The genetic algorithm conducts a global search, sampling diverse regions of the search space, while the local search method intensifies the search locally, allowing the overall method to converge to better solutions.

The memetic algorithm (MA) we propose for the $(1,\textit{Cap}(t)\|\sum T_{i})$ problem combines the genetic algorithm (GA) and the local improvement method (LS) described in the previous sections. MA follows the same structure as Algorithm 2, with the difference that just after evaluating each chromosome, i.e., building a schedule using Algorithm 1, the local search method presented in Algorithm 3 is issued from it, resulting in a (possibly) improved schedule. Figure 5 shows the main organization of the memetic algorithm. As we can observe, given a $(1,\textit{Cap}(t)\|\sum T_{i})$ problem instance, the MA first generates and evaluates an initial population of random chromosomes. Then, iteratively until the termination condition is met, the population undergoes genetic operators of selection, recombination, evaluation, local improvement and replacement. As a termination condition, the MA uses a maximum number of generations, although other criteria could be used as well, such as a maximum running time. Finally, the MA returns the best schedule found.

The MA instruments a Lamarckian evolution model, i.e., after issuing LS, the resulting schedule is coded back into the chromosome. This way, the characteristics that led to an improvement are translated from parents to offsprings along the search. To this respect, note that the local search method works on a C-path $P$ in the schedule, so in the resulting chromosome the jobs in $P$ will appear in the order they appear in the final schedule, without changing the position of any other jobs. Clearly, applying the decoding algorithm to this chromosome would lead to the improved schedule.

8. Experimental results

We present the results from an experimental study carried out to evaluate the algorithms proposed in this work, namely, the genetic algorithm (GA) described in Section 5, the local improvement method (LS) introduced in Section 6 and the memetic algorithm (MA) proposed in Section 7.

Table 1
Summary of results. Error (in percentage) of the solutions returned by each method w.r.t. the best solutions computed by all the methods in the table, averaged for groups of instances with the same number of jobs. Running times of GA are given in seconds

			ATC				GA
$n$	EDD	SPT	025	0.5	0.75	1.0	Best	Avg	Time
15	42.59	382.51	25.02	24.24	33.15	55.08	0.00	0.01	13.13
30	18.94	524.98	6.49	5.26	5.97	8.21	0.00	0.09	21.49
45	27.76	1146.33	11.84	13.27	12.65	23.31	0.00	0.85	30.22
60	36.28	3895.37	14.59	15.09	18.47	29.48	0.00	1.47	38.48
Avg	31.42	1526.90	14.40	14.37	17.80	29.02	0.00	0.60	25.83

For this purpose, we defined a testbed with instances of different sizes and characteristics. These instances are inspired in the expected structure of the instances generated when solving the real EV charging scheduling problem, but at the same time, we avoid generating trivial instances that appear in situations of low demand. Each instance is characterized by the number of jobs ( $n$ ) and the maximum capacity of the machine ( $M C$ ). Given fixed $n$ and $M C$ , a random instance is generated using uniform distributions as follows (all sampled values are integers):

Each job $i\in\mathcal{J}={1,\ldots,n}$ is assigned a random processing time $p_{i}\in\{1,\ldots,100\}$ .

Once all jobs have a processing time, these are assigned a random due date $d_{i}\in[p_{i},\max\{p_{i}+2,\sum_{j\in\mathcal{J}}{p_{j}}/2\}]$ .

The capacity of the machine, $\textit{Cap}(t)$ , is generated as a unimodal function, with each constant interval taking a random duration in the range $[1,$ $\sum{p_{j}}/MC]$ . Both the initial and the final capacities are random integers in $\{1,2\}$ .

This procedure aims at avoiding the generation of under-constrained instances, which can be easily solved. The benchmark set includes instances of different sizes, with $n\in\{15,30,45,60,90,120\}$ and $MC\in\{3,5,7\}$ . For each pair of values $(n,MC)$ we built 10 random instances, so the experimental study was carried out over a total of 180 instances. Compared to [6], the instances with 90 and 120 jobs are new. These are substantially larger than what can be initially expected for the application domain of scheduling the charging times of electric vehicles, but are useful for observing the improvements due to the MA, since the GA is effective already for the smaller instances, as we will observe.

All the algorithms have been implemented in a prototype coded in Python 2.7, and the experiments were run on a Linux cluster (Intel Xeon 2.26 GHz. 24 GB RAM).

The experimental study is structured in three parts. We first evaluate the GA and compare it to some well-known priority rules previously used for solving the problem [4]. Then, we assess the effectiveness and running time of LS over random solutions. Finally, we analyze the performance of MA, comparing it to GA.

8.1 Genetic algorithm

The first series of experiments were run over the 120 instances with sizes up to 60 jobs, with the purpose of assessing the performance of the GA and the quality of the solutions it returns.

To this aim, it is compared with some well-known priority rules, which serve to select the job to be scheduled at each iteration of Algorithm 1. We integrated the following priority rules into our prototype: earliest due date (EDD), which selects the job with the smallest due date, shortest processing time (SPT), which picks the job with the smallest processing time and apparent tardiness cost (ATC), which schedules the job $j$ that maximizes the expression:

$\displaystyle\Pi_{j}={\displaystyle\frac{1}{p_{j}}}\exp\bigg{[}{\displaystyle% \frac{-\max(0,d_{j}-\Gamma(\alpha)-p_{j})}{g\bar{p}}}\bigg{]},$ (7)

where $\Gamma(\alpha)$ is the earliest starting time in which an unscheduled job could be scheduled, $\bar{p}$ denotes the average duration of the jobs, and $g>0$ is a look-ahead parameter to be introduced by the user.

ATC takes into account both processing times and due dates of the unscheduled jobs, and uses the parameter $g$ to achieve a proper balance; note that a large value of $g$ results in a behavior similar of SPT, whereas low values of $g$ make ATC to take due dates into account as well. Other priority rules could be also devised for this problem by taking into account the slack of the jobs at a given time [46].

In the experiments, ATC was run in four configurations on each instance, with $g\in\{0.25,0.5,0.75,1.0\}$ , as was done in [4]. The GA was run 10 times on each problem instance with the parameters $\#popsize=250$ , $\#gen=300$ , $Pc=0.9$ and $Pm=0.1$ .

The results of the comparison are shown in Table 1, averaged for groups of instances with the same number of jobs. For each approach, it reports the relative errors (in percentage) of the cost of the solution obtained w.r.t. the best solution computed by all the methods in the table.2 For GA, it shows the best and average errors over the 10 runs of the algorithm and the average running time of one run (in seconds).

As we can observe, the best solution obtained overall by any methods in the table corresponds to the best solution found by GA over the 10 runs in all cases. The priority rules clearly lay behind GA, with (much) larger errors, and so worse solutions. ATC is the best performing priority rule when using $g\in\{0.25,0.5\}$ ; EDD is in average slightly worse than ATC in its worst configuration ( $g=1.0$ ) and SPT usually leads to low-quality solutions. Besides, the average solutions obtained by GA over the 10 runs are in general close to the best one, with an average improvement of one order of magnitude w.r.t. the best priority rule, in many cases being this improvement greater. Although priority rules are clearly faster (these take negligible time), the GA is quite efficient, taking less than 40 seconds for the largest instances with 60 jobs. To this respect, note that the prototype was coded in Python, and an implementation in C or C++ would be expected to achieve significant time savings.

Table 2

Summary of results. evaluation of LS

$n$	$\#$ Success	$\%$ Reduction	T.Sched	T.LS
15	802.8	18.45	0.16	0.06
30	913.9	22.51	0.26	0.15
45	938.4	23.01	0.37	0.3
60	960.97	24.35	0.46	0.52
90	965.47	25.13	0.67	1.0
120	965.07	25.42	0.87	1.83
Avg.	952.21	23.79	0.49	0.69

Figure 6.

Comparison of ATC and GA. Distribution of error in percentage terms w.r.t. the best solutions found.

Figure 6 shows the errors of the solutions computed by ATC in its four configurations, and by GA, both the average and best solutions over the 10 runs. To make it clearer, the y-axis was limited to 100, although all the configurations of ATC included some values above this limit. This plot confirms that GA reaches higher-quality solutions than ATC.

8.2 Local improvement algorithm

In order to evaluate the performance of the local improvement algorithm (LS) we ran a series of experiments over the whole set of 180 instances. For each instance, we generated 1000 random solutions by making random choices in each iteration of the schedule builder (Algorithm 1) and applied LS to them, recording their total tardiness, as well as the time taken.

Figure 7.

Average total tardiness of random schedules before (Random) and after (Random $+$ LS) applying LS. Points below the main diagonal indicate the superiority of applying LS.

Table 2 summarizes the results averaged for groups of instances with same number of jobs. It shows the number of times (out of 1000) LS resulted in an improved solution ( $\#$ Sucess), the average reduction in percentage of the total tardiness ( $\%$ Reduction) of the final solution w.r.t. the initial one, the time taken in building the 1000 random solutions using the schedule builder (T.Sched) and the time taken in running LS over the 1000 solutions (T.LS). Running times are given in seconds. As we can observe, LS is able to improve the quality of the schedules most of the times, ranging from 80.28% of the cases for the smallest instances to more than 96.5% of the cases for the largest instances. The extent of the improvement is also significant, with an average reduction of 23.79 of the total tardiness, being this value greater for the largest and hardest instances. Both the schedule builder and LS are quite efficient as well, taking 0.49 and 0.69 seconds respectively for 1000 runs each. Note that LS is more efficient than the schedule builder for the smaller instances, while it takes more time for the largest ones, where the most significant improvements are achieved.

Figure 7 shows a scatter plot comparing, for each of the 180 instances, the average total tardiness of the 1000 solutions before and after applying LS. As can be seen, in many cases the average improvement due to LS is remarkable.

8.3 Memetic algorithm

The last series of experiments is aimed at evaluating the memetic algorithm (MA), comparing it to GA.

For the sake of fairness, both GA and MA have been configured with the same parameters as the ones used in the evaluation of GA, i.e. $\#\textit{popsize}=250,Pc=0.9$ and $Pm=0.1$ . In addition, instead of setting the number of generations to a fixed value, the algorithms perform as many iterations as possible within the same timeout which is enforced. In order to match the running times observed above for GA, the timeout is dependent on the number of jobs of the problem instance, and has been set to $2*n/3$ seconds. The experiments were carried out over the whole set of 180 instances, running the algorithms 10 times each.

Table 3
Summary of results. Error (in percentage) of the solutions returned by GA and MA (both the best and average values over 10 runs) w.r.t. the best known solutions, averaged for groups of instances with the same number of jobs. Running times are the same for GA and MA, setting a timeout as $2*n/3$ seconds

$n$	GA Avg	GA Best	MA Avg
15	0.01	0.00	0.01
30	0.24	0.03	0.00
45	1.36	0.02	0.08
60	2.07	0.13	0.06
90	3.77	1.68	0.09
120	23.30	9.62	0.18
Avg.	6.30	2.40	0.08

Figure 8.

Comparison of GA and MA. Distribution of error in percentage terms w.r.t. the best solutions found.

Table 3 compares GA and MA regarding the quality of the solutions computed by the timeout. The results are averaged for groups instances with the same number of jobs, and it shows the error in percentage terms of the best and average solutions computed by GA and MA w.r.t. the best solution known. As we can observe, in all cases, the best solution known for each problem instance is given by the best solution found by MA over the 10 runs. We can also observe that MA is quite stable, obtaining high-quality average solutions with total tardiness close to the best one. This provides evidence that the obtained solutions may be very close to the optimal ones. For the smallest instances, GA and MA perform similarly, being GA able to reach high quality solutions as well. However, as the size of the instances grows, the improvement of MA over GA becomes more significant, especially for the largest instances, where MA obtains (much) better average solutions than the best solutions obtained by GA.

Figure 8 compares GA and MA regarding the errors of the best and average solutions over the whole set of instances. The y-axis was limited to 20, although GA incurred in greater values for a few instances. As we can observe, MA clearly outperforms GA.

9. Conclusions

This paper addresses the $(1,\textit{Cap}(t)\|\sum T_{i})$ problem, which consists in scheduling a set of jobs on a machine whose capacity varies over time so that minimizing the total tardiness. This problem naturally stems from the application domain of scheduling the charging times of a fleet of electric vehicles under technological constraints, such as time dependent power availability [4]. So, efficient solutions to this problem would potentially benefit the ever increasing adoption of electric vehicles in the near future.

Due to the computational intractability of the $(1,$ $\textit{Cap}(t)\|\sum T_{i})$ problem, as well as the expected tight time requirements in the application domain, we propose the use of meta-heuristic algorithms as a means to efficiently approximate optimal solutions to the problem. Concretely, we propose a memetic algorithm that combines a genetic algorithm with a local search method. The genetic algorithm exploits a schedule builder in its decoding phase, which restricts the search to the subset of the so-called left-shifted schedules. Both the search space and the schedule builder are studied in detail in the paper, with formal proofs of its properties, including dominance. The local search algorithm constitutes an important original contribution of the paper. This method is based on swapping consecutive jobs in a feasible schedule, and uses efficient conditions for improvement, which makes the local search algorithm very efficient in practice. The results from an experimental study show that the proposed algorithms are much more effective than the priority rules previously used for solving the problem, while keeping running times reasonably low. The results also show a clear superiority of the memetic algorithm over the genetic algorithm, especially for the largest (and hardest) problem instances.

Future work will investigate alternatives to the algorithms proposed herein. A promising research line would be to develop methods based on the shifting bottleneck heuristic [45], as well as approaches based on constraint programming [47], such as large neighborhood search [48]. Another idea worth developing would be the use of hyper-heuristics [49] for solving the problem, with the aim of obtaining high-quality initial approximations in short running times. In addition, the good results obtained by the memetic algorithm proposed in this paper motivate future work on alternative evolutionary approaches, such as cultural algorithms [8]. On the other hand, a promising line of future research will be to extend the $(1,$ $\textit{Cap}(t)\|\sum T_{i})$ problem with additional features, such as setup times, as well as considering more general models with queuing schemes of EVs, or settings involving wide geographical areas with multiple charging stations. Besides, it would be interesting to consider multi-objective approaches [50, 51, 52], for optimizing different criteria at the same time.

Footnotes

The problem could be denoted $(1|\textit{Cap}(t)|\sum T_{i})$ as well, since $\textit{Cap}(t)$ denotes a constraint. We refer to it as the $(1,$ $\textit{Cap}(t)\|\sum T_{i})$ problem for the sake of consistency with [], where $\textit{Cap}(t)$ is seen as a characteristic of the machine.

In the results reported in this subsection, errors are computed w.r.t. the best solution obtained by GA and the priority rules (and not w.r.t. the best solution known) to make it consistent with the results presented in [6]. For many instances, the best solution known was found by the memetic algorithm in the experiments of Section .

Acknowledgments

This research has been supported by the Spanish Government under project TIN2016-79190-R.

References

Brucker

Knust

. Complex Scheduling. Springer, 2006.

Carlier

. The one-machine sequencing problem. European Journal of Operational Research. 1982; 11: 42-47.

Balas

Simonetti

Vazacopoulos

. Job shop scheduling with setup times, deadlines and precedence constraints. Journal of Scheduling. 2008; 11: 253-262.

Hernández-Arauzo

Puente

Varela

Sedano

. Electric vehicle charging under power and balance constraints as dynamic scheduling. Computers and Industrial Engineering. 2015; 85: 306-315.

Graham

Lawler

Lenstra

Kan

AHGR

. Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics. 1979; 5: 287-326.

Mencía

Sierra

Mencía

Varela

. In: Genetic Algorithm for Scheduling Charging Times of Electric Vehicles Subject to Time Dependent Power Availability. Ferrández Vicente

Álvarez-Sánchez

de la Paz López

Toledo Moreo

Adeli

, editors, Cham: Springer International Publishing, 2017; 160-169.

Talbi

. Metaheuristics-From Design to Implementation. Wiley, 2009.

Reynolds

Sverdlik

. Problem solving using cultural algorithms. Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence, Orlando, Florida, USA, June 27-29, 1994. IEEE; 1994; 645-650. Available from: https://doi.org/10.1109/ICEC.1994.349983.

EDSO; 10 April 2012. Position paper on electric vehicles charging infrastructure. European Distribution system Operators for Smart Grids (EDSO). http://www.edsoforsmartgrids.eu.

10.

Gan

Topcu

Low

. Optimal decentralized protocol for electric vehicle charging. IEEE Conference on Decision and Control and European Control Conference, CDC-ECE, 2011; 5798-5804.

11.

Aliprantis

Ying

. Load scheduling and dispatch for aggregators of plug-in electric vehicles. IEEE Transactions on Smart Grid. 2012 March; 3(1): 368-376.

12.

Callaway

Hiskens

. Decentralized charging control of large populations of plug-in electric vehicles. IEEE Transactions on Control Systems Technology. 2013; 21(1): 67-78.

13.

Kim

Lee

Park

. Constraint-based charging scheduler design for electric vehicles. Proceedings of the 4th Asian conference on Intelligent Information and Database Systems-Volume Part III. ACIIDS’12. Berlin, Heidelberg: Springer-Verlag; 2012; 266-275.

14.

Kang

Duncan

Mavris

. Real-time scheduling techniques for electric vehicle charging in support of frequency regulation. Procedia Computer Science. 2013; 16: 767-775.

15.

Xydas

Marmaras

Cipcigan

. A multi-agent based scheduling algorithm for adaptive electric vehicles charging. Applied Energy. 2016; 177: 354-365.

16.

Binetti

Davoudi

Naso

Turchiano

Lewis

. Scalable real-time electric vehicles charging with discrete charging rates. IEEE Transactions on Smart Grid. 2015; 6(5): 2211-2220.

17.

Kamankesh

Agelidis

Kavousi-Fard

. Optimal scheduling of renewable micro-grids considering plug-in hybrid electric vehicle charging demand. Energy. 2016; 100: 285-297.

18.

Subramanian

Garcá

Domínguez-García

Callaway

Poollaand

Varaiya

. Real-time scheduling of deferrable electric loads. Proceedings of American Control Conference (ACC), 2012; 3643-3650.

19.

Zhang

Chen

Han

Cao

. Charging scheduling of electric vehicles with local renewable energy under uncertain electric vehicle arrival and grid power price. IEEE Transactions on Vehicular Technology. 2014; 63(6): 2600-2612.

20.

Godina

Rodrigues

EMG

Matias

JCO

Catalo

JPS

. Smart electric vehicle charging scheduler for overloading prevention of an industry client power distribution transformer. Applied Energy. 2016; 178: 29-42.

21.

Alipour

Mohammadi-Ivatloo

Moradi-Dalvand

Zare

. Stochastic scheduling of aggregators of plug-in electric vehicles for participation in energy and ancillary service markets. Energy. 2017; 118: 1168-1179.

22.

Jin

Jia

. Optimal day-ahead scheduling of integrated urban energy systems. Applied Energy. 2016; 180: 1-13.

23.

Ottesen

SØ

Korpås

Tomasgard

. Smart electric vehicle charging scheduling at capacity limited charging sites. Censes Working Paper 3/2016, Norwegian University of Science and Technology. 2016; 1-23.

24.

Sedano

Portal

Hernández-Arauzo

Villar

Puente

Varela

. Intelligent system for electric vehicle charging: Design and operation. DYNA. 2013; 88(6): 640-647.

25.

(IEC) TIEC; Electric Vehicle Conductive Charging System?Part 1: General Requirement; IEC 61851-1. London, UK, 2001.

26.

Koulamas

. The total tardiness problem: Review and extensions. Operations Research. 1994; 42: 1025-1041.

27.

Schmidt

. Scheduling with limited machine availability. European Journal of Operational Research. 2000; 121(1): 1-15. Available from: https://doi.org/10.1016/S0377-2217(98)00367-1.

28.

Garey

Johnson

. Computers and Intractability. Freeman, 1979.

29.

Giffler

Thompson

. Algorithms for solving production scheduling problems. Operations Research. 1960; 8: 487-503.

30.

Artigues

Lopez

Ayache

. Schedule generation schemes for the job shop problem with sequence-dependent setup times: Dominance properties and computational analysis. Annals of Operations Research. 2005; 138: 21-52.

31.

Mencía

Sierra

Mencía

Varela

. Genetic algorithms for the scheduling problem with arbitrary precedence relations and skilled operators. Integrated Computer-Aided Engineering. 2016; 23(3): 269-285.

32.

Sprecher

Kolisch

Drexl

. Semi-active, active, and non-delay schedules for the resource-constrained project scheduling problem. European Journal of Operational Research. 1995; 80: 94-102.

33.

Hung

Adeli

. A parallel genetic/neural network learning algorithm for MIMD shared memory machines. IEEE Trans Neural Networks. 1994; 5(6): 900-909. Available from: https://doi.org/10.1109/72.329686.

34.

Kociecki

Adeli

. Two-phase genetic algorithm for size optimization of free-form steel space-frame roof structures. Journal of Constructional Steel Research. 2013; 90: 283-296. Available from: http://www.sciencedirect.com/science/article/pii/S0143974X13002204.

35.

Kociecki

Adeli

. Shape optimization of free-form steel space-frame roof structures with complex geometries using evolutionary computing. Engineering Applications of Artificial Intelligence. 2015; 38: 168-182. Available from: http://www.sciencedirect.com/science/article/pii/S0952197614002528.

36.

Schonfeld

Yang

Zhang

Wang

Xiong

. Mountain railway alignment optimization with bidirectional distance transform and genetic algorithm. Computer-Aided Civil and Infraestructure Engineering. 2017; 32(8): 691-709.

37.

Prieto

Bellas

Trueba

Duro

. Real-time optimization of collective non-separable problems through distributed embodied evolution. Integrated Computer-Aided Engineering. 2016; 23(3): 237-253.

38.

Pillon

Pedrino

Roda

Nicoletti

. A hardware oriented ad-hoc computer-based method for binary structuring element decomposition based on genetic algorithms. Integrated Computer-Aided Engineering. 2016; 23(4): 369-383.

39.

Kyriklidis

Dounias

. Evolutionary computation for resource leveling optimization in project management. Integrated Computer-Aided Engineering. 2016; 23(2): 161-172.

40.

Ahn

Lee

Bahn

. A smart elevator scheduler that considers dynamic changes of energy cost and user traffic. Integrated Computer-Aided Engineering. 2017; 24(2): 187-202.

41.

Davis

. Applying adaptive algorithms to epistatic domains. IJCAI, 1985; 162-164. Available from: http://ijcai.org/Proceedings/85-1/Papers/029.pdf.

42.

Van Laarhoven

Aarts

Lenstra

. Job shop scheduling by simulated annealing. Operations Research. 1992; 40: 113-125.

43.

Nowicki

Smutnicki

. An advanced tabu search Algorithm for The job shop problem. Journal of Scheduling. 2005; 8: 145-159.

44.

Zhang

Rao

Guan

. A very fast TS/SA algorithm for the job shop scheduling problem. Computers and Operations Research. 2008; 35: 282-294.

45.

Adams

Balas

Zawack

. The shifting bottleneck procedure for job shop scheduling. Managament Science. 1988; 34: 391-401.

46.

Papakostas

Chryssolouris

. A scheduling policy for improving tardiness performance. Asian International Journal of Science and Technology. 2009; 2(3): 79-89.

47.

Rossi

Beek

Walsh

. Handbook of constraint programming (foundations of artificial intelligence). New York, NY, USA: Elsevier Science Inc., 2006.

48.

Shaw

. Using constraint programming and local search methods to solve vehicle routing problems. Maher MJ, Puget J, editors. Principles and Practice of Constraint Programming – CP98, 4th International Conference, Pisa, Italy, October 26-30, 1998, Proceedings. vol. 1520 of Lecture Notes in Computer Science. Springer; 1998; 417–431. Available from: https://doi.org/10.1007/3-540-49481-2_30.

49.

Branke

Nguyen

Pickardt

Zhang

. Automated design of production scheduling heuristics: A review. IEEE Trans Evolutionary Computation. 2016; 20(1): 110-124. Avai- lable from: https://doi.org/10.1109/TEVC.2015.2429314.

50.

Rostami

Neri

. Covariance matrix adaptation pareto archived evolution strategy with hypervolume-sorted adaptive grid algorithm. Integrated Computer-Aided Engineering. 2016; 23(4): 313-329.

51.

Pan

Tian

Zhang

. A region division based diversity maintaining approach for many-objective optimization. Integrated Computer-Aided Engineering. 2017; 24(3): 279-296.

52.

Wang

Liu

Yuan

Chen

. Optimizing the energy-spectrum efficiency of cellular systems by evolutionary multi-objective algorithm. Integrated Computer-Aided Engineering. 2018; Pre-press: 1-14.

Evolutionary one-machine scheduling in the context of electric vehicles charging

Abstract

Keywords

1. Introduction

2. Electric vehicle charging models

4.1 Left-shifted schedules

(Left-shift movement).

(Left-shifted schedule).

.

Proof..

.

Proof..

4.2 Schedule builder

.

Proof..

.

Proof..

5. Genetic algorithm

6. Local search algorithm

.

Proof..

.

.

Proof..

8. Experimental results

Table 1 Summary of results. Error (in percentage) of the solutions returned by each method w.r.t. the best solutions computed by all the methods in the table, averaged for groups of instances with the same number of jobs. Running times of GA are given in seconds

Footnotes

Acknowledgments

References

Table 1
Summary of results. Error (in percentage) of the solutions returned by each method w.r.t. the best solutions computed by all the methods in the table, averaged for groups of instances with the same number of jobs. Running times of GA are given in seconds