An Algebraic Approach for the Search Space of Permutations with Repetition

Abstract

We present an algebraic approach for dealing with combinatorial optimization problems based on permutations with repetition. The approach is an extension of an algebraic framework defined for combinatorial search spaces which can be represented by a group (in the algebraic sense). Since permutations with repetition does not have the group structure, in this work we derive some definitions and we devise discrete operators that allow to design algebraic evolutionary algorithms whose search behavior is in line with the algebraic framework. In particular, a discrete Differential Evolution algorithm which directly works on the space of permutations with repetition is defined and analyzed. As a case of study, an implementation of this algorithm is provided for the Job Shop Scheduling Problem. Experiments have been held on commonly adopted benchmark suites, and they show that the proposed approach obtains competitive results compared to the known optimal objective values.

1 Introduction

An algebraic framework for combinatorial optimization problems has been previously proposed in a series of articles [4,5,6, 22]. This framework mainly proposed the discrete operations of sum, difference, and scalar multiplication that allow to design discrete variants of widely used continuous evolutionary algorithms such as the Differential Evolution (DE) [22] and the Particle Swarm Optimization (PSO) [23]. The main requirement of the framework is that the solutions in the search space of the combinatorial problem at hand must form a group (in the algebraic sense). For instance, this is the case of widely considered search spaces such as those of bit-strings [24] and permutations [1, 6].

However, there are interesting problems defined in combinatorial search spaces which do not form a group. One of these is the space of permutations with repetition, i.e., ordering of items which – differently from classical permutations – can appear multiple times in the sequence. This search space has been considered, for example, in [8, 14, 16, 20, 27]. The most notable applications of permutations with repetition are in some scheduling and partitioning problems. Indeed, in the scheduling case, the repeated items accommodate the fact that some jobs need to be processed in more than one machine, while, in partitioning problems, permutations with repetition are intended as assignments of items to a particular cluster among a set of clusters with a given size. Widely known example of such problems are the job shop scheduling problem [11] and the balanced multiway graph partitioning problem [17].

In this work, we extend the algebraic framework in order to work on the search space of permutations with repetition, even if they do not form a group. With this regard, we derive formal definitions and algorithmic implementations of the discrete operators of sum, difference and scalar multiplication. Such operators allow to design discrete variants of evolutionary algorithms which are commonly and effectively used in the continuous search spaces. In particular, we introduce a discrete Algebraic Differential Evolution for Permutations with Repetition (ADE-PR) by also analyzing its search behavior.

ADE-PR can in principle be applied to any problems requiring a permutation with repetition as a solution. As a case of study, we have investigated the effectiveness of ADE-PR on the Job Shop Scheduling Problem (JSSP). Therefore, few additional algorithmic components, purposely defined for the JSSP, have been integrated in ADE-PR. Finally, computational experiments have been held by considering widely used benchmark suites for the JSSP.

The rest of the paper is organized as follows. Section 2 recalls the algebraic framework which has been extended in Sect. 3 in order to handle the space of permutations with repetition. Section 4 describes the main scheme of ADE-PR, while its implementation for the JSSP is depicted in Sect. 5. The experimental analysis is described in Sect. 6, while Sect. 7 concludes the paper by also providing future lines of research.

2 Algebraic Background

2.1 The Abstract Algebraic Framework for Evolutionary Computation

The algebraic framework for evolutionary computation, firstly proposed in [22] and further studied in [3, 4, 6, 7], allows to define the discrete operators $\oplus$, $\ominus$ and $\odot$ which simulate in a discrete search space the properties of their numerical counterparts.

In particular, these discrete operators are abstractly defined for any combinatorial search space whose solution set can be represented with an algebraic structure known as finitely generated group [18].

The triple $(X,\circ ,G)$ is a finitely generated group representing the search space of a given combinatorial optimization problem $\mathcal {P}$ if:

• X is the set of solutions of $\mathcal {P}$;

• $\circ$ is a binary operation on X satisfying the group properties, i.e., closure, associativity, identity (e), and invertibility ($x^{-1}$); and

