File(s) under permanent embargo
A parallel Lagrangian-ACO heuristic for project scheduling
conference contribution
posted on 2014-01-01, 00:00 authored by O Brent, Dhananjay ThiruvadyDhananjay Thiruvady, A Gómez-Iglesias, R García-FloresIn 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.
History
Event
IEEE Computational Intelligence Society. Conference (2014 : Beijing, China)Series
IEEE Computational Intelligence Society ConferencePagination
2985 - 2991Publisher
Institute of Electrical and Electronics EngineersLocation
Beijing, ChinaPlace of publication
Piscataway, N.J.Publisher DOI
Start date
2014-07-06End date
2014-07-11ISBN-13
9781479914883Language
engPublication classification
E1.1 Full written paper - refereedCopyright notice
2014, IEEEEditor/Contributor(s)
[Unknown]Title of proceedings
IEEE CEC 2014 : Proceedings of the 2014 IEEE Congress on Evolutionary ComputationUsage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC