PARALLEL SIMULATED ANNEALING ALGORITHMS

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.