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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

23 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)330-346
Journal / PublicationEuropean Journal of Operational Research
Volume83
Issue number2
Publication statusPublished - 8 Jun 1995

Abstract

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. © 1995.

Research Area(s)

  • Adaptive search, Jobs with arbitrary time lags, Scheduling, Simulated annealing, Threshold accepting

Citation Format(s)

A comparative study of both standard and adaptive versions of threshold accepting and simulated annealing algorithms in three scheduling problems. / C.K.Y. Lin, Ka Yuk Carrie; Haley, K. B.; Sparks, C.

In: European Journal of Operational Research, Vol. 83, No. 2, 08.06.1995, p. 330-346.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review