Implementation of a Multithreaded Branch and Bound Algorithm for Permutation Flowshop Problems

C.-S. Chung, J. Flynn, and J. Sang (USA)


Parallel Branch and Bound, Multithreaded Programming, Multicore System, Permutation Flowshop, Flow Time


The general m-machine permutation flowshop problem with the total flow-time objective is known to be NP-hard for m ≥ 2. The only practical method for finding opti mal solutions has been branch and-bound algorithms. Considering the lengthy process in the search for an optimal schedule, we focus on using multiple threads for solving permutation flowshop problems on shared-memory multicore platforms. Our approach is based on a Master/Worker model and depth-first/best-first hybrid strategies. The experimental results show that the proposed method exhibits improved performance compared with the existing depth first parallel algorithm.

Important Links:

Go Back