A queueing network model for analyzing a class of branch-and-bound algorithms on a master-slave architecture

Partitioning methods lend themselves very well to implementation on parallel computers. In recent years, branch-and-bound algorithms have been tested on various types of architectures. In this paper, the authors develop a queueing network model for the analysis of a class of branch-and-bound algorithms on a master-slave architecture. The analysis is based on a fluid flow approximation. Numerical examples illustrate the concepts developed. Finally, related branch-and-bound algorithms are studied using a machine repair queueing model.