Solving the Resource Constrained Project Scheduling Problem using the parallel Tabu Search designed for the CUDA platform

View Researcher's Other Codes

Disclaimer: The provided code links for this paper are external links. Science Nest has no responsibility for the accuracy, legality or content of these links. Also, by downloading this code(s), you agree to comply with the terms of use as set out by the author(s) of the code(s).

Please contact us in case of a broken link from here

Authors Libor Bukata, Přemysl Šůcha, Zdeněk Hanzálek
Journal/Conference Name Journal of Parallel and Distributed Computing
Paper Category
Paper Abstract The Resource Constrained Project Scheduling Problem, which is considered to be difficult to tackle even for small instances, is a well-known scheduling problem in the operations research domain. To solve the problem we have proposed a parallel Tabu Search algorithm to find high quality solutions in a reasonable time. We show that our parallel Tabu Search algorithm for graphics cards (GPUs) outperforms other existing Tabu Search approaches in terms of quality of solutions and the number of evaluated schedules per second. Moreover, the algorithm for graphics cards is about 10.5/42.7 times faster (J90 benchmark instances) than the optimized parallel/sequential algorithm for the Central Processing Unit (CPU). The same quality of solutions is achieved up to 5.4/22 times faster in comparison to the parallel/sequential CPU algorithm respectively. The advantages of the GPU version arise from the sophisticated data-structures and their suitable placement in the device memory, tailor-made methods, and last but not least the effective communication scheme.
Date of publication 2014
Code Programming Language Cuda
Comment

Copyright Researcher 2022