Journal article
An inherently parallel method for heuristic problem-solving. I. General framework
IEEE transactions on parallel and distributed systems, Vol.6(10), pp.1006-1015
10/1995
DOI: 10.1109/71.473511
Abstract
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.< >
Details
- Title: Subtitle
- An inherently parallel method for heuristic problem-solving. I. General framework
- Creators
- I Pramanick - ASD, Performance Eng., Silicon Graphics, Mountain View, CA, USAJ.G Kuhl
- Resource Type
- Journal article
- Publication Details
- IEEE transactions on parallel and distributed systems, Vol.6(10), pp.1006-1015
- Publisher
- IEEE
- DOI
- 10.1109/71.473511
- ISSN
- 1045-9219
- eISSN
- 1558-2183
- Language
- English
- Date published
- 10/1995
- Academic Unit
- Electrical and Computer Engineering; Public Policy Center (Archive)
- Record Identifier
- 9984083831902771
Metrics
18 Record Views