A genetic algorithm for mode identity and the resource constrained project scheduling problem

AbstractThe Multi-mode Resource Constrained Project Scheduling Problem (MRCPSP) is one of the most important problems in the context of project scheduling. This paper involves a Mode identity and Resource Constrained Project Scheduling Problem (MIRCPSP) to minimize the project makespan. This problem is a more realistic model and a general case of a multi-mode resource constrained project scheduling problem in which the set of project activities is partitioned into disjoint subsets, while all activities forming one subset have to be processed in the same mode. The problem formed in this way is NP-hard, forcing us to develop a meta-heuristic algorithm, namely, the Genetic Algorithm (GA), to obtain a global optimum solution or at least a satisfying one. In addition, the Taguchi experimental design is employed as a statistical optimization technique to calibrate the effective parameters of GA in order to have a robust algorithm. The meta-heuristic algorithm is compared with an exact branch and bound procedure on the basis of a computational experiment performed on a data set constructed by the ProGen/πx project generator. Obtained results show that the performance of the proposed genetic algorithm is quite satisfactory