GPU-based two level parallel B&B for the Blocking job shop scheduling problem.
Loading...
Date
2016-05-23
Journal Title
Journal ISSN
Volume Title
Publisher
IEEE
Abstract
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.
Description
Keywords
Job shop; blocking with swap; GPGPU; parallel computing; Branch-and- Bound.