Name
Abstract | ||
|---|---|---|
In this paper we present a parallel implementation of an existing Lagrangian heuristic for solving a project scheduling problem. The original implementation uses Lagrangian 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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/CEC.2014.6900504 | Evolutionary Computation |
Keywords | Field | DocType |
ant colony optimisation,memory architecture,multiprocessing systems,parallel algorithms,processor scheduling,shared memory systems,ant colony optimisation,lower bounds,multicore shared memory architecture,parallel Lagrangian-ACO heuristic,project scheduling problem,upper bounds | Schedule (project management),Mathematical optimization,Heuristic,Upper and lower bounds,Computer science,Scheduling (computing),Parallel computing,Schedule,Lagrangian relaxation,Ant colony,Multi-core processor | Conference |
Citations | PageRank | References |
2 | 0.39 | 7 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oswyn Brent | 1 | 2 | 0.39 |
| Dhananjay R. Thiruvady | 2 | 16 | 4.42 |
| Antonio Gomez-Iglesias | 3 | 2 | 0.39 |
| Rodolfo García-Flores | 4 | 42 | 5.28 |
| Gomez-Iglesias, A. | 5 | 2 | 0.39 |
| Garcia-Flores, R. | 6 | 2 | 0.39 |