A parallel Optimal Best-First search Branch-and-Bound (B&B) algorithm (obs) is proposed and evaluated for MIN-based multiprocessor systems. The proposed algorithm decomposes a problem into a number of subproblems and each subproblem is processed on a small group of processors. A performance analysis is conducted to estimate the speed-up of the proposed parallel B&B algorithm. It considers both the computation and communication times to evaluate the realistic performance. Simulation data are given, along with analysis results for model validation. It is shown that the proposed algorithm performs better than other reported schemes with its various advantageous features such as: less subproblem evaluations, proper load balancing, and limited scope of remote communication through the network.

We propose and evaluate a parallel "decomposite best-first" search branch-and-bound algorithm (dbs) for MIN-based multiprocessor systems. We start with a new probabilistic model to estimate the number of evaluated nodes for a serial best-first search branch-and-bound algorithm. This analysis is used in predicting the parallel algorithm speed-up. The proposed algorithm initially decomposes a problem into N subproblems, where N is the number of processors available in a multiprocessor. Afterwards, each processor executes the serial best-first search to find a local feasible solution. Local solutions are broadcasted through the network to compute the final solution. A conflict-free mapping scheme, known as the step-by-step spread, is used for subproblem distribution on the MIN. A speedup expression for the parallel algorithm is then derived using the serial best-first search node evaluation model. Our analysis considers both computation and communication overheads for providing realistic speed-up. Communication modeling is also extended for the parallel global best-first search technique. All the analytical results are validated via simulation. For large systems, when communication overhead is taken into consideration, it is observed that the parallel decomposite best-first search algorithm provides better speed-up compared to other reported schemes.>

A parallel "Decomposite Best-First" search Branch-and-Bound algorithm (pdbsbb) for MIN-based multiprocessor systems is proposed in this paper. A conflict free mapping scheme, known as step-by-step spread, is used to map the algorithm efficiently on to a MIN-based system for reducing communication overhead. It is shown that the proposed algorithm provides better speed-up than other reported schemes when communication overhead is taken into consideration.