Chao-Chin Wu¹, Kai-Cheng Wei¹, Wei-Shen Lai², Yun-Ju Li¹,
¹National Changhua University of Education, Taiwan and ²Chienkuo Technology University, Taiwan

Graphics Processing Units (GPUs) have been emerged as powerful parallel compute platforms for various application domains. A GPU consists of hundreds or even thousands processor cores and adopts Single Instruction Multiple Threading (SIMT) architecture. Previously, we have proposed an approach that optimizes the Tabu Search algorithm for solving the Permutation Flowshop Scheduling Problem (PFSP) on a GPU by using a math function to generate all different permutations, avoiding the need of placing all the permutations in the global memory. Based on the research result, this paper proposes another approach that further improves the performance by avoiding duplicated computation among threads, which is incurred when any two permutations have the same prefix. Experimental results show that the GPU implementation of our proposed Tabu Search for PFSP runs up to 1.5 times faster than another GPU implementation proposed by Czapiński and Barnes.

GPU, CUDA, Parallel algorithm, Tabu Search, Permutation Flowshop Scheduling Problem