Vol de tâches basé sur IVM pour Branch-and-Bound parallèle sur GPU

International audienceThe irregularity of Branch-and-Bound (B&B) algorithms makes their design and implementation on the GPU challenging. In this paper we present a B&B algorithm entirely based on GPU and propose four work stealing 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 work stealing 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-accelerated 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