SA is an intrinsically sequential
algorithm, due to its recursive structure. Some possible parallel
designs (reviewed by Arts and Korst [2]) have been developed, making
use of the idea of * multiple trial parallelism*, in which several
different trial solutions are simultaneously generated, evaluated
and tested on individual processors. Whenever one of these
processors accepts its solution, it becomes the new one from which
others are generated. Although such an approach results in N times
as many solutions being investigated per unit time (where N is the
number of processors), it is found that the total (elapsed) time
required for convergence is not proportionally reduced. This is due
to the fact that the instantaneous concurrent efficiency h, which in
this context can be defined as

where is the time taken for a
new solution to be accepted by the serial or parallel algorithm,
varies as the search progresses. It is initially only about ,
because the vast majority of the solutions generated are accepted,
and, therefore, **N-1** of the processors are redundant. As the annealing
temperature is reduced (and the solution acceptance probability
falls), increases, approaching 100% as **T** nears zero. However, the
overall incentive for parallelizing the optimization scheme is not
great, especially as in many instances the problem function
evaluation procedure can be multitasked with much greater ease and
effect.