An Electromagnetism Meta-Heuristic For The Resource-Constrained Project Scheduling Problem

Recently, a new heuristic algorithm for global optimization has been proposed by Birbil and Fang (2003), referred to as Electromagnetism (EM). This technique is based on the electromagnetism theory of physics, and simulates attraction and repulsion of sample points in order to move towards an optimal solution. In this paper, we have extended the EM methodology for combinatorial optimization problems. To that purpose, we use the EM framework for solving the well-known resource-constrained project scheduling problem (RCPSP) heuristically. We rely on problem-specific characteristics to adapt the original EM framework to the problem under study. We present computational experiments on a standard benchmark dataset, compare the results of the different modifications on the original EM framework with current state-of-the-art heuristics, and show that the procedure is capable of producing consistently good results for challenging instances of the resource-constrained project scheduling problem. We also give directions for future research in order to make the EM framework competitive with the current state-of-the-art heuristics.