Local Optima Networks for the Permutation Flowshop Scheduling Problem: Makespan vs. Total Flow Time

Citation

Hernando L, Daolio F, Veerapen N & Ochoa G (2017) Local Optima Networks for the Permutation Flowshop Scheduling Problem: Makespan vs. Total Flow Time. In: 2017 IEEE Congress on Evolutionary Computation (CEC). IEEE Congress on Evolutionary Computation 2017, San Sebastián, Spain, 05.06.2017-08.06.2017. Piscataway, NJ, USA: IEEE, pp. 1964-1971. https://doi.org/10.1109/CEC.2017.7969541

Abstract
Local Optima Networks were proposed to understand the structure of combinatorial landscapes at a coarse-grained level. We consider a compressed variant of such networks with features that are meaningful for the study of search difficulty in the context of local search. In particular, we investigate different landscapes of the Permutation Flowshop Scheduling Problem. The insert and 2-exchange neighbourhoods are considered, and two different objective functions are taken into account: the makespan and the total flow time. The aim is to analyse the network features in order to find differences between the landscape structures, giving insights about which features impact algorithm performance. We evaluate the correlation between landscape properties and the performance of an Iterated Local Search algorithm. Visualisation of the network structure is also given, where evident differences between the makespan and total flow time are observed.

People

Professor Gabriela Ochoa

Professor, Computing Science