O'Reilly logo

Large Scale Network-Centric Distributed Systems by Albert Y. Zomaya, Hamid Sarbazi-Azad

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required