Accelerating a Flow Shop Algorithm on the GPU
Result description
We present a GPGPU (General-Purpose computing on Graphics Processing Units) based approach to combinatorial problems, specifically to the permutation flow shop scheduling problem. Presented genetic algorithm uses the homogeneous computing model in orderto maximize the algorithm performance. The algorithm is based on work presented by Pospichal et al. In our paper, we suggest several improvements (e.g. another mechanism for individuals migration, more efficient problem representation) allowing to applythis algorithm on a wider group of NP-hard combinatorial problems. Our experimental results show significant speedup with respect to the sequential algorithm version.
Keywords
The result's identifiers
Result code in IS VaVaI
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Accelerating a Flow Shop Algorithm on the GPU
Original language description
We present a GPGPU (General-Purpose computing on Graphics Processing Units) based approach to combinatorial problems, specifically to the permutation flow shop scheduling problem. Presented genetic algorithm uses the homogeneous computing model in orderto maximize the algorithm performance. The algorithm is based on work presented by Pospichal et al. In our paper, we suggest several improvements (e.g. another mechanism for individuals migration, more efficient problem representation) allowing to applythis algorithm on a wider group of NP-hard combinatorial problems. Our experimental results show significant speedup with respect to the sequential algorithm version.
Czech name
—
Czech description
—
Classification
Type
O - Miscellaneous
CEP classification
JD - Use of computers, robotics and its application
OECD FORD branch
—
Result continuities
Project
GPP103/10/P401: Optimization Algorithms for the Project Scheduling Problem
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2011
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Basic information
Result type
O - Miscellaneous
CEP
JD - Use of computers, robotics and its application
Year of implementation
2011