Experimental investigation of the applicability of ant colony optimization algorithms for project scheduling

摘要

Ant Colony Optimization (ACO) algorithms have recently been developed.These are algorithms that have taken inspiration from the observation of ant colonies' foraging behaviour. Although a lot of effort has already been put into the development of ACO algorithms for multiple fields of application, the research for the resource-constrained project scheduling problem (RCPSP) has remained scarce. This problem is an NP -hard optimization problem that aims at minimizing the makespan of a project consisting of activities which have to be processed under two types of constraints, namely precedence and resource constraints. In this paper, we investigate the applicability of ACO for the RCPSP. First, we study the basic features of ant algorithms and look at some implementations for the RCPSP. Then, we break down the algorithm into its constituent procedures and examine various mechanisms to come to a better understanding of the algorithmic performance. Computational experiments are performed on standard benchmark datasets. Our experiments result in two full-fledged ant algorithms for the RCPSP. Finally, we compare the performance of these two algorithms with existing ACO algorithms and with other non-hybrid heuristics taken from literature. This comparison allows us to predict very good results for hybrid versions of ACO algorithms for the RCPSP.