Solving the permutation problem efficiently for Tabu search on CUDA GPUs

Liang Tsung Huang, Syun Sheng Jhan, Yun Ju Li, Chao Chin Wu

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

NVIDIA’s Tesla Graphics Processing Units (GPUs) have been used to solve various kinds of long running-time applications because of their high performance compute power. A GPU consists of hundreds or even thousands processor cores and adopts (Single Instruction Multiple Threading) SIMT) architecture. This paper proposes an approach that optimizes the Tabu Search algorithm for solving the Permutation Flowshop Scheduling Problem (PFSP) on a GPU. We use a math function to generate all different permutations, avoiding the need of placing all the permutations in the global memory. Experimental results show that the GPU implementation of our proposed Tabu Search for PFSP runs up to 90 times faster than its CPU counterpart.

Original languageEnglish
Pages (from-to)342-352
Number of pages11
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8733
Publication statusPublished - 2014 Jan 1

Fingerprint

Tabu search
Graphics Processing Unit
Tabu Search
Permutation
Permutation Flowshop
Flow Shop Scheduling
Scheduling Problem
Scheduling
Tabu Search Algorithm
Program processors
High Performance
Optimise
Data storage equipment
Graphics processing unit
Experimental Results

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

@article{35d2145ddb7e42d9a7e78d9d60907325,
title = "Solving the permutation problem efficiently for Tabu search on CUDA GPUs",
abstract = "NVIDIA’s Tesla Graphics Processing Units (GPUs) have been used to solve various kinds of long running-time applications because of their high performance compute power. A GPU consists of hundreds or even thousands processor cores and adopts (Single Instruction Multiple Threading) SIMT) architecture. This paper proposes an approach that optimizes the Tabu Search algorithm for solving the Permutation Flowshop Scheduling Problem (PFSP) on a GPU. We use a math function to generate all different permutations, avoiding the need of placing all the permutations in the global memory. Experimental results show that the GPU implementation of our proposed Tabu Search for PFSP runs up to 90 times faster than its CPU counterpart.",
author = "Huang, {Liang Tsung} and Jhan, {Syun Sheng} and Li, {Yun Ju} and Wu, {Chao Chin}",
year = "2014",
month = "1",
day = "1",
language = "English",
volume = "8733",
pages = "342--352",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Springer Verlag",

}

TY - JOUR

T1 - Solving the permutation problem efficiently for Tabu search on CUDA GPUs

AU - Huang, Liang Tsung

AU - Jhan, Syun Sheng

AU - Li, Yun Ju

AU - Wu, Chao Chin

PY - 2014/1/1

Y1 - 2014/1/1

N2 - NVIDIA’s Tesla Graphics Processing Units (GPUs) have been used to solve various kinds of long running-time applications because of their high performance compute power. A GPU consists of hundreds or even thousands processor cores and adopts (Single Instruction Multiple Threading) SIMT) architecture. This paper proposes an approach that optimizes the Tabu Search algorithm for solving the Permutation Flowshop Scheduling Problem (PFSP) on a GPU. We use a math function to generate all different permutations, avoiding the need of placing all the permutations in the global memory. Experimental results show that the GPU implementation of our proposed Tabu Search for PFSP runs up to 90 times faster than its CPU counterpart.

AB - NVIDIA’s Tesla Graphics Processing Units (GPUs) have been used to solve various kinds of long running-time applications because of their high performance compute power. A GPU consists of hundreds or even thousands processor cores and adopts (Single Instruction Multiple Threading) SIMT) architecture. This paper proposes an approach that optimizes the Tabu Search algorithm for solving the Permutation Flowshop Scheduling Problem (PFSP) on a GPU. We use a math function to generate all different permutations, avoiding the need of placing all the permutations in the global memory. Experimental results show that the GPU implementation of our proposed Tabu Search for PFSP runs up to 90 times faster than its CPU counterpart.

UR - http://www.scopus.com/inward/record.url?scp=84921650946&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84921650946&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:84921650946

VL - 8733

SP - 342

EP - 352

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -