3

A Multithreaded Branch-and-Bound Algorithm for Solving the Flow-Shop Problem on a Multicore Environment

Mohand Mezmaz, Nouredine Melab, and Daniel Tuyttens

Contents

3.1 Introduction

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 ...

Get Large Scale Network-Centric Distributed Systems now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.