A GPU-accelerated Branch-and-Bound Algorithm for the Flow-Shop Scheduling Problem

Abstract : Branch-and-Bound (B&B) algorithms are time intensive tree-based exploration methods for solving to optimality combinatorial optimization problems. In this paper, we investigate the use of GPU computing as a major complementary way to speed up those methods. The focus is put on the bounding mechanism of B&B algorithms, which is the most time consuming part of their exploration process. We propose a parallel B&B algorithm based on a GPU-accelerated bounding model. The proposed approach concentrate on optimizing data access management to further improve the performance of the bounding mechanism which uses large and intermediate data sets that do not completely fit in GPU memory. Extensive experiments of the contribution have been carried out on well known FSP benchmarks using an Nvidia Tesla C2050 GPU card. We compared the obtained performances to a single and a multithreaded CPU-based execution. Accelerations up to x100 are achieved for large problem instances.
Type de document :
Communication dans un congrès
14th IEEE International Conference on Cluster Computing, Cluster'12, Sep 2012, Beijin, China. 2012
Liste complète des métadonnées

https://hal.inria.fr/hal-00723736
Contributeur : Imen Chakroun <>
Soumis le : samedi 18 août 2012 - 14:54:43
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : lundi 19 novembre 2012 - 02:20:09

Fichiers

CLUSTER.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00723736, version 1
  • ARXIV : 1208.3933

Citation

Nouredine Melab, Imen Chakroun, Mohand Mezmaz, Daniel Tuyttens. A GPU-accelerated Branch-and-Bound Algorithm for the Flow-Shop Scheduling Problem. 14th IEEE International Conference on Cluster Computing, Cluster'12, Sep 2012, Beijin, China. 2012. 〈hal-00723736〉

Partager

Métriques

Consultations de la notice

472

Téléchargements de fichiers

308