Abstract
Simulated annealing is inspired by the physical process of heating and cooling process to obtain a strong crystalline structure. It is a heuristic algorithm that can be used to solve discrete optimization problems. The concepts of parallel computing were applied to speed up computation. It allows us obtain solutions in a shorter time.Multiple trials is the basic concept of many parallel simulated annealing. It is to perform multiple trials at the same time to search acceptable solutions. The division simulated annealing with no communication and The clustering simulated annealing are two common types of parallel simulated annealing methods. The division simulated annealing with no communication makes each processor generate its own adjacent solution from its own current solution and compute the acceptance probability for a adjacent solution. Each of the processors searches solutions without communicating each other. Clustering simulated annealing makes each processor generate its own adjacent solution from a common current solution and compute the acceptance probability for each adjacent solution. Then, it decides which adjacent solution should be used to replace current solution according to a pre-specified rule.Dynamic parallel simulated annealing (DPSA) combined independent simulated annealing with clustering simulated annealing. At high temperature, DPSA makes each processor search in it own sequence independently; while at low temperature, DPSA merges processors into clusters that performs a common search sequence.The focus of this research is how and when we should combine processors of independent search sequences into a cluster. There are two dynamic parallel simulated annealing algorithm used in this research. Both of them have better search result than independent simulated annealing.