A novel heuristic algorithm with activity back-shift response model for resource-constrained project scheduling problem

The resource-constrained project scheduling problem is one of the most intractable problems in the field of operation research and management science. It is important for both academic research and engineering applications to develop effective solution algorithms for scheduling problems. In this paper, the activity back-shift response model is introduced for scheduling problems, based on which a resource-constrained scheduling model is built, and a two-phase decomposition algorithm is proposed to address the project resource-constraint and timing optimization. The first stage is resource optimization, where the conflicted activities are resolved by a genetic algorithm. In this case, if parallel activities are scrambling resources during resource optimization, the activity priority, determined by comparing the activity back-shift response time, is applied to dissolve the resource conflict. The second stage is timing optimization. After obtaining the progress plan with optimized resource constraints, activities are adjusted to move forward as much as possible. The validity of the proposed algorithm is verified by a real project case. The computational results reveal that the proposed model and algorithm obtain appropriate results and have the potential to be applied to other similar problems.