NILS: a Neutrality-based Iterated Local Search and its application to Flowshop Scheduling. This paper presents a new methodology that exploits specific characteristics from the fitness landscape. In particular, we are interested in the property of neutrality, that deals with the fact that the same fitness value is assigned to numerous solutions from the search space. Many combinatorial optimization problems share this property, that is generally very inhibiting for local search algorithms. A neutrality-based iterated local search, that allows neutral walks to move on the plateaus, is proposed and experimented on a permutation flowshop scheduling problem with the aim of minimizing the makespan. Our experiments show that the proposed approach is able to find improving solutions compared with a classical iterated local search. Moreover, the tradeoff between the exploitation of neutrality and the exploration of new parts of the search space is deeply analyzed.

References in zbMATH (referenced in 7 articles , 1 standard article )

Showing results 1 to 7 of 7.
Sorted by year (citations)

  1. Khatami, Mostafa; Salehipour, Amir; Hwang, F. J.: Makespan minimization for the (m)-machine ordered flow shop scheduling problem (2019)
  2. Meignan, David; Knust, Sigrid: A neutrality-based iterated local search for shift scheduling optimization and interactive reoptimization (2019)
  3. Vallada, Eva; Ruiz, Rubén; Framinan, Jose M.: New hard benchmark for flowshop scheduling problems minimising makespan (2015)
  4. Garza-Fabre, Mario; Rodriguez-Tello, Eduardo; Toscano-Pulido, Gregorio: Comparative analysis of different evaluation functions for protein structure prediction under the HP model (2013) ioport
  5. Humeau, J.; Liefooghe, A.; Talbi, E.-G.; Verel, S.: ParadisEO-MO: from fitness landscape analysis to efficient local search algorithms (2013)
  6. Marmion, Marie-Éléonore; Jourdan, Laetitia; Dhaenens, Clarisse: Fitness landscape analysis and metaheuristics efficiency (2013)
  7. Marmion, Marie-Eléonore; Dhaenens, Clarisse; Jourdan, Laetitia; Liefooghe, Arnaud; Verel, Sébastien: NILS: A neutrality-based iterated local search and its application to flowshop scheduling (2011) ioport