Solving bi-objective flow shop problem with hybrid path relinking algorithm

This paper presents and investigates different ways to integrate path relinking techniques into the hypervolume-based multi-objective local search algorithm (HBMOLS). We aim to evaluate the effectiveness of different path relinking strategies, these strategies focus on two main steps: the ways of path generation and the mechanisms of solutions selection. We propose different methods to establish the path relinking algorithms in a multi-objective context. Computational results on a bi-objective flow shop problem (FSP) and a statistical comparison are reported in the paper. In comparison with two versions of HBMOLS, the algorithms selecting a set of solutions located in the middle of the generated path are efficient. The behavior of these algorithms sheds light on ways to further improvements.

Graphical abstractFigure optionsDownload full-size imageDownload as PowerPoint slideHighlights•Different ways to hybridize a path relinking algorithm with a hypervolume-based multi-objective local search algorithm are investigated.•We evaluate the effectiveness of different path relinking strategies in a multi-objective context.•Different versions of a hybrid multi-objective algorithm are evaluated on a biobjective flow shop problem.