Keywords: ant colony optimization, critical path, resource-constrained construction scheduling.

One of the pillars of project management is the need to "map" a project's sequence of activities from start to completion, and the ability to solve the resulting flow network for the activities that are most critical to successful project completion. Within this framework of mapping a project's logic diagram (i.e. the flow of activities) and identifying the activities that are the most critical to accomplishing specified milestones, the science of construction scheduling has gained in importance and has become the focal point of construction management practitioners.

Currently, the most widely used method for analyzing construction project networks and solving for longest (critical) paths in such networks is the Critical Path Method (CPM), a deterministic approach that relies on forward and backward pass calculations to identify and solve for the critical path in a network (critical being the sequence of activities from project start to project end that results in the longest path in the network, thus defining the project's duration). The longest path calculations and all relevant time and resource optimizations are typically performed by linear programming and optimization algorithms, subject to imposed constraints (time, resource and logic constraints).

The paper presents an alternative methodology to perform critical path calculations using algorithms based on the Ant Colony Optimization (ACO) metaheuristic. ACO is a population-based, artificial multi-agent, general-search technique for the solution of difficult combinatorial problems. The method's theoretical roots are based on the behaviour of real ant colonies and the collective trail-laying and trail-following of its members in searching for optimal solutions in traversing multiple paths. In essence, ACO is inspired by the foraging behaviour of natural ant colonies which optimize their path from an origin (ant nest) to a destination (food source) by taking advantage of knowledge acquired by ants that previously traversed the possible paths, and the pheromone trail that these ants left behind as they traversed the paths to optimal solution.

The work presented builds on previous work on critical path calculations by use of ACO, and presents a methodology to extend the ACO solution algorithms to account for resource-constrained construction sequences. The suggested possible implementation strategy is preceded by an outline of the fundamental mathematical background of the ACO method. The methodology is examined by means of a case study construction schedule and the results are compared to the ones obtained by traditional CPM calculations, concluding that the ACO metaheuristic provides users with an alternative way of constructing longest-path solutions in acyclic (unidirectional) network topologies.

Further to the longest-path calculations, the applied ACO methodology is shown to be applicable to resource flows, and node-to-node longest path calculations. The former is achieved by considering the respective activity assignments and including them in the cost function of each arc used in the optimization process. The presented work concludes with an algorithm developed for solving the resource-constrained problem by use of ACO, and the results from a sample application.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £62 +P&P)