# Foundations Of The Pareto Iterated Local Search Metaheuristic

Martin Josef Geiger Lehrstuhl f¨ur Industriebetriebslehre Institut f¨ur Betriebswirtschaftslehre Universit¨at Hohenheim Schloß Hohenheim, Osthof-Nord, D-70593 Stuttgart, Germany E-mail: mjgeiger@uni-hohenheim.de

## Keywords: Pareto Iterated Local Search, Metaheuristics, Multi-Objective Scheduling

Summary: *The paper describes the proposition and application of a local search metaheuristic* for multi-objective optimization problems. It is based on two main principles of heuristic search, intensification through variable neighborhoods, and diversification through perturbations and successive iterations in favorable regions of the search space. The concept is successfully tested on permutation flow shop scheduling problems under multiple objectives. While the obtained results are encouraging in terms of their quality, another positive attribute of the approach is its' simplicity as it does require the setting of only very few parameters.

The implementation of the Pareto Iterated Local Search metaheuristic is based on the MOOPPS computer system of local search heuristics for multi-objective scheduling which has been awarded the European Academic Software Award 2002 in Ronneby, Sweden (http://www.easa-award.net/, *http://www.bth.se/llab/easa_2002.nsf)*.

## 1. Introduction

Real world problems often comprise several points of view that from a decision makers perspective have to be taken simultaneously into consideration. Multi-objective optimization approaches play in this context an increasingly important role, tackling applications in numerous areas. Due to the complexity of most problems however, problem resolution has to rely in many cases on modern heuristics that provide fast results without necessarily identifying an optimal solution. Here, local search approaches like e. g. Simulated Annealing, Evolutionary Algorithms, and Tabu Search play a dominant role. Depending on the application area, more and more refined version and adaptations of local search metaheuristics have been proposed with increasing success in recent years.

Scheduling is one of the most active areas of research, with applications in numerous areas of manufacturing, computer systems/grid scheduling, sports/tournament scheduling, and airline/fleet scheduling, to mention a few. Many of the mentioned problems are of multi-criteria nature, and considerable effort has been made to solve these often N P-hard problems. While metaheuristics often lead to acceptable results, room for improvements can still be identified, especially as modern metaheuristics tend to require increasingly complex parameter settings. The current paper describes an local search heuristic for the effective resolution of multi-objective optimization problems, based on the local search paradigm. An application of the approach is presented to the multi-objective permutation flow shop scheduling problem. The article is organized as follows. Section 2 first introduces the considered problem and briefly reviews heuristic solution approaches known from literature. The Pareto Iterated Local Search algorithm is then presented in Section 3. An application of the metaheuristic to the discussed problem is given in the following Section 4, and conclusions are drawn in Section 5.

arXiv:0809.0406v1 [cs.AI] 2 Sep 2008