Carnegie Mellon University
Iterative Flattening Search for Resource Constrained Scheduling

Angelo Oddi, Nicola Policella, Amedeo Cesta, and Stephen Smith
Journal of Intelligent Manufacturing, 21(1), February 2010., February, 2010.

  • Adobe portable document format (pdf) (242KB)
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.

Iterative Flattening Search (IFS) is a meta-heuristic strategy for solving multi-capacity scheduling problems. Given an initial solution, IFS iteratively applies: (1) a relaxation-step, in which a subset of scheduling decisions are randomly retracted from the current solution; and (2) a flattening-step, in which a new solution is incrementally recomputed from this partial schedule. Whenever a better solution is found, it is retained, and, upon termination, the best solution found during the search is returned. Prior research has shown IFS to be an effective and scalable heuristic procedure for minimiz-ing schedule makespan in multi-capacity resource settings. In this paper we experimentally investigate the impact on IFS performance of algorithmic variants of the flattening step. The variants considered are distinguished by different computational requirements and correspondingly vary in the type and depth of search performed. The analysis is cen-tered around the idea that given a time bound to the over-all optimization procedure, the IFS optimization process is driven by two different and contrasting mechanisms: the ran-dom sampling performed by iteratively applying the “relax-ation/flattening” cycle and the search conducted within the constituent flattening procedure. On one hand, one might expect that efficiency of the flattening process is key: the faster the flattening procedure, the greater the number of it-erations (and number of sampled solutions) for a given time bound; and hence the greater the probability of finding bet-ter quality solutions. On the other hand, the use of more ac-curate (and more costly) flattening procedures can increase the probability of obtaining better quality solutions even if their greater computational cost reduces the number of IFS iterations. Comparative results on well-studied benchmark problems are presented that clarify this tradeoff with respect to previously proposed flattening strategies, identify quali-tative guidelines for the design of effective IFS procedures, and suggest some new directions for future work in this area.

Scheduling, meta-heuristics, iterative sampling


Text Reference
Angelo Oddi, Nicola Policella, Amedeo Cesta, and Stephen Smith, "Iterative Flattening Search for Resource Constrained Scheduling," Journal of Intelligent Manufacturing, 21(1), February 2010., February, 2010.

BibTeX Reference
   author = "Angelo Oddi and Nicola Policella and Amedeo Cesta and Stephen Smith",
   title = "Iterative Flattening Search for Resource Constrained Scheduling",
   booktitle = "Journal of Intelligent Manufacturing, 21(1), February 2010.",
   month = "February",
   year = "2010",
   number= "CMU-RI-TR-",