Simulated annealing (SA) has been considered a good tool for complex n
onlinear optimization problems. The technique has been widely applied
to a variety of problems. However, a major disadvantage of the techniq
ue is that it is extremely slow and hence not suitable for complex opt
imization problems such as scheduling. There are many attempts to deve
lop parallel versions of the algorithm. Many of these algorithms are p
roblem dependent in nature. We present, in this paper, two general alg
orithms for SA. The algorithms have been applied to job shop schedulin
g problem (JSS) and the traveling salesman problem (TSP) and it has be
en observed that it is possible to achieve superlinear speedups using
the algorithm. (C) 1996 Academic Press, Inc.