A bi-population genetic algorithm with two novel greedy mode selection methods for MRCPSP

The multimode resource-constrained project scheduling problem (MRCPSP) is an extension of the single-mode resource-constrained project scheduling problem (RCPSP). In this problem, each project contains a number of activities which precedence relationship exist between them besides their amount of resource requirements to renewable and non-renewable resources are limited to the resources availabilities. Moreover, each activity has several execution modes, that each of them has its amount of resource requirements and execution duration. The MRCPSP is NP-hard, in addition, proved that if at least 2 non-renewable resources existed, finding a feasible solution for it is NP-complete. This paper introduces two greedy mode selection methods to assign execution modes of the primary schedules’ activities in order to balance their resource requirements and thus reduce the number of infeasible solutions in the initialization phase of a bi-population genetic algorithm for the problem. To investigate the usage effect of these greedy methods on the quality of the final results, in addition, to evaluating the performance of the proposed algorithm versus the other meta-heuristics, the instances of the PSPLIB standard library have been solved. The computational results show that by the growth of the problem size, the proposed algorithm reports better results in comparison with the other metaheuristics in the problem literature.

کلیدواژه ها:

Resource-constrained project scheduling ، Multi-mode ، Genetic algorithm ، Makespan ، Initialization