Simulated annealing algorithm for solving the single machine early/tardy problem

Jrjung Lyu, A. Gunasekaran, J. H. Ding

Research output: Contribution to journalArticle

7 Citations (Scopus)


Recently, several studies have been conducted regarding the application of the simulated annealing (SA) method to solve combinatorial optimization problems. Most of the previous reports have shown that SA has been used to obtain reasonable solutions that are better than some heuristic algorithms and in comparable CPU time. A single machine early/tardy problem is selected in this paper to demonstrate the usefulness of SA. Firstly, based on previous studies, this research uses the factorial experiment to analyse the factors that are critical to the efficiency of SA. Secondly, SA, tuned by the previous step, is compared with branch-and-bound and neighbourhood search methods by solving some test problems. The results show that SA is very sensitive to the cooling schedule, generation mechanism, acceptance criteria and stopping criteria. When SA is used to solve the single machine problem with n ≤ 15, it can converge to the optimal solution quickly. For the single machine problem where n ≥ 30, the branch-and-bound algorithm is not feasible while SA can provide a much better solution than the neighbourhood search method.

Original languageEnglish
Pages (from-to)605-610
Number of pages6
JournalInternational Journal of Systems Science
Issue number7
Publication statusPublished - 1996 Jan 1

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Simulated annealing algorithm for solving the single machine early/tardy problem'. Together they form a unique fingerprint.

  • Cite this