• $G \subseteq X$ is a finite generating set of the group, i.e., any $x \in X$ has a (not necessarily unique) minimal-length decomposition $\langle g_1, \dots , g_l \rangle$, with $g_i \in G$ for all $i \in \{1,\ldots ,l\}$, and whose evaluation is x, i.e., $x = g_1 \circ \dots \circ g_l$.

Moreover, the length of a minimal decomposition of a discrete solution $x \in X$ is denoted by |x|.

Using $(X,\circ ,G)$, it is possible to provide formal definitions of the operators $\oplus$, $\ominus$ and $\odot$. Let $x,y \in X$ and $\langle g_1, \dots , g_k, \dots , g_{|x|} \rangle$ be a minimal decomposition of x, then

$$\begin{aligned} x \oplus y := x \circ y \text{, } \end{aligned}$$

(1)

$$\begin{aligned} x \ominus y := y^{-1} \circ x \text{, } \end{aligned}$$

(2)

$$\begin{aligned} a \odot x := g_1 \circ \dots \circ g_k \text{, } \text{ with } k = \lceil a \cdot |x| \rceil \text{ and } a \in [0,1]. \end{aligned}$$

(3)

Interesting graph-based interpretations of these definitions can be given as follows. The algebraic structure on the search space naturally defines neighborhood relations among the solutions. Indeed, any finitely generated group $(X,\circ ,G)$ is associated to a labelled digraph $\mathcal {G}$ whose vertices are the solutions in X and two generic solutions $x,y \in X$ are linked by an arc labelled by $g \in G$ if and only if $y = x \circ g$. Therefore, a simple one-step move in the search space can be directly encoded by a generator, while a composite move can be synthesized as the evaluation of a sequence of generators (a path on the graph).

In analogy with $\mathbb {R}^n$, the elements of X can be dichotomously interpreted both as solutions (vertices on the graph) and as displacements between solutions (labelled paths on the graph). As detailed in [22], this allows to provide rational interpretations of the definitions (1), (2) and (3) as follows:

• $x \oplus y$ is the vertex of $\mathcal {G}$ where we arrive if we move from the vertex x following the arcs in any (minimal) decomposition of y;

• a minimal decomposition of $x \ominus y$ corresponds to the sequence of arcs in a shortest path from the vertex y to the vertex x in $\mathcal {G}$;

• the scalar multiplication $a \odot x$, with $a \in [0,1]$, corresponds to truncating a shortest path from the vertex e (the identity of the group) to the vertex x in $\mathcal {G}$.

Clearly, these geometrical interpretations are in line with the vectors/points interpretations of the classical Euclidean space.

2.2 The Algebraic Differential Evolution

As shown in [22] and [23], expressions which involve the three discrete operators allow to derive discrete variants of some popular evolutionary schemes originally defined for continuous problems [19, 26]. For instance, a discrete variant of the Differential Evolution (DE) algorithm, namely Algebraic Differential Evolution (ADE), can be defined by simply replacing the classical mathematical operations with their discrete variants $\oplus ,\ominus ,\odot$ in the definition of the differential mutation which is the key operator of the DE.

Therefore, the differential mutation of ADE is defined as follows:

$$\begin{aligned} v \leftarrow x_{r_0} \oplus F \odot ( x_{r_1} \ominus x_{r_2} ), \end{aligned}$$

(4)

where $x_{r_0},x_{r_1},x_{r_2} \in X$ are three randomly selected population individuals, $F \in [0,1]$ is the DE scale factor parameter, and $v \in X$ is the mutant produced.

The interpretation of Eq. (4) in the search space graph $\mathcal {G}$ is as follows: v is generated by starting from the vertex $x_{r_0}$ and following the arcs indicated by $F \odot ( x_{r_1} \ominus x_{r_2} )$ which is a sequence of arcs’ labels (generators) obtained by truncating a shortest path from $x_{r_2}$ to $x_{r_1}$. This is in line with what is done by the classical differential mutation equation in the Euclidean space, i.e., generate a mutant v by applying to $x_{r_0}$ the vector corresponding to the truncated segment which connects $x_{r_2}$ to $x_{r_1}$. Indeed, note that the concept of segment in the Euclidean space is analogous to the concept of shortest path in the graph representing a discrete search space.

2.3 The Search Space of Permutations

The definitions provided in the previous sections are abstract and require implementations for concrete spaces. One of the most investigated search space that verifies the properties of finitely generated groups is the space of permutations [2, 25].

