Hybrid-directional planning: improving improvement heuristics for scheduling resource-constrained projects

摘要

The resource-constrained project scheduling problem (RCPSP) has been of a continuing interest and challenge for researchers and practitioners since its advent. The formidable computational requirements of the RCPSP have resulted in numerous attempts to develop heuristic procedures, leading to the interest in improvement heuristics. Traditionally, such heuristics constructed a schedule by the scheme of forward, backward, or bidirectional planning directions. In this paper, we introduce a hybrid-directional planning that can make all improvement heuristics (e.g., meta-heuristics) more effective in solving the RCPSP. To validate its effectiveness, the proposed scheme is incorporated into three popular meta-heuristics, including genetic algorithm, simulated annealing, and Tabu search. A comprehensive numerical investigation shows that the performance of such meta-heuristics is significantly increased by using the hybrid-directional planning, which indicates that such a hybrid planning direction will hopefully encourage researchers and practitioners to apply it to different improvement heuristics for solving the RCPSP.