An efficient random key-based genetic algorithm for solving multimode resource-constrained project scheduling problem

The multimode resource-constrained project scheduling problem (MRCPSP) is recognized as a well-known NP-hard combinatorial optimization problem. It incorporates both renewable and nonrenewable resources, along with multiple modes of each task, thereby offering a more accurate representation of real-world construction project scheduling scenarios. The paper proposes a novel genetic algorithm (GA) with three key innovations for the MRCPSP. First, a feasible mode assignment algorithm with a threshold-based selection strategy is introduced, which rapidly identifies feasible individuals of the initial population to satisfy the nonrenewable resource constraints. Second, a modified multimode forward and backward improvement (MMFBI) technique is developed as a local search approach to dynamically improve the schedules. Third, a GA framework is designed incorporating four key components: (1) an encoding scheme structure to enhance genetic operations; (2) a random key adjustment mechanism to reduce redundant search spaces; (3) a hierarchical search strategy to balance global exploration and local exploitation across individuals at different fitness levels; and (4) a feasible solution preservation mechanism throughout evolutionary process. The algorithm's performance was rigorously evaluated against the state-of-the-art metaheuristics using the multimode benchmark library (MMLIB) and a construction project. It identified 5 new best-known solutions (BKS) for both MM50 and MM100 (each data set containing 540 instances) and 277 new BKS for the MMplus data set (containing 3,240 instances). These results underscore the effectiveness of the algorithm and its potential to advance the field of construction project scheduling optimization problem.