An inherently parallel method for heuristic problem-solving. I. General framework

The class of NP-hard problems contains many problems of considerable practical importance. The complexity of these problems is so overwhelming that exhaustive search of the solution space is not possible even using massively parallel search techniques, particularly for problems of super-exponential complexity such as flow-shop and job-shop scheduling. This two-part paper discusses a novel, inherently parallel heuristic solution technique. Part I presents this technique, known as parallel dynamic interaction (PDI), as a general solution framework that is applicable to a number of computationally intractable problems, and gives details of its general methodology. From a parallel processing standpoint, PDI is interesting because it is inherently based upon the dynamic interplay between simultaneously executing subproblems. As such, PDI has no direct serial analog, and is not directly amenable to conventional parallel processing speedup analysis. This may provide 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 often 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