Parallelization of a Branch and Bound Algorithm on Multicore Systems
Parallelization of a Branch and Bound Algorithm on Multicore Systems作者机构：Department of Operations and Supply Chain Management Cleveland State University Cleveland USA Departmentof Computer and Information Science Cleveland State University Cleveland USA.
出 版 物：《Journal of Software Engineering and Applications》 (软件工程与应用（英文）)
年 卷 期：2012年第5卷第8期
页 面：621-629页
学科分类：081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）]
主 题：Parallel Branch and Bound Multithreaded Programming Multicore System Permutation Flowshop Software Reuse
摘 要：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 optimal solutions has been branch-and-bound algorithms. In this paper, we present an improved sequential algorithm which is based on a strict alternation of Generation and Exploration execution modes as well as Depth-First/Best-First hybrid strategies. The experimental results show that the proposed scheme exhibits improved performance compared with the algorithm in [1]. More importantly, our method can be easily extended and implemented with lightweight threads to speed up the execution times. Good speedups can be obtained on shared-memory multicore systems.
维普期刊数据库