An inherently parallel method for heuristic problem-solving. II. Example applications

For pt.I. see ibid., p.1006-15. This paper presents the application of parallel dynamic interaction (PDI) to three real problem domains: the flowshop scheduling problem, the job-shop scheduling problem and the vertex cover problem. Specific examples are provided as to how the general PDI framework, introduced in part I of this paper, can be applied to a particular problem. The results of an empirical study of 90 example instances of these problems indicate that PDI consistently out-performs previously published heuristics for the vertex cover problem, and can typically generate solutions within a few percent of optimal for flow-shop and job-shop problems. Out of the 76 examples for which the optimal solution could be determined, PDI was able to produce results averaging within 4% of optimal. In over 30% of the cases, PDI was able to find the optimal solution. In no case did the PDI solution deviate more than 15% from optimal. It is also seen that the time taken by PDI to arrive at these solutions is negligible compared to that taken by conventional search techniques. This provides strong empirical evidence that PDI is capable of generating high quality solutions to exponentially and super-exponentially hard problems in reasonably short periods of time