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. The parallel Tabu Search for the Resource Constrained Project Scheduling Problem.To accelerate the algorithm the CUDA optimized version was implemented.A new resources evaluation algorithm was proposed.Promising results in terms of performance and quality of solutions.
Scope and Purpose-A summary is provided of some of the recent (and a few not-so-recent) developments that otTer promise for enhancing our ability to solve combinatorial optimization problems. These developments may be usefully viewed as a synthesis of the perspectives of operations research and artificial intelligence. Although compatible with the use of algorithmic subroutines, the frameworks examined are primarily heuristic, based on the supposition that etTective solution of complex combinatorial structures in some cases may require a level of flexibility beyond that attainable by methods with formally demonstrable convergence properties. This chapter presents the fundamental concepts of Tabu Search (TS) in a tutorial fashion. Special emphasis is put on showing the relationships with classical Local Search methods and on the basic elements of any TS heuristic, namely, the definition of the search space, the neighborhood structure, and the search memory. Other sections cover other important concepts such as search intensification and diversification and provide references to significant work on TS. Recent advances in TS are also briefly discussed.