This paper proposes an iterative improvement algorithm for solving instances of the Resource Constraint Project Scheduling Problem with Time-Windows (RCPSP/max). The algorithm is based on Iterative Flattening Search (ifs), an effective meta-heuristic strategy proposed over the past years 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 this is the first paper which proposes a version of ifs for solving RCPSP/max instances. The main contribution of this paper is threefold: (1) we succeed in improving 15 out of 90 solutions with respect to the officially published current best, thus demonstrating the general efficacy of ifs; (2) we highlight an intrisic limitation of the original ifs strategy in solving RCPSP/max, such that under certain circumstances the two-step improvement loop can get stuck in a status where no solving decision can be retracted; (3) we propose two different escaping strategies which extend the original ifs procedure. An experimental evaluation ends the paper, comparing the performances of the proposed escaping strategies against the original ifs procedure.
Iterative Flattening Search on RCPSP/max Problems: Recent Developments
Contributo in volume
Springer-Verlag Berlin, Berlin, DEU
Recent Advances in Constraints 13th Annual ERCIM International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2008, Rome, Italy, June 18-20, 2008, Revised Selected Papers, pp. 99–115. Berlin: Springer-Verlag Berlin, 2009