Multi-objective approaches to scheduling consider a vector G(x) = (g1(x), . . . , gK(x)) of optimality criteria at once [21]. As the relevant optimality criteria are often of conflicting nature, not a single solution x ∈ X exists optimizing all components of G(x**). Optimality in multi-objective**
optimization problems is therefore understood in the sense **of Pareto-optimality, and the resolution** of multi-objective optimization problems lies in the identification of all elements belonging to the Pareto set P, containing all alternatives x **which are not dominated by any other alternative** x
′ ∈ X.

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 investigations 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 **[17]. 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**
[16], again under the combination of both objectives into a weighted sum. Later work on the same problem class by Basseur, Seynhaeve and Talbi **[4] avoids the weighted sum approach, using**
dominance relations among the solutions only.

Most recent work is presented by Loukil, Teghem and Tuyttens **[14]. Contrary to approaches**
from Evolutionary Computations, the authors apply the Multi Objective Simulated Annealing approach MOSA of Ulungu, Teghem, Fortemps and Tuyttens **[22] to a variety of bi-criterion**
scheduling problems.

Flow shop scheduling problems with three objectives are studied by Ishibuchi and Murata **[11],** and Ishibuchi, Yoshida and Murata **[12]. 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 **[1, 2].**
 2009

## 2 Pareto Iterated Local Search

![0_Image_0.Png](0_Image_0.Png)

MIC
The Pareto Iterated Local Search (PILS) metaheuristic is a concept for the solution of multiobjective optimization problems. It combines the two main driving forces of local search, intensification and diversification, into a single algorithm, and **extends the work presented in [8]. The**
motivation behind 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:
1. Iterated Local Search, introducing the idea of perturbing solutions to overcome local optimality and continue search in interesting areas of the search space **[15]. After the pioneering work of**
Boese **[6], who investigated properties of the search space of the traveling salesman problem,**
this concept has been used with increasing success on problems where solutions of high quality can be found relatively concentrated in alternative space.

## Hamburg, Germany, July 13–16, 2009
