Iterative Flattening Search for Multi-Capacity Scheduling Problems

Oddi, A., Cesta, A., Policella, N., and Smith, S.F

In CAEPIA 2007 Workshop on Planning, Scheduling and Constraint Satisfaction, Salamanca, Spain, 2007

Iterative Flattening Search (IFS) is an iterative improvement heuristic schema for solving scheduling problems. Given an initial solution, IFS iteratively applies two-steps: (1) a subset of solving decisions are randomly retracted from a current solution (relaxation-step); (2) a new solution is incrementally recomputed (flattening-step). The aim of this work is to experimentally evaluate the different IFS variations which have been proposed so far. Specifically, we examine the utility of: (1) operating with different relaxation strategies; (2) using different strategies to built a new solution. The experimental results shed light on the weaknesses and the strengths of the different variants and suggest potentials for the synthesis of more effective IFS procedures.