A hybrid decomposition procedure for scheduling projects under multiple resource constraints

This paper presents a hybrid decomposition procedure for solving the resource‐constrained project scheduling problem. The procedure finds an initial schedule for the project, and refines it through a decomposition process. This is performed through a refinement process which consists of (i) analyzing the initial schedule to find appropriate decomposition point(s), (ii) decomposing the associated project into appropriate subprojects, (iii) optimizing the subprojects by an efficient implicit enumeration technique, and subsequently (iv) integrating optimal sub‐schedules to create a feasible schedule. This refinement process is aimed at reducing the makespan of the initial schedule. To achieve further reduction, the refined schedule is overrefined by a genetic algorithm. The results of computational experiments performed on 2,040 benchmark instances indicate that in a reasonable time the procedure can obtain solutions whose average percentage deviation from their associated best solutions in the litrature is 0.41.