Large Scale Network-Centric Distributed Systems

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

3.2 Flow-Shop Scheduling Problem

3.3 Parallel Branch-and-Bound Algorithms

3.3.1 Multiparametric Parallel Model

3.3.2 Parallel Tree Exploration Model

3.3.3 Parallel Evaluation of Bounds

3.3.4 Parallel Evaluation of a Bound Model

3.4 A Multithreaded Branch-and-Bound

3.4.1 Low-Level Multithreaded B&B

3.4.2 High-Level Multithreaded B&B

3.5 The Proposed Multithreaded B&B

3.6 Experiments and Results

3.6.1 Flow-Shop Instances

3.6.2 Hardware and Software Testbed

3.6.3 Experimental Protocol

3.6.4 Performance Analysis

3.6.5 Page Faults

3.6.6 Context Switches

3.7 Conclusion

References

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