Iterated Local Search Algorithms For The Resource Constrained Project Scheduling Problem

For resource-constrained project scheduling problem (RCPSP), the main task is to arrange time and resources for activities scheduling projects, rational use of resources to achieve the optimization of the stated objectives. In recent years, due to the need for rapid development of enterprise information and project management, the problem is more extensive research and application, further research on this problem has a good sense of value and application research. For this problem we present a iterated local search algorithm (ILS) for RCPSP.As a simple but efficient and powerful metaheuristic, iterated local search (ILS) algorithm has been successfully applied for solving plenty of combinational optimization problems. In this article ILS algorithm is applied to RCPSP problem, through further improvement and optimization, making it more suitable for RCPSP problem.First, we study in the generation of initial solution, Based on the results of various experiments of outstanding heuristic algorithm, the final choice is we use the earliest start time(EST) priority rule with serial schedule generation scheme(SSGS) to generate an initial solution. Meanwhile, in order to further optimize the local search process to make it more suitable for RCPSP problem, we have studied the algorithm performance of two kinds of local search process and designed using an iterative manner exchange to optimize the local search process of current solution. To overcome the shortcomings of local search process which is easy to fall into local optimum this paper presents a new effective perturbation strategy by dynamically perturbed multiple tasks manner to prevent falling into local optimum. In order to further improve the search efficiency, this paper has studied key critical chain and critical path method. With those improvement strategy, we complete the new local search algorithm for RCPSP.Optimization objective of this paper is to minimize the project’s completion time. Determine the parameters set by the standard data, and finally verify the effectiveness of the algorithm.