Reconstructing permutation table to improve the Tabu Search for the PFSP on GPU

Kai Cheng Wei, Xue Sun, Hsun Chu, Chao Chin Wu

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


General-purpose computing on graphics processing unit (GPGPU) has been adopted to accelerate the running of applications which require long execution time in various problem domains. Tabu Search belonging to meta-heuristics optimization has been used to find a suboptimal solution for NP-hard problems within a more reasonable time interval. In this paper, we have investigated in how to improve the performance of Tabu Search algorithm on GPGPU and took the permutation flow shop scheduling problem (PFSP) as the example for our study. In previous approach proposed recently for solving PFSP by Tabu Search on GPU, all the job permutations are stored in global memory to successfully eliminate the occurrences of branch divergence. Nevertheless, the previous algorithm requires a large amount of global memory space, because of a lot of global memory access resulting in system performance degradation. We propose a new approach to address the problem. The main contribution of this paper is an efficient multiple-loop struct to generate most part of the permutation on the fly, which can decrease the size of permutation table and significantly reduce the amount of global memory access. Computational experiments on problems according with benchmark suite for PFSP reveal that the best performance improvement of our approach is about 100%, comparing with the previous work.

Original languageEnglish
Pages (from-to)4711-4738
Number of pages28
JournalJournal of Supercomputing
Issue number11
Publication statusPublished - 2017 Nov 1

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Information Systems
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Reconstructing permutation table to improve the Tabu Search for the PFSP on GPU'. Together they form a unique fingerprint.

Cite this