Definition 2.1 (Pareto dominance): A vector of objective functions G(x**) is said to dominate an vector** G(x
′
**) if and**
only if ∀i gi(x) ≤ gi(x
′
) ∧ ∃i | gi(x) < gi(x
′
).

The neighbourhood operators applied within the framework have been k-FSH, k-BSH, and k**-EX. A control**
parameter k **determines the number of succeeding jobs in the sequence being involved in the shift or exchange** operation, resulting in a block shift or block exchange neighbourhood for k > 1. Settings of k = 1, k = 2, and k = 3 have been tested. 100 Test instances have been generated with n = m = 10 following the proposal of Taillard **[28],**
and the due dates of the jobs were generated adopting the methodology of Demirkol et al. **[9]. The size of the**
instances allows the determination of the true Pareto set by enumerating all possible alternatives within reasonable time.

| Abbreviation   | No objectives   | Classification α | β | γ [12]                  |
|----------------|-----------------|------------------------------------------------|
| γ1             | 2               | F | prmu, dj | Cmax, Tmax                      |
| γ2             | 2               | F | prmu, dj | Cmax, Csum                      |
| γ3             | 2               | F | prmu, dj | Cmax, Tsum                      |
| γ4             | 2               | F | prmu, dj | Tmax, Tsum                      |
| γ5             | 2               | F | prmu, dj | Csum, Tmax                      |
| γ6             | 2               | F | prmu, dj | Csum, Tsum                      |
| γ7             | 3               | F | prmu, dj | Cmax, Tmax, Tsum                |
| γ8             | 3               | F | prmu, dj | Cmax, Csum, Tmax                |
| γ9             | 3               | F | prmu, dj | Cmax, Csum, Tsum                |
| γ10            | 3               | F | prmu, dj | Csum, Tmax, Tsum                |
| γ11            | 4               | F | prmu, dj | Cmax, Csum, Tmax, Tsum          |
| γ12            | 6               | F | prmu, dj | Cmax, Csum, Tmax, Tsum, Isum, U |

Tab. 1: **Investigated combinations of optimality criteria.**
Each neighbourhood operator has been tested on each problem instance in 100 test runs regarding twelve different combinations of optimality criteria as given in table 1, leading to a total of 1,080,000 local search runs.

The approximation quality of the obtained set P
approx to the Pareto set P has been measured using the D1 **(average**
deviation of P
approx to P) and D2 **(maximum deviation of** P
approx to P) metrics of Czyzak ˙ and Jaszkiewicz **[7].**

## 2.2 Results

The average results obtained by the local search operators have **been investigated for statistical significance using**
a t-test at a given level of significance of 0.01. Table 2 and 3 give the number of test instances, in which a neighbourhood definition led to a significantly best approximation for D1 and D2.

It is possible to observe that neighbourhoods with a control parameter of k > **1 are only superior for very**
few problem instances. Comparing 1-FSH, 1-BSH and 1-EX, no operator turns out to be the most appropriate in all cases. While forward shift tends to lead more frequently to significantly best results, there are still numerous instances for which other operators are more favourable. It can **also be noticed that this result is not primarily** depending on the optimality criteria involved.

On a more detailed level it is possible to observe that the identification **probability of a single Pareto optimal**
alternative depends on the choice of the neighbourhood operator. To illustrate this circumstance, figure 1 plots for each x ∈ P of a problem instance, involving the optimality criteria combination γ11**, the frequency of its** identification. No correlation between the identification frequencies can be seen, and the analysis reveals the existence of Pareto optimal alternatives which may be identified rather easily using e.g. 1-FSH while not being found by the 1-EX neighbourhood and vice versa.