A parallel simulated annealing algorithm that is problem-independent, maintains the serial decision sequence, and obtains speedup which can exceed log/sub 2/P on P processors is discussed. The algorithm achieves parallelism by using the concurrency technique of speculative computation. Implementation of the parallel algorithm on a hypercube multiprocessor and application to a task assignment problem are described. The simulated annealing solutions are shown to be, on average, 28% better than the solutions produced by a random task assignment algorithm and 2% better than the solutions produced by a heuristic.>

Simulated annealing for obtaining approximate solutions to combinatorial optimization problems is addressed. The serial algorithm, however, can require extensive computation time. Most parallel algorithms for simulated annealing are problem-specific and/or violate the serial decision sequence, thereby allowing errors not present in the serial algorithm. Maintaining the serial sequence is necessary to prove that the algorithm converges to a global optimum solution when allowed to reach equilibrium at each temperature. A parallel algorithm which is both problem-independent and maintains the serial decision sequence is presented. The parallel algorithm uses the concurrency techniques of speculative computation to achieve speedup which can exceed log/sub 2/P, on P processors. For three problems investigated, the average speedup on eight processors was 2.6.>

The authors present a method for parallelizing the simulated annealing algorithm by mapping the algorithm onto a dynamically structured tree of processors. The resulting parallel simulated annealing algorithm is discussed and its performance evaluated using simulation techniques. An important property of the parallel algorithm is that it maintains the same move decision sequence as the serial simulated annealing algorithm, thus avoiding problems associated with move conflicts and erroneous move acceptance/rejection decisions which have been associated with other parallel simulated annealing algorithm proposals. The parallel algorithm presented achieves speedups between log/sub 2/N and (N+log/sub 2/N)/2 where N is the number of processors in the parallel processor. Experimental results are presented on three versions of the basic method: the static, dynamic balanced, and dynamic unbalanced parallel-simulated-annealing algorithms.>