The permutations of the set $\{ 1, \ldots , n \}$, together with the usual permutation composition, form the so-called Symmetric group $\mathcal {S}(n)$. The identity permutation is $\iota = \langle 1,\ldots ,n \rangle$. Furthermore, since $\mathcal {S}(n)$ is finite, it is also finitely generated.

One of the most useful generating sets for the permutations is the set of simple transpositions $ASW \subset \mathcal {S}(n)$, i.e., particular permutations which algebraically encode the adjacent swap moves. Formally,

$$\begin{aligned} ASW = \{ \sigma _i : 1 \le i < n \}, \end{aligned}$$

(5)

where the $n-1$ simple transpositions $\sigma _i$ are permutations such that

$$\begin{aligned} \sigma _i(j) = {\left\{ \begin{array}{ll} i+1 &{} \text{ if } j=i,\\ i &{} \text{ if } j=i+1,\\ j &{} \text{ otherwise. } \end{array}\right. } \end{aligned}$$

(6)

Given a generic $\pi \in \mathcal {S}(n)$, the composition $\pi \circ \sigma _i$ swaps the i-th and $(i+1)$-th items in $\pi$. Therefore, using the abstract definitions provided before, a minimal decomposition of the difference between two generic permutations $\pi$ and $\rho$ corresponds to the shortest sequence of adjacent swap moves which transforms $\pi$ into $\rho$.

A minimal decomposition for a generic permutation $\pi \in \mathcal {S}(n)$, in terms of $ASW$, can be obtained by ordering the items in $\pi$ by using a sorting algorithm based on adjacent swap moves. The sequence of generators corresponding to the moves performed during the sorting process is annotated, then reversing this sequence produces a minimal decomposition [22].

As widely known, the bubble-sort algorithm sorts any given array by using a minimal number of adjacent swap moves, therefore it can be used for computing a minimal decomposition of any permutation in terms of $ASW$. Anyway, since there can be more than one minimal decompositions, a randomized variant of bubble-sort, namely $RandBS$, has been proposed in [22].

$RandBS$ exploits the concept of inversion and the property that the identity permutation $\iota$ is the only permutation without inversions. Formally, (i, j) is an inversion of a given permutation $\pi$ if and only if $i<j$ and $\pi (i)>\pi (j)$. Moreover, a permutation with a positive number of inversions has to have at least one adjacent inversion, i.e., an inversion of the form $(i,i+1)$. Therefore, $RandBS (\pi )$ decreases the inversions of $\pi$ by first computing its adjacent inversions and, then, iteratively applying adjacent swaps corresponding to those inversions. At the end of this process $\pi$ will be transformed into the identity $\iota$, thus the reverse of the sequence of adjacent swaps is a minimal decomposition of $\pi$.

$RandBS$ has been proved to have $\varTheta (n^2)$ complexity. For further implementation details, proofs of correctness and complexity we refer the interested reader to [22].

3 Permutations with Repetition

3.1 Motivations and Preliminary Definitions

The search space of permutations arises in a variety of combinatorial problems such as, just to name a few: the permutation flowshop scheduling problem, the linear ordering problem, the quadratic assignment problem and the traveling salesman problem. Without loss of generality, an n-length permutation is an ordering of the set $\{ 1,\ldots ,n \}$, thus the items in this ordering are all different from each other.

However, there exist other important combinatorial problems for which it is required that some items can appear several times in the ordering. For instance, in the job shop scheduling problem [11], the items are the jobs to be scheduled and repeated items accommodate the fact that some jobs need to be processed on more than one machine. Repeated items also allow to handle some partitioning problems, such as the balanced multiway graph partitioning problem [17].

We can encode solutions to these problems by means of permutations with repetition, i.e., orderings of a given multiset.

A multiset M is a collection of possibly repeated items, the size (or cardinality) of the collection is denoted by |M|, and its support $Supp (M)$ is the set of all different items appearing in M. For example, the multiset $M=\{1,1,2,2,3,3\}$ has cardinality $|M|=6$ and support $Supp (M)=\{1,2,3\}$.

Given a multiset M with support $\{1,\ldots ,n\}$ and cardinality $q>n$, a permutation with repetition of M is an ordering of the q items in M. We denote by $\mathcal {R}_M$ the set of all the permutations with repetition of M. Considering the multiset M in the previous example, a possible permutation with repetition is $x = \langle 2,1,3,3,2,1 \rangle$.

The search space $\mathcal {R}_M$ has size

$$\begin{aligned} |\mathcal {R}_M| = \frac{q!}{\prod _{i \in Supp (M)} m_M(i)!}, \end{aligned}$$

(7)

where $m_M(i)$ is the multiplicity of the item i in M, i.e., the number of times i appears in M. Therefore, though $|\mathcal {R}_M| < |\mathcal {S}(q)|$, the size of the search space is anyway exponential with respect to the length of the orderings. This is the main reason of why the combinatorial problems with solutions in $\mathcal {R}_M$ are usually NP-hard.

For the sake of readability, in the rest of the paper, we will use the acronym PwR in place of the phrase “permutation with repetition”.

3.2 Discrete Operators for Permutations with Repetition

Differently from classical permutations, it is not apparent how to define an internal operation on $\mathcal {R}_M$ which obeys to the group properties. As a consequence, it is not possible to directly use the discrete algebraic operators as defined in Sect. 2.

Anyway, the same simple search moves considered for permutations, i.e., swaps of adjacent items, can be used to move between permutations with repetition. Indeed, all the PwRs in $\mathcal {R}_M$ can be thought as vertices of a search space graph where, as before, its arcs are labelled by adjacent swap moves. Hence, the solutions $x,y \in \mathcal {R}_M$ are neighbors to each other if and only if y can be obtained from x (or vice versa) by swapping two adjacent items in x (or y).

By recalling that the adjacent swap move between the i-th and $(i+1)$-th items (of a normal permutation, but also of a PwR) can be represented as the very simple permutation $\sigma _i \in ASW$ defined in Eq. (6), we have that a path between two given PwRs $x,y \in \mathcal {R}_M$ is a composition of adjacent swaps, i.e., a generic |M|-length permutation $\pi \in \mathcal {S}(|M|)$. Clearly, in this space we do not have the dichotomy observed in the Symmetric group $\mathcal {S}(n)$ that is: solutions and paths between solutions have different representations. Solutions are elements of $\mathcal {R}_M$, while paths/moves between solutions are elements of $\mathcal {S}(|M|)$.

The absence of the solution-move dichotomy does not allow to use the same algebraic definitions given in Sect. 2. Nevertheless, we can exploit the graph structure of $\mathcal {R}_M$ in order to derive reasonable definitions for the discrete sum, difference and scalar multiplication operators. These definitions are in line with the geometrical interpretations given in the previous section.

Discrete Sum. The discrete sum operator $\boxplus : \mathcal {R}_M \times \mathcal {S}(|M|) \rightarrow \mathcal {R}_M$ which, given a solution $x \in \mathcal {R}_M$ and a move $\pi \in \mathcal {S}(|M|)$, produces the new solution $y = x \boxplus \pi$ by applying to x all the adjacent swap moves appearing in a minimal decomposition of $\pi$ in terms of $ASW$.

Discrete Difference. The discrete difference operator $\boxminus : \mathcal {R}_M \times \mathcal {R}_M \rightarrow \mathcal {S}(|M|)$ applied to two solutions $x,y \in \mathcal {R}_M$ produces the permutation $\pi = x \boxminus y$ whose minimal decomposition in terms of $ASW$ is formed by the sequence of adjacent swaps that transform y into x. It is interesting to note that, similarly to what happens in the classical Euclidean space, $\boxplus$ and $\boxminus$ are consistent to each other, i.e., for any $x,y \in \mathcal {R}_M$, $x \boxplus \left( y \boxminus x \right) = x$.

Discrete Scalar Multiplication. Regarding the scalar multiplication, let observe that practically it is only used to scale-down a move or path in the space¹. With this regard, see also the geometric interpretation of ADE in Sect. 2.2. Since a move in the search space of PwRs is a normal permutation, we can use unmodified the operator $\odot$ defined in Sect. 2 for the permutation space.

3.3 Implementation of the Discrete Operators

The definition previously given for $\boxplus$ actually indicates also its implementation. As noted in Sect. 2.3, decomposing the permutation costs $\varTheta (|M|^2)$. Luckily, given $x \in \mathcal {R}_M$ and $\pi \in \mathcal {S}(|M|)$, it is possible to compute $x \boxplus \pi$ in linear time without decomposing $\pi$. Formally, by denoting with x(i) the i-th item of the PwR x, we have that:

$$\begin{aligned} \left( x \boxplus \pi \right) (i) = x( \pi (i) ) . \end{aligned}$$

(8)

It is easy to see that applying Eq. (8) to any item $i \in \{1,\ldots ,|M|\}$ is equivalent to sequentially applying to x all the adjacent swaps in a decomposition of $\pi$.

Let also note that the operator $\boxplus$ is actually a (right) group action [18] of the Symmetric group $\mathcal {S}(|M|)$ on the set $\mathcal {R}_M$. Indeed, by using the Polish notation for the sake of readability, it is easy to verify that $\boxplus$ satisfies the two axioms of the (right) group action functions [18]: (i) $\boxplus (x,\iota ) = x$ for all $x \in \mathcal {R}_M$, and (ii) $\boxplus (x,\pi \circ \sigma ) = \boxplus ( \boxplus (x,\pi ), \sigma )$ for any $\pi ,\sigma \in \mathcal {S}(|M|)$ and $x \in \mathcal {R}_M$.

For the discrete difference $\boxminus$, we first need to define the canonical PwR $e \in \mathcal {R}_M$ as the ordering of M whose items are increasingly sorted. For instance, given $M = \{1,1,2,2,3,3\}$, its canonical PwR is $e = \langle 1,1,2,2,3,3 \rangle$.

Furthermore, let observe that the concept of inversion, introduced in Sect. 2.3, is also defined on the permutations with repetition, and e is the only PwR without inversions.

Therefore, it is possible to use $RandBS$ – or, if randomness is not required, any other bubble-sort variant – to sort any PwR x, towards the canonical PwR e, by using an optimal number of adjacent swaps. The optimality derives from the facts that: (i) bubble-sort schemes are known to be optimal when all items are different, and (ii) useless adjacent swaps between equivalent items in a PwR are avoided because the pairs of equivalent items cannot form inversions.

Hence, we are now able to find the sequence of adjacent swaps for moving from any PwR x towards e, i.e., we are able to compute $e \boxminus x$. Moreover, by observing the commutative diagram depicted in Fig. 1, we can generalize the computation $x \boxminus y$ to any $x,y \in \mathcal {R}_M$. In this diagram, any arrow connects two PwRs and is labelled with the permutation which encodes the sequence of adjacent swaps that transform the tail of the arrow into its head. Equivalently, the label of the arrow is the difference between the head PwR and the tail PwR.

Fig. 1.

Commutative diagram showing how to compute $\pi = x \boxminus y$

Since we know how to compute $\sigma = e \boxminus y$ and $\rho = e \boxminus x$, we can now define the difference between two generic PwRs as:

$$\begin{aligned} x \boxminus y = \pi = \sigma \circ \rho ^{-1}. \end{aligned}$$

(9)

4 Algebraic Differential Evolution for Permutations with Repetition

In this section we define an Algebraic Differential Evolution scheme for Permutations with Repetition (ADE-PR) which is based on the ADE scheme described in Sect. 2.2 and the discrete operators for the PwR representation depicted in Sect. 3.

ADE-PR evolves a population of N permutations with repetition by means of the genetic operators: differential mutation, crossover and selection. Its working scheme, depicted in Algorithm 1, is similar to those of ADE and classical DE. The main difference is that the population of ADE-PR is composed by individuals represented as permutations with repetition.

ADE-PR optimizes a given objective function f defined on the search space $\mathcal {R}_M$. Its control parameters are: the population size N, the scale factor $F \in [0,1]$ and the crossover strength $CR \in [0,1]$ (the latter may not be present depending on the chosen crossover operator).

In Algorithm 1, the population is randomly initialized in lines 2–3, then the evolution is performed in the main cycle in lines 4–12 until a given termination criterion is satisfied. For each population individual $x_i$, a mutant $v_i$ is generated in line 6 by exploiting the differential mutation scheme which is implemented by means of the discrete operators for PwRs previously introduced. Then, a trial PwR $u_i$ is obtained, in line 7, by hybridizing $x_i$ and $v_i$ by means of a chosen crossover operator working on the PwR representation (like, for instance, GOX, GPMX and PPX [8, 9]). In lines 9–10, if $u_i$ is fitter than $x_i$, it enters the next-generation population by replacing $x_i$.

Moreover, it is possible to integrate into the ADE-PR scheme: (i) a local search scheme, purposely defined for the problem at hand, in order to refine the search, and (ii) a restart procedure which is often useful in combinatorial problems whose search space is finite.

Note also that the parameters F and $CR$ can be self-adapted during the evolution using one of the many self-adaptive DE schemes in the literature.

The key operator of ADE-PR is the newly introduced differential mutation scheme which directly works with permutations with repetition. The expression in line 6 of Algorithm 1 can be interpreted as follows. The mutant $v_i$ is generated by applying to the PwR $x_{r_0}$ a sequence of adjacent swap moves which is a prefix of the sequence of moves that transform the PwR $x_{r_2}$ into $x_{r_1}$. Clearly, the length of the prefix is regulated by the scale factor $F \in [0,1]$. This interpretation is in line with what happens in the continuous DE and for ADE in a search space representable as a finitely generated group.

5 ADE-PR for the Job Shop Scheduling Problem

As a case study, we describe an implementation of ADE-PR for solving the Job Shop Scheduling Problem (JSSP). The resulting algorithm, called ADE-PR-JSSP, follows the scheme depicted in Sect. 4, i.e., it starts with a population of randomly initialized PwRs which are evolved by means of the following operators: discrete differential mutation, GOX crossover [9], selection, local search for the JSSP, and restart procedure. Furthermore, the parameter F used in the discrete differential mutation is self-adapted by means of the jDE method [10], while the GOX crossover, as defined in [9], has no parameter.

In the next subsections we describe: the definition of the JSSP, the procedure for converting a permutation with repetition to a feasible JSSP schedule, the local search operator and the restart scheme adopted in ADE-PR-JSSP.

5.1 Definition of the Problem

The Job Shop Scheduling Problem (JSSP) is an important scheduling problem with many applications in the manufacturing and service industry [12, 13].

An instance of the JSSP is defined in terms of a set $\mathcal {J}$ of n jobs $J_1,\dots ,J_n$ and a set $\mathcal {M}$ of m machines $\mu _1,\dots ,\mu _m$. Each job $J_i$ is composed by m operations $O_{i1}, \dots , O_{im}$. Every operation $O_{ij}$ has a processing time $p_{ij}$ and has to be executed by the machine $\mu _{ij}\in \mathcal {M}$. All the operations within a given job are linearly ordered, while no constraint is defined among operations belonging to different jobs. The set of all the operations is denoted by $\mathcal {O}$.

A feasible schedule s consists in assigning to each operation $O_{ij}\in \mathcal {O}$ a start time $s_{ij}$ such that the following constraints are satisfied: for each $i=1,\dots ,n$ and $j=1,\dots ,m-1$,

$$\begin{aligned} s_{ij} \le s_{i,j+1}, \end{aligned}$$

(10)

and, for each $O_{ij}, O_{hk} \in \mathcal {O}$ with $\mu _{ij} = \mu _{hk}$,

$$\begin{aligned} s_{ij}\ge e_{hk} \text{ or } s_{hk} \ge e_{ij}, \end{aligned}$$

(11)

where $e_{ij} = s_{ij} + p_{ij}$ is the end time of the operation $O_{ij}$.

A feasible schedule s is optimal if it optimizes a given objective function. In this paper, the aim is to minimize the makespan

$$\begin{aligned} C_{max}(s) = \max _{ij} e_{ij}. \end{aligned}$$

(12)

The JSSP has been approached using a variety of different techniques. In the recent survey [11] many evolutionary and meta-heuristic approaches to solve the JSSP are described: Particle Swarm Optimization, Ant Colony Optimization, Variable Neighborhood Search, Tabu Search, Genetic Algorithms, and several others.

5.2 From a Permutation with Repetition to a JSSP Schedule

The solutions of ADE-PR-JSSP are represented as PwRs over the multiset $M_{m,n}$, whose support is $\{1,\dots ,n\}$, and such that every item in $M_{m,n}$ has multiplicity m. Hence, ADE-PR-JSSP navigates the search space of the permutations with repetition in $\mathcal {R}_{M_{m,n}}$.

This representation, called operation-based representation [12], was firstly introduced by [8] and has the important property that it generates only feasible solutions.

The operation-based representation is based on the fact that each operation $O_{ij} \in \mathcal {O}$ can be uniquely identified by the integer number $(i-1) m + j$. Therefore, a PwR $x \in \mathcal {R}_{M_{m,n}}$ is decoded to a JSSP schedule by using a two-phase procedure.

In the first phase, a permutation $\pi _x \in \mathcal {S}(mn)$, representing a total order $\prec _x$ among the operations in $\mathcal {O}$, is built from x as follows.

For each $h = 1,\dots ,mn$, let $j=x(h)$ be the h–th item of x and let k be the number of items $x_l$, for $1 \le l \le h$, such that $x_l=j$, then $\pi _x(h)$ is set to $(j-1) m + k$. Then, $\pi _x(h)$ corresponds to the operation $O_{j,k}$.

It is easy to see that $\prec _x$ respects the constraint (10) by construction. Indeed $O_{ij} \prec _x O_{i,j+1}$, for each pair of indices i and $j<m$. Moreover, for each pair of operations $O_{ij}, O_{hk} \in \mathcal {O}$ assigned to the same machine, $\prec _x$ states in which order the two operations have to be executed.

The second phase assigns to each operation $O_{ij}$ a start time $s_{ij}$ as the maximum among the end time of $O_{i,j-1}$ and the end times of all the operations $O_{hk}$ preceding $O_{ij}$, with respect to $\prec _x$, and such that $\mu _{ij} = \mu _{hk}$.

The obtained schedule is feasible and respects the precedence relations induced by $\pi _x$. Therefore, by calling the conversion procedure as $GenerateSchedule$ and given a PwR $x \in \mathcal {R}_{M_{m,n}}$, we have that the fitness of x in ADE-PR-JSSP is the makespan of the corresponding schedule, i.e., $C_{max}\left( GenerateSchedule (x) \right)$.

5.3 Local Search for the JSSP

We have designed ADE-PR-JSSP in such a way that every trial individual $u_i \in \mathcal {R}_{M_{m,n}}$, at every generation of the algorithm, undergoes a local search procedure with probability $p_{LS}$.

Before applying the local search, the trial individual, represented as a PwR, is first converted to a schedule by means of the procedure described in Sect. 5.2.

The local search is based on the neighborhood $\mathcal {N}^{\star }$, as described in [21], and works as follows. At each iteration the critical path of the current schedule s is computed. This path is the sequence of consecutive operations (where the end time of any operation coincides with the start time of the successive operation in the path) which has the maximum completion time (which corresponds to the makespan of s). Then, the blocks of consecutive operations assigned to the same machine are detected in the critical path. For each block B, two swaps are tried: one exchanges the first two operations in B, while the other exchanges the last two operations. The swap which most reduces the makespan is performed and the schedule is updated accordingly. If no swap produces a better makespan, the local search terminates.

Now, the local optimal schedule is converted back to a PwR and replaces the seed individual $u_i$ in the population of ADE-PR-JSSP. The conversion can be easily implemented by considering a topological sorting in the precedence graph of the local optimal schedule.

After some preliminary experiments, we set the probability $p_{LS}$ to apply the local search as

$$\begin{aligned} p_{ LS }(t) = \frac{t}{T} \cdot p_{ LS }^{ end } + \left( 1 - \frac{t}{T} \right) \cdot p_{ LS }^{ start }, \end{aligned}$$

(13)

where t is the current computational time, T is the budget for the execution time, $p_{LS}^{start}$ is the probability of applying the local search at time $t=0$, and $p_{LS}^{end}>p_{LS}^{start}$ is the probability at time $t=T$. Hence, the local search is progressively applied more often as time passes. This behavior should favor exploration in the earlier phase of the evolution, while exploitation is intensified with the passing of time.

5.4 Restart Scheme

The restart mechanism is implemented by replacing all the population individuals, except the best one, with new randomly generated PwRs.

A restart is performed when the algorithm has not been able to improve its best solution so far after $T \cdot r_{restart}$ seconds, where T is the total allotted running time and $r_{restart}<1$ is the parameter which regulates how often this operation should be performed at most.

6 Experiments

ADE-PR-JSSP has been experimentally validated on some commonly adopted benchmarks for the JSSP, namely: the ft, la, and orb benchmark suites [15]². The benchmarks contain a total of 53 JSSP instances with $n \cdot m$ ranging from 36 to 300.

After some preliminary experiments, the population size has been set to $N=25$ individuals, the range for the application probability of the local search has been set using $p_{LS}^{start}=0$ and $p_{LS}^{end}=1$, while the restart parameter $r_{restart}$ has been set to 0.1.

The executions of ADE-PR-JSS have been carried out on a machine equipped with the Intel Xeon CPU E5-2620 v4 clocking at 2.10 GHz. Every execution terminates after a time budget of $T=4mn$ seconds has been exhausted. Moreover, $R=15$ executions per instance have been run.

Table 1. Experimental results on instances with $nm<100$

Table 2. Experimental results on instances with $nm=100$

The presentation of the experimental results is divided in three groups, according to the values of mn: Table 1 refers to the instances with $nm<100$, Table 2 to those with $nm=100$, and Table 3 to the remaining instances. In these three tables we present, for each instance: the sizes n and m, the average ($Avg _i$) and minimum ($Min _i$) fitness values obtained by ADE-PR-JSSP in the R runs, the known optimal value ($Opt _i$) for the instance (taken from the recently published survey paper [15]), and the average relative percentage deviation computed as $ARPD_i = 100 \times \frac{ Avg _i - Opt _i}{ Opt _i}$. Moreover, the minimum $Min_i$ is reported in boldface when it matches the known optimal value $Opt _i$.

Interestingly, in 38 out of 53 instances, ADE-PR-JSSP reached the optimal value at least once, while, in 22 instances, this happened in all the executions.

In particular, the results provided in Table 1 refer to small JSSP instances, where ADE-PR-JSSP has been always able to find the optimal value, and for 7 of such instances this happened in all the executions. Indeed, the average ARPD for this set of instances is rather small, i.e., $0.167\%$.

Table 2 shows that on the 22 selected instances with $nm=100$ the algorithm has been able to find the optimal value: at least once on 17 instances, and in all the executions in 6 cases. As expected, the average ARPD for this second set of instances, $0.606\%$, is larger than the previous, but anyway close to 0.

In Table 3 it is possible to see that ADE-PR-JSSP reached the known optimal value: at least once in half the instances (10 out of 20), and in all the executions for 8 of them. Therefore, the average ARPD for this last set of instances is slightly larger than the other: $0.841\%$. Moreover, Table 3 also shows that the instances with $m=15$ are much harder and the average ARPD restricted to this subset raises to $1.652\%$.

Table 3. Experimental results on instances with $nm>100$

Summarizing, the overall ARPD obtained by averaging on all the 53 instances is 0.604, thus promoting the proposed approach as a method competitive with respect to the known values for the considered benchmarks.

7 Conclusion and Future Work

In this paper, we have extended the algebraic framework for evolutionary computation previously proposed in [22] in order to handle the search space of permutations with repetition. The newly proposed discrete operators allowed to design an Algebraic Differential Evolution called ADE-PR which can be applied to any combinatorial optimization problem whose solutions may be represented as permutations of possibly repeated items.

In particular, ADE-PR has been devised for the Job Shop Scheduling Problem (JSSP). In order to validate the effectiveness of the proposed approach, experiments have been on a set of widely adopted benchmark instances for the JSSP. The experimental results show that our proposal is competitive with respect to the known optimal objective values for the considered benchmarks.

Possible future lines of research are: apply ADE-PR to partitioning problems; use simple search moves other than the swaps of adjacent items; design other algebraic evolutionary algorithms, like the APSO [23], in order to work with permutations with repetition; and generalize the approach to other search spaces, by means of the algebraic concept of group action, in order to see the deployed discrete operators as projections from a known space which can be represented as a group to other more general combinatorial spaces.