A Parallel Solution for the Multiprocessor Document Allocation Problem

We present a new coarse grain parallel genetic algorithm (PGA}for the Multiprocessor Document Allocation Problem (MDAP, an NP-complete problem). The problem is to find an optimal mapping of a collection of documents onto the multiprocessor nodes such that the average cluster diameter is kept to a minimum while providing for an even document distribution across the nodes. Our algorithm has been implemented on a 16-node Intel iPSC/2 hypercube and the performance was evaluated. As part of the experimental analysis, the effects of varying the number of documents and their distribution across the clusters are studied. We also investigate the impact of varying two PGA parameters - the migration period and the migration volume