Parallel dynamic interaction--an inherently parallel problem-solving methodology
Ira Pramanick · 1992
This thesis details a novel inherently parallel heuristic solution framework known as Parallel Dynamic Interaction (PDI) that is applicable to certain types of exponentially hard problems. The complexity of many NP-hard problems, particularly of super-exponential problems such as flow-shop and job-shop scheduling, is so overwhelming that exhaustive search of the solution space is not possible even using massively parallel search techniques. Due to the practical significance of such problems, there has been considerable interest in the development of heuristic solution methods, which can find acceptably good solutions in a reasonable amount of time. PDI is such a methodology. PDI is inherently based upon the dynamic interplay between simultaneously executing subproblems. As such, PDI has no straightforward serial analog, and is not directly amenable to conventional parallel processing speedup analysis. This provides an indication that parallel processing can offer opportunities beyond simply speeding up the solution of sequentially specified algorithms. From a practical problem-solving perspective, PDI shows promise as a method capable of generating high quality solutions to exponentially and super-exponentially hard problems. For large problems, PDI is typically able to find a near-optimal solution many orders of magnitude faster than the time taken for a conventional parallel branch-and-bound search to find a solution of comparable quality. In addition to presenting PDI as a general solution methodology, the thesis describes its application to three real problem domains: the flow-shop scheduling problem, the job-shop scheduling problem and the vertex cover problem. These examples demonstrate how the general PDI framework can be applied to specific problems. The results of empirical studies of 90 example instances of these problems are reported. The inherently parallel nature of PDI is also specifically studied in the thesis. An empirical study is presented that supports the claim that PDI is an inherently parallel technique. Preliminary investigation of the suitability of PDI implementation on a distributed-memory system indicate that distributed PDI may represent a viable approach for solving very large problems where the parallel processing requirements become too high for shared-memory systems.