An Efficient Imperialist Competitive Algorithm for Resource Constrained Project Scheduling Problem

Abstract

In this paper, a new algorithm based on the framework of the imperialist competitive algorithm for solving resource constrained project scheduling problem (RCPSP) will be proposed. In this problem, the activities are scheduled based on the resource and precedence relationships constraints in a way that the makes pan will be minimized. In order to model the assimilation process, a uniform crossover has been used, and to avoid premature convergence of the proposed algorithm, two revolution operators including one point revolution and multi-point revolution will be introduced. Also, in order to enhance the exploitation ability, a combined local search including permutation based local search (PBLS) and forward-backward improvement (FBI) is performed. The algorithm parameters are determined by designing Taguchi experiment, and the efficiency of proposed ICA is demonstrated by solving PSPLIB problems. Computational results and comparisons with some existing algorithms show that the proposed algorithm can produce near-optimal solution for small problems and competitive solution for large ones.