A composite multi-criteria search technique for resource-constrained project scheduling problems

This paper proposes an improved SLA^* (search and learning A^* algorithm) for solving resource-constrained project scheduling problems. The objective is to reduce the amount of SLA^* backtracking. Resource utilization and number of parallel processing activities are two new criteria of the proposed algorithm. The proposed algorithm combines those three criteria : (1) resource utilization, (2) total heuristic estimate, and (3) number of parallel processing activities. The composite criteria are used at the front state selection of the SLA^* procedure. The performance of the proposed algorithm is analyzed with different problems. The problems are characterized by problem scale, network complexity, resource factor and resource tightness. Computational results show that the proposed algorithm reduces backtracking more than 50% on average compared to the original SLA^* giving optimal or near optimal solutions