Combining variants of iterative flattening search

Abstract

Iterative flattening search (IFS) is an iterative improvement heuristic schema for makespan minimization in scheduling problems. Given an initial solution, IFS iteratively interleaves a relaxation-step, which randomly retracts some search decisions, and an incremental solving step (or flattening-step) to recompute a new solution. The process continues until a stop condition is met and the best solution found is returned. In recent work we have created a uniform software framework to analyze component techniques that have been proposed in IFS approaches. In this paper we combine basic components to obtain hybrid variants and perform a detailed experimental evaluation of their performance. Specifically, we examine the utility of: (1) operating with different relaxation strategies and (2) using different searching strategies to build a new solution. We present a two-step experimental evaluation: (a) an extensive explorative evaluation with a spectrum of parameter combination; (b) a time-intensive evaluation of the best IFS combinations emerged from the previous. The experimental results shed light on weaknesses and strengths of the different variants improving the current understanding of this family of meta-heuristics.