• français
    • English
  • français 
    • français
    • English
  • Ouvrir une session
  • CGU
  • -
  • About
  • -
  • Contact
  • -
  • Team
Voir le document 
  •   CERIST DL
  • Articles Scientifiques
  • Rapports de Recherche Internes
  • Voir le document
  •   CERIST DL
  • Articles Scientifiques
  • Rapports de Recherche Internes
  • Voir le document
JavaScript is disabled for your browser. Some features of this site may not work without it.

Parcourir

Tout DLCommunautés & CollectionsPar date de publicationAuteursTitresSujetsCette collectionPar date de publicationAuteursTitresSujets

Mon compte

Ouvrir une sessionS'inscrire

GPU parallel B&B for the Blocking job shop scheduling problem.

Thumbnail
Voir/Ouvrir
RR.pdf (280.8Ko)
Auteur(s) :
Dabah, Adel
Bendjoudi, Ahcène
Ait Zai, Abdelhakim
El Baz, Didier
Date :
2016-02-22
URI :
http://dl.cerist.dz/handle/CERIST/797
Résumé
Branch and bound algorithms (B&B) are well known techniques 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), which is a version of classical job shop scheduling 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, for 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.

Mots clés:

Job shop; blocking with swap; GPGPU; parallel computing; Branch-and- Bound.

Source:

Rapports de recherche internes
ISRN :CERIST-DTISI/RR-16-00000006--DZ

Éditeur / Etablissement:

CERIST

Lieu:

Alger
Collections
  • Rapports de Recherche Internes [234]

Tous les documents dans CERIST DIGITAL LIBRARY sont protégés par copyright, avec tous droits réservés. copyright © 2013-2015  CERIST
Contactez-nous | Faire parvenir un commentaire
Powered by 
@mire NV
 

 


Tous les documents dans CERIST DIGITAL LIBRARY sont protégés par copyright, avec tous droits réservés. copyright © 2013-2015  CERIST
Contactez-nous | Faire parvenir un commentaire
Powered by 
@mire NV