Angelo Oddi, Riccardo RasconiIn this work we propose an iterative improvement heuristic for solving the Resource Constraint Project Scheduling Problem with Time-Windows (RCPSP/max), a challenging NP-hard scheduling problem. The algorithmis based on Iterative Flattening Search (IFS), an effective meta-heuristic strategy for solving multi-capacity optimization 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). At the end, the best solution found is returned. To the best of our knowledge no paper is available in the current literature which proposes a version of IFS for solving RCPSP/max instances. One of the main contribution of this work is the discovery of an intrinsic limitation of the original IFS strategy in solving RCPSP/max, occurring in those cases where the two-step improvement loop can get stuck in a status where no solving decision can be retracted. Hence, we propose two different escaping strategies which extend the original IFS procedure. An experimental evaluation ends the paper, where we compare the performance of the proposed escaping strategies against the original IFS procedure. We succeed in improving 18 out of 90 solutions with respect to the officially published current bests, in particular we discovered two new optimal solutions, thus demonstrating the general efficacy of IFS. @Inproceedings{OddiRasconi, author = {Angelo Oddi and Riccardo Rasconi}, title ={Iterative Improvement Heuristics for Resource Constrained Scheduling with Time Windows}, year = {2008}, editor = {Marco Gavanelli and Toni Mancini}, booktitle = {R.i.C.e.R.c.A. 2008: RCRA Incontri E Confronti}, } |