- **The minimisation of the number of tardy jobs** U =Pn j=1 Uj **where** Uj =
1 : Tj > 0 0 : Tj = 0 In terms of machine efficiency, idle times Ii of the machines Mi **may be considered up to the completion of the last**
job. Optimality criteria are therefore:
- The minimisation of the maximum machine idleness Imax = max{I1**, . . . , I**m}.

- The minimisation of the total machine idleness Isum =Pm i=1 Ii.

An important factor for the resolution of the permutation flow shop scheduling problem is the circumstance that the functions are regular [6]. It is therefore possible to map a given sequence of jobs π = {π1, . . . , πn} **into an**
active schedule, one of which is optimal [8]. Consequently, many existing local search approaches are based on this idea of a schedule representation, and neighbourhood definitions manipulate the job permutations π **by changing** the positions of jobs [23]:
- Exchange neighbourhood (EX), exchanging the position of two jobs πj and πk, j 6= k. - Forward shift neighbourhood (FSH), removing a job πj and reinserting it at position πk with **k > j**.

- Backward shift neighbourhood (BSH), removing a job πj and reinserting it at position πk with **k < j**.

- **Inversion neighbourhood (INV), inverting the positions of a chosen subset of** π.
Important applications of local search algorithms for the permutation flow shop scheduling problem comprise local search descent [11, 23, 32], simulated annealing [10, 11, 13, 19, 20, 25], tabu search [22, 27, 33], and evolutionary algorithms [1–4,14,15,17,18,26]. The majority of the previously conducted studies consider the problem as a single objective optimisation problem with respect to the makespan objective Cmax**. Here, shift neighbourhood operators**
lead in most cases to superior results [27]. A generalisation of the conclusions with respect to multi objective problem settings seems however questionable, and corresponding **studies have not been conducted yet.**

## 2 An Investigation Of Neighbourhood Operators 2.1 Local Search Framework And Experimental Setup

The effectiveness of local search operators for multi objective flow shop scheduling problems has been investigated using the framework described in algorithm 2.1 [29].

Algorithm 2.1 **Multi Objective Local Search Descent**
1: **Generate initial solution** x 2: P
approx = {x}
3: **repeat**
4: **Select** x ∈ P
approx for which nh(x**) has not been investigated yet**
5: **Generate** nh(x) 6: **Update** P
approx **with all** x
′ ∈ nh(x)
7: if x ∈ P
approx **then**
8: Mark nh(x**) as 'investigated'**
9: **end if**
10: **until** 6∃x ∈ P
approx with nh(x**) still to be investigated**
Starting from a random initial solution, neighbouring solutions are generated until no further improvement is possible. With respect to the goal of approximating a Pareto set P **of alternatives, an approximation set** P
approx is maintained during search. The update of P
approx **is done according to the the Pareto dominance relation,**
given in definition 2.1 for the chosen objective vector G(x) = (g1(x), . . . , gk(x)). P
approx **therefore only contains**
nondominated alternatives. Solutions x
′ ∈ nh(x) that dominate x lead to the removal of x **from** P
approx**, making**
step 7 after the update of P
approx necessary.