It can be seen, that the algorithm computes a set of neighborhoods for each alternative. The sequence in which the neighborhoods are computed is arranged in a random fashion, described in line 13 of Algorithm 1. This introduces an additional element of diversity to the concept, as otherwise the search might be biased by a certain sequence of neighborhoods.

## 4. An Application To Multi-Objective Flow Shop Scheduling 4.1. Configuration Of The Algorithm And Experimental Setup

In the following, the Pareto Iterated Local Search is applied to a set of benchmark instances of the multiobjective permutation flow shop scheduling problem. They have been provided by (Basseur, Seynhaeve and Talbi, 2002), who first defined due dates for the well-known instances of (Taillard, 1993). The instances range from n **= 20** jobs that have to be processed on m = 5 machines to n = 100, m **= 20**. All of them are solved under the simultaneous consideration of the minimization of the maximum completion time Cmax and the total tardiness Tsum.

Three operators are used in the definition of the neighborhoods N1**, . . . ,** Nk, described in the work of
(Reeves, 1999). 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, each computing n(n−1)
2neighboring 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 are needed to return from x
′′ back to x
′
. This is important, als otherwise the algorithm might navigate straight back to the initially perturbed alternative, possibly leading to a cycle in the search path.

The perturbation neighborhood N**perturb** 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 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 + 3 to j, and the job at position j + 3 to j + 2. In brief, this leads to a combination of several exchange and shift moves, executed at once.

The benchmark instances of Basseur have been solved using the PILS algorithm. In each of the 100 test runs, the approximation quality of the obtained results has been analyzed using the D1 and D2 metrics of (Czy˙zak and Jaszkiewicz, 1998). While for the smaller instances the optimal solutions are known, the analysis for the larger instances has to rely on the best known results published in the literature. Experiments have been carried out on a Intel Pentium IV processor, running at 1.8 GHz. Table 1 gives an overview about the number of evaluations executed for each instance. Clearly, considerable more alternatives have to be evaluated with increasing size of the problem instances to allow a convergence of the algorithm. An implementation of the algorithm has been made available within the MOOPPS computer system, a software for the resolution of multi-objective scheduling problems using metaheuristics. The system is equipped with an extensive user interface that allows an interaction with a decision maker and is able to visualize the obtained results in alternative and outcome space. The system also allows the comparison of results obtained by different metaheuristics. For a first analysis, we compare the results obtained by PILS to the approximations of a multi-objective multi-operator search algorithm MOS, described in Algorithm 2.

The MOS Algorithm 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.