work of Reeves **[19]. First, an exchange neighborhood, exchanging the position of two jobs in** π, second, a forward shift neighborhood, taking a job from position i **and reinserting it at position** j with j < i, and finally a backward shift neighborhood, shifting a job from position i to j **with** j < i**. All operators are problem independent operators for permutation-based representations, each**
computing n(n−1)
2**neighboring solutions.**
After a first approximation P
approx **of the Pareto set is obtained, one element** x
′ P
approx is selected by random and perturbed into another solution x
′′**. We use a special neighborhood that on**
one hand leaves most of the characteristics of the perturbed **alternatives intact, while still changes**
the positions of some jobs. Also, several consecutive applications of the neighborhoods N1**, . . . ,** Nk would be needed to transform x
′′ **back into** x
′
**. This is important, as otherwise the algorithm might**
return to the initially perturbed alternative x
′
**, leading to a cycle in the search path.**
The perturbation neighborhood Nperturb can be described as follows. First, a subset of π **is randomly**
selected, comprising four consecutive jobs at positions j, j+1, j+2, j**+3. Then a neighboring solution**
x
′′ is generated by moving the job at position j to j + 3, the one at position j + 1 to j **+ 2, the one**
at position j + 2 to j, and the job at position j + 3 to j + 1, leaving the jobs at the positions < j and > j **+ 3 untouched. In brief, this leads to a combination of several exchange and shift moves,**
executed at once.

 2009 In order to analyze the quality of the approximations, we compare the results obtained by PILS to the approximations of a multi-objective multi-operator search algorithm MOS, described in Algorithm 2.

Algorithm 2 **Multi-objective multi-operator search framework**
1: Generate initial solution x**, set** P
approx = {x}
2: **repeat**
3: **Randomly select some** x ∈ P
approx | **neighborhoods not investigated yet**
4: Randomly select some neighborhood Nifrom N1**, . . . ,** Nk 5: **Generate** Ni(x)
6: **Update** P
approx **with** Ni(x)
7: if x ∈ P
approx **then**
8: Set neighborhoods of x **as 'investigated'**
9: **end if**
10: **until** 6∃x ∈ P
approx | **neighborhoods not investigated yet**
11: **Return** P
approx MIC

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

The MOS Algorithm, taken from [8], is based on the concept of Variable Neighborhood Search, extending the general idea of several neighborhood operators by adding an archive P
approx **towards**
the optimization of multi-objective problems. For a fair comparison, the same neighborhood operators are used as in the PILS algorithm. After the termination **criterion is met in step 10, we restart**
search while keeping the approximation P
approx **for the final analysis of the quality of the obtained**
solutions.

## 3.2 Results

The benchmark instances of Basseur and the one of Bagchi **have been solved using the PILS**
algorithm. In each of the 100 test runs, the approximation quality of the obtained results has been Hamburg, Germany, June 13–16, 2009