On the Parallelization of a Branch&Bound Algorithm to Solve the Resource-Constrained Project Scheduling Problem

Previous results solving the resource-constrained project scheduling problem through the parallelization of branch and bound algorithms have shown that efforts should be oriented to minimise overlapping during the search process. We try to find a compromise between communication costs and overlapping, introducing a new parallel algorithm running on a PVM (Parallel Virtual Machine) cluster of personal computers, where processors share upper bounds and cutsets information. Finally, we discuss some aspects that must be considered in theparallelization of this kind of algorithms