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)

Abstract

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
Volume27
Issue number7
DOIs
Publication statusPublished - 1996 Jan 1

Fingerprint

Simulated Annealing Algorithm
Single Machine
Simulated annealing
Simulated Annealing
Neighborhood Search
Search Methods
Factorial Experiment
Stopping Criterion
Combinatorial optimization
Branch and Bound Algorithm
Branch-and-bound
Heuristic algorithms
CPU Time
Combinatorial Optimization Problem
Heuristic algorithm
Test Problems
Program processors
Cooling
Schedule
Optimal Solution

All Science Journal Classification (ASJC) codes

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

Cite this

@article{48caf1ec0dbc4b34a96e2c3e7d0a9353,
title = "Simulated annealing algorithm for solving the single machine early/tardy problem",
abstract = "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.",
author = "Jrjung Lyu and A. Gunasekaran and Ding, {J. H.}",
year = "1996",
month = "1",
day = "1",
doi = "10.1080/00207729608929256",
language = "English",
volume = "27",
pages = "605--610",
journal = "International Journal of Systems Science",
issn = "0020-7721",
publisher = "Taylor and Francis Ltd.",
number = "7",

}

Simulated annealing algorithm for solving the single machine early/tardy problem. / Lyu, Jrjung; Gunasekaran, A.; Ding, J. H.

In: International Journal of Systems Science, Vol. 27, No. 7, 01.01.1996, p. 605-610.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Lyu, Jrjung

AU - Gunasekaran, A.

AU - Ding, J. H.

PY - 1996/1/1

Y1 - 1996/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0030195549&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030195549&partnerID=8YFLogxK

U2 - 10.1080/00207729608929256

DO - 10.1080/00207729608929256

M3 - Article

AN - SCOPUS:0030195549

VL - 27

SP - 605

EP - 610

JO - International Journal of Systems Science

JF - International Journal of Systems Science

SN - 0020-7721

IS - 7

ER -