IVM-Based Work Stealing for Parallel Branch-and-Bound on GPU

In this paper we present a B&B algorithm entirely based on GPU and propose four work stealing (WS) strategies to balance the workload inside the GPU. Our B&B is based on an Integer-Vector-Matrix (IVM) data structure instead of a pool of permutations, and work units exchanged are intervals of factoradics instead of sets of nodes. To the best of our knowledge, the proposed approach is the pioneering to perform the entire exploration process on GPU. The four WS strategies have been experimented and compared to a multi-core IVM-based approach using standard flow shop scheduling problem instances. The reported results show, on the one hand, that the GPU-based approach is more than 5 times faster than its multi-core counterpart. On the other hand, the best of the four strategies provides a near-optimal load balance while consuming only 2% of the total execution time of the algorithm.