Tabu Search with two approaches to parallel flowshop evaluation on CUDA platform

Michal Czapinski, Stuart Barnes
Applied Mathematics and Computing Group, Cranfield University, College Road, Cranfield, Bedfordshire, MK43 0AL, United Kingdom
Journal of Parallel and Distributed Computing (02 March 2011)


   title={Tabu Search with two approaches to parallel flowshop evaluation on CUDA platform},

   author={Czapinski, M. and Barnes, S.},

   journal={Journal of Parallel and Distributed Computing},





Source Source   



The introduction of NVidia’s powerful Tesla GPU hardware and Compute Unified Device Architecture (CUDA) platform enable many-core parallel programming. As a result, existing algorithms implemented on a GPU can run many times faster than on modern CPUs. Relatively little research has been done so far on GPU implementations of discrete optimisation algorithms. In this paper, two approaches to parallel GPU evaluation of Permutation Flowshop Scheduling Problem, with makespan and total flowtime criteria, are proposed. These methods can be employed in most population-based algorithms, e.g. genetic algorithms, Ant Colony Optimisation, Particle Swarm Optimisation, and Tabu Search. Extensive computational experiments, on Tabu Search for Flowshop with both criteria, followed by statistical analysis, confirm great computational capabilities of GPU hardware. A GPU implementation of Tabu Search runs up to 89 times faster than its CPU counterpart.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: