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

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

研究成果: Article同行評審

4 引文 斯高帕斯(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.

頁(從 - 到)4711-4738
期刊Journal of Supercomputing
出版狀態Published - 2017 十一月 1

All Science Journal Classification (ASJC) codes

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

指紋 深入研究「Reconstructing permutation table to improve the Tabu Search for the PFSP on GPU」主題。共同形成了獨特的指紋。