Task assignment by parallel simulated annealing
E.E. Witte, Roger D. Chamberlain, Mark A. Franklin · 2002
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.>