Solving the Resource Constrained Project Scheduling Problem Using the Parallel Tabu Search Designed for the CUDA Platform
This work addresses scheduling optimization for resource-constrained projects, offering incremental improvements in efficiency and solution quality for combinatorial problem-solving in operations research.
The paper tackles the NP-hard Resource Constrained Project Scheduling Problem by proposing a parallel Tabu Search algorithm optimized for CUDA GPUs, resulting in the GPU version outperforming an optimized CPU version in computational time and solution quality, often providing better solutions than existing heuristics.
In the paper, a parallel Tabu Search algorithm for the Resource Constrained Project Scheduling Problem is proposed. To deal with this NP-hard combinatorial problem many optimizations have been performed. For example, a resource evaluation algorithm is selected by a heuristic and an effective Tabu List was designed. In addition to that, a capacity-indexed resource evaluation algorithm was proposed and the GPU (Graphics Processing Unit) version uses a homogeneous model to reduce the required communication bandwidth. According to the experiments, the GPU version outperforms the optimized parallel CPU version with respect to the computational time and the quality of solutions. In comparison with other existing heuristics, the proposed solution often gives better quality solutions.