1. Local Optima Networks of the Permutation Flowshop Scheduling Problem: Makespan vs. total flow time
- Author
-
Leticia Hernando, Fabio Daolio, Gabriela Ochoa, Nadarajen Veerapen, University of the Basque Country (University of the Basque Country), University of Stirling, and IEEE
- Subjects
Mathematical optimization ,021103 operations research ,Job shop scheduling ,Linear programming ,Iterated local search ,business.industry ,Feature extraction ,0211 other engineering and technologies ,Context (language use) ,02 engineering and technology ,[INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] ,Permutation ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Local search (optimization) ,Algorithm design ,business ,ComputingMilieux_MISCELLANEOUS ,Mathematics - 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.
- Published
- 2017
- Full Text
- View/download PDF