Combining Variants of Iterative Flattening Search

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 built 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. (C) 2008 Elsevier Ltd. All rights reserved.

Tipo Pubblicazione: 
Articolo
Author or Creator: 
Oddi
A.
Cesta
Policella
N.
Smith
S.F.
Publisher: 
Pineridge,, Swansea , Regno Unito
Source: 
Engineering applications of artificial intelligence 21(5) (2008): 283–290. doi:10.1016/j.engappai.2008.03.003
info:cnr-pdr/source/autori:Oddi, A., Cesta, A., Policella, N., and Smith, S.F./titolo:Combining Variants of Iterative Flattening Search/doi:10.1016/j.engappai.2008.03.003/rivista:Engineering applications of artificial intelligence/anno:2008/pagina_da:283/
Date: 
2008
Resource Identifier: 
http://www.cnr.it/prodotto/i/47086
https://dx.doi.org/10.1016/j.engappai.2008.03.003
info:doi:10.1016/j.engappai.2008.03.003
http://www.sciencedirect.com/science/article/pii/S0952197608000328
ISTC Author: 
Ritratto di Angelo Oddi
Real name: 
Ritratto di Amedeo Cesta
Real name: