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.
From the Tabu Search parallelization point of view @cite_20 proposed a sophisticated solution. The authors use a circular buffer where the size of the buffer is equivalent to the number of the started threads (often the number of CPUs cores). Every location (i.e. an index of a thread) has different parameters (a tabu tenure, stopping criteria). At the beginning of the search each thread initializes its own location by a short TS operator, i.e. a modified version of the Taillard's robust tabu search. Then the asynchronous parallel tabu search is started. Every thread independently reads a solution and parameters from the location, possibly makes a diversification, runs the TS operator on the solution, and writes back and sets an UPDATE flag if an improving solution is found. After that the thread location index is circularly incremented. Diversification takes place if the read solution does not have the UPDATE flag set. Every best global solution is copied to half of the locations of the circular buffer to propagate elite solutions. Since the circular buffer is shared by many threads, the access has to be as short as possible and the locations have to be protected by critical sections.
@cite_20
2044166522
In this study, we introduce a cooperative parallel tabu search algorithm (CPTS) for the quadratic assignment problem (QAP). The QAP is an NP-hard combinatorial optimization problem that is widely acknowledged to be computationally demanding. These characteristics make the QAP an ideal candidate for parallel solution techniques. CPTS is a cooperative parallel algorithm in which the processors exchange information throughout the run of the algorithm as opposed to independent concurrent search strategies that aggregate data only at the end of execution. CPTS accomplishes this cooperation by maintaining a global reference set which uses the information exchange to promote both intensification and strategic diversification in a parallel environment. This study demonstrates the benefits that may be obtained from parallel computing in terms of solution quality, computational time and algorithmic flexibility. A set of 41 test problems obtained from QAPLIB were used to analyze the quality of the CPTS algorithm. Additionally, we report results for 60 difficult new test instances. The CPTS algorithm is shown to provide good solution quality for all problems in acceptable computational times. Out of the 41 test instances obtained from QAPLIB, CPTS is shown to meet or exceed the average solution quality of many of the best sequential and parallel approaches from the literature on all but six problems, whereas no other leading method exhibits a performance that is superior to this.