A Multithreaded Branch-and-Bound Algorithm for Solving the Flow-Shop Problem on a Multicore Environment
Many real-world problems encountered in different industrial and economic fields, such as task allocation, job scheduling, network routing, cutting, and packing, are of a combinatorial nature. Such combinatorial optimization problems are known to be large in size and NP-hard to solve. One of the most popular exact methods for solving to optimality a combinatorial optimization problem, is the branch-and-bound (B&B) algorithm.
This algorithm is based on an implicit enumeration of all the feasible solutions of the problem to be tackled. The space of potential solutions, called the search space, is explored by dynamically building a tree for which the root node designates the initial problem. The internal or intermediate ...