The Robotics Institute

Carnegie Mellon Robotics Institute

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

Iterative ﬂattening 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 ﬂattening-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. Speci ﬁcally, we exami ne the utility of: (1) operating with different relaxation strategies and (2) usin g different searching s trategies to buil t a new solut ion. We present a two-step experim ental evalu ation: (a) an extensive explorative evaluat ion with a spect rum of parameter comb inati on; (b) a time-i ntensive evalua tion 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

Keywords

Scheduling, Local search, Constraint satisfaction,Iterative improvement,Stochastic search

Notes

Text Reference

Angelo Oddi, Amedeo Cesta, Nicola Policella, and Stephen Smith , "Combining variants of iterative ﬂattening search," Engineering Applications of Artificial Intelligence, 21 (5): 683-690, August, 2009., August, 2009.

BibTeX Reference

@inproceedings{Oddi_2009_7055,
   author = "Angelo Oddi and Amedeo Cesta and Nicola Policella and Stephen {Smith }",
   title = "Combining variants of iterative ﬂattening search",
   booktitle = "Engineering Applications of Artificial Intelligence, 21 (5): 683-690, August, 2009.",
   month = "August",
   year = "2009",
   number= "CMU-RI-TR-",
}

The Robotics Institute

Menu