A comparative study of both standard and adaptive versions of threshold accepting and simulated annealing algorithms in three scheduling problems

摘要

Local search techniques are reported to be effective for many optimization problems with arbitrary objective functions and constraints. This paper compares simulated annealing with a less frequently mentioned approach, threshold accepting. Three scheduling problems of jobs with arbitrary time lags in a single-server system are considered. The optimization criteria used are maximum completion time and mean completion time. Two adaptive versions of both techniques: the adaptive neighbourhood search and the adaptive temperature/threshold values are proposed which guide the future search according to the recent search performance. These adaptive concepts prove to be effective and may be applied into other local search techniques. Computational results show that threshold accepting algorithms achieve better or comparable performance with simulated annealing in the standard and adaptive versions. Incorporating descent approaches into threshold accepting may lead to substantial improvement.