Ant colony optimization for resource-constrained project scheduling with generalized precedence relations

Abstract

This paper presents an ant colony optimization (ACO) approach to solve the resource-constrained project scheduling problem (RCPSP) with generalized precedence relations (RCPSP-GPR) with the objective of minimizing the project duration. The general ACO is improved by using the ants with backtracking capabilities and several kinds of heuristic information for solution construction. The combination of direct and summation pheromone evaluation methods and the pseudo-random-proportional action choice rule is also used. The ACO algorithm is tested efficient by using a set of benchmark problems generated by the project generator ProGen/max and performs the best on average among several other heuristic methods.