Angelo Oddi, Riccardo Rasconi

In 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},
}