Solving the Resource Constrained Project Scheduling Problem Using the Parallel Tabu Search Designed for the CUDA Platform

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F15%3A00221960" target="_blank" >RIV/68407700:21230/15:00221960 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.jpdc.2014.11.005" target="_blank" >http://dx.doi.org/10.1016/j.jpdc.2014.11.005</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.jpdc.2014.11.005" target="_blank" >10.1016/j.jpdc.2014.11.005</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Solving the Resource Constrained Project Scheduling Problem Using the Parallel Tabu Search Designed for the CUDA Platform

Popis výsledku v původním jazyce

The Resource Constrained Project Scheduling Problem, which is considered to be difficult to tackle even for small instances, is a well-known scheduling problem in the operations research domain. To solve the problem we have proposed a parallel Tabu Search algorithm to find high quality solutions in a reasonable time. We show that our parallel Tabu Search algorithm for graphics cards (GPUs) outperforms other existing Tabu Search approaches in terms of quality of solutions and the number of evaluated schedules per second. Moreover, the algorithm for graphics cards is about 10.5/42.7 times faster (J90 benchmark instances) than the optimized parallel/sequential algorithm for the Central Processing Unit (CPU). The same quality of solutions is achieved up to5.4/22 times faster in comparison to the parallel/sequential CPU algorithm respectively. The advantages of the GPU version arise from the sophisticated data-structures and their suitable placement in the device memory, tailor-made method

Název v anglickém jazyce

Solving the Resource Constrained Project Scheduling Problem Using the Parallel Tabu Search Designed for the CUDA Platform

Popis výsledku anglicky

The Resource Constrained Project Scheduling Problem, which is considered to be difficult to tackle even for small instances, is a well-known scheduling problem in the operations research domain. To solve the problem we have proposed a parallel Tabu Search algorithm to find high quality solutions in a reasonable time. We show that our parallel Tabu Search algorithm for graphics cards (GPUs) outperforms other existing Tabu Search approaches in terms of quality of solutions and the number of evaluated schedules per second. Moreover, the algorithm for graphics cards is about 10.5/42.7 times faster (J90 benchmark instances) than the optimized parallel/sequential algorithm for the Central Processing Unit (CPU). The same quality of solutions is achieved up to5.4/22 times faster in comparison to the parallel/sequential CPU algorithm respectively. The advantages of the GPU version arise from the sophisticated data-structures and their suitable placement in the device memory, tailor-made method

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BB - Aplikovaná statistika, operační výzkum

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2015

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Parallel and Distributed Computing

ISSN

0743-7315

e-ISSN

—

Svazek periodika

77

Číslo periodika v rámci svazku

March

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

11

Strana od-do

58-68

Kód UT WoS článku

000351482400005

EID výsledku v databázi Scopus

2-s2.0-84923783589