Load Balancing in Hypercube Solution of Stochastic Optimization Problems

In some stochastic optimization problems the error bounds computed for the expected optimum can be decreased through recursive divide-and-conquer methods based on partitioning the support of the random variables. Each generated partition from the divide-and-conquer process can be treated independently. This class of problems is therefore easy to parallelize, and we describe two parallel implementations of this divide-and-conquer algorithm applied to PERT. Our results indicate that parallel processing and divide-and-conquer are indeed feasible and efficient for problems of this type. The tests were done on an Intel iPSC/2 multicomputer with 16 nodes.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.