GPU-Based Two Level Parallel B&B for the Blocking Job Shop Scheduling Problem - LAAS - Laboratoire d'Analyse et d'Architecture des Systèmes Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

GPU-Based Two Level Parallel B&B for the Blocking Job Shop Scheduling Problem

Résumé

Branch and bound algorithm (B&B) is a well known technique for solving optimally combinatorial optimization problems. Nevertheless, these algorithms remain inefficient when dealing with large instances. This paper deals with the blocking job shop scheduling (BJSS) problem, which is a version of classical job shop scheduling problem with no intermediate buffer between machines. This problem is an NP-hard problem and its exact resolution using the sequential approach is impractical. We propose in this paper a GPU-based parallelization in which a two level scheme is used. The first level is a node-based parallelization in which the bounding process is faster because it is calculated in parallel using several threads organized in one GPU block. To fully occupy the GPU, we propose a second level of parallelization which is a generalization of the first level. Therefore, at each iteration, several search tree nodes are evaluated on the GPU using several thread-blocks. The obtained results, using the well-known Taillard instances, confirm the efficiency of the proposed approach. Also, the results show that our approach is 65 times faster than an optimized sequential B&B version.
Fichier principal
Vignette du fichier
Pco.pdf (289.02 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02115751 , version 1 (30-04-2019)

Identifiants

Citer

Adel Dabah, Ahcène Bendjoudi, Didier El Baz, Abdelhakim Aitzai. GPU-Based Two Level Parallel B&B for the Blocking Job Shop Scheduling Problem. IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW 2016), May 2016, Chicago, United States. pp.747-755, ⟨10.1109/IPDPSW.2016.14⟩. ⟨hal-02115751⟩
64 Consultations
9 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More