Abstract: To effectively reduce the complexity and solution space of the multi-mode resource-constrained project scheduling model, three mixed-integer linear programming models are established in this paper. The upper bound of time series T is reduced by using the tight upper bound T_TUB, while the upper and lower bounds of the completion time of each activity are reduced by using the critical path method. Thereby, complexity and solution space of the model are reduced. 1106 instances with different scales are selected from the MRCPSP benchmark library to verify the effectiveness of the improved model. Results show that the CPM-based multi-mode resource-constrained project scheduling model has smaller solution space; the number of decision variables is reduced by 3~65 times, and the number of constraints is reduced by 1~4 times; the average computation time is decreased by 53%~112%, resulting in that the performance of the proposed model is significantly better than that of others. Moreover, the results of the 1106 instances also indicate that the closer α is to 1, the lower the complexity and the smaller the solution space of the model, which verifies the performance of parameter α. But the difficulty of exploring feasible solutions increases with the increase of instance scales. Therefore, the value of α should be appropriately relaxed for large-scale instances.

Key words: multi-mode resource-constrained project scheduling, model complexity, solution space, upper bound, mixed-integer linear programming model