A parallel Lagrangian-ACO heuristic for project scheduling

Oswyn Brent, Dhananjay Thiruvady, Antonio Gómez-Iglesias, Rodolfo García-Flores

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

9 Citations (Scopus)


In this paper we present a parallel implementation of an existing Lagrangian heuristic for solving a project scheduling problem. The original implementation uses La-grangian relaxation to generate useful upper bounds and provide guidance towards generating good lower bounds or feasible solutions. These solutions are further improved using Ant Colony Optimisation via loose and tight couplings. While this approach has proven to be effective, there are often large gaps for a number of the problem instances. Thus, we aim to improve the performance of this algorithm through a parallel implementation on a multicore shared memory architecture. However, the original algorithm is inherently sequential and is not trivially parallelisable due to the dependencies between the different components involved. Hence, we propose different approaches to carry out this parallelisation. Computational experiments show that the parallel version produces consistently better results given the same time limits.

Original languageEnglish
Title of host publication2014 IEEE Congress on Evolutionary Computation (CEC)
PublisherIEEE, Institute of Electrical and Electronics Engineers
Number of pages7
ISBN (Electronic)9781479914883
Publication statusPublished - 16 Sep 2014
Externally publishedYes
EventIEEE Congress on Evolutionary Computation 2014 - Beijing, China
Duration: 6 Jul 201411 Jul 2014
https://ieeexplore.ieee.org/xpl/conhome/6880677/proceeding (Proceedings)


ConferenceIEEE Congress on Evolutionary Computation 2014
Abbreviated titleIEEE CEC 2014
Internet address

Cite this