After the identification of the Pareto set P, an interactive search might be performed by the decision maker
(Vincke, 1992). The interactive procedure terminates with the identification of a most-preferred solution x
∗ ∈ P.

## 2.2. Previous Research

Several approaches of metaheuristics have been formulated and tested in order to solve the permutation flow shop scheduling problem under multiple, in most cases two, objectives. Common to all is the representation of solutions using permutations π of jobs, as in previous investigation only regular functions are considered. First results have been obtained using Evolutionary Algorithms, which in general play a dominant role in the resolution of multi-objective optimization problems when using metaheuristics. This is mainly due to the fact that these methods incorporate the idea of a set of solutions, a so called *population*, as a general ingredient. Flow shop scheduling problems minimizing the maximum completion time and the average flow time have been solved by (Nagar, Heragu and Haddock, 1996). In their work, they however combine the two objectives into a weighted sum. Problems minimizing the maximum completion time and the total tardiness are solved by (Murata, Ishibuchi and Tanaka, 1996), again under the combination of both objectives into a weighted sum. Later work on the same problem class by (Basseur, Seynhaeve and Talbi, 2002) avoids the weighted sum approach, using dominance relations among the solutions only. Most recent work is presented by (Loukil, Teghem and Tuyttens, 2005). Contrary to approaches from Evolutionary Computations, the authors apply the Multi Objective Simulated Annealing approach MOSA
(Ulungu, Teghem, Fortemps and Tuyttens, 1999) to a variety of bi-criterion scheduling problems.

Flow shop scheduling problems with three objectives are studied by (Ishibuchi and Murata, 1998), and (Ishibuchi, Yoshida and Murata, 2003). The authors minimize the maximum completion time, the total completion time, and the maximum tardiness at once. A similar problem minimizing the maximum completion time, the average flow time, and the average tardiness is then tackled by (Bagchi, 1999; Bagchi, 2001).

## 3. Pareto Iterated Local Search

The Pareto Iterated Local Search (PILS) metaheuristic is a novel concept for the resolution of multiobjective optimization problems. It combines the two main driving forces of local search, intensification and diversification, into a single algorithm. The motivation behind the proposition of this concept can be seen in the increasing demand for simple, yet effective heuristics for the resolution of complex multi-objective optimization problems. Two developments in local search demonstrate the effectiveness of some intelligent ideas that make use of certain structures within the search space topology of problems. First, Iterated Local Search (Lourenc¸o, Martin and St¨utzle, 2003), introducing the idea of perturbations to overcome local optimality and continue search in interesting areas of the search space. Second, Variable Neighborhood Search
(Hansen and Mladenovi´c, 2003), combining multiple neighborhood operators into a single algorithm in order to avoid local optimality in the first place. In the proposed concept, both paradigms are combined and extended within a search framework handling not only a single but a set of alternatives at once.

The main principle of the algorithm is sketched in Figure 1. Starting from an initial solution x1, an improving, intensifying search is performed until a set of locally optimal alternatives is identified, stored in a set P
approx representing the approximation of the true Pareto set P. No further improvements are possible from this point. In this initial step, a set of neighborhoods ensures that all identified alternatives are locally optimal not only to a single but to a set of neighborhoods. This principle, known from Variable Neighborhood Search, promises to lead to better results as it is known that all global optima are also locally optimal with respect to all possible neighborhoods while this is not necessarily the case for local optima.

After the identification of a locally optimal set, a diversification step is performed on a solution x2 using a perturbation operator, continuing search from the perturbed solution x3. The perturbation operator has to be significantly different from the neighborhoods used in intensification, as otherwise the following search