More Web Proxy on the site http://driver.im/

research-article

Parallel Simulated Annealing Algorithms

Authors:

T.H. Sreenivas,

K.Ganapathy SubramaniamAuthors Info & Claims

Journal of Parallel and Distributed Computing, Volume 37, Issue 2

Pages 207 - 212

https://doi.org/10.1006/jpdc.1996.0121

Published: 15 September 1996 Publication History

Abstract

Simulated annealing (SA) has been considered a good tool for complex nonlinear optimization problems. The technique has been widely applied to a variety of problems. However, a major disadvantage of the technique is that it is extremely slow and hence not suitable for complex optimization problems such as scheduling. There are many attempts to develop parallel versions of the algorithm. Many of these algorithms are problem dependent in nature. We present, in this paper, two general algorithms for SA. The algorithms have been applied to job shop scheduling problem (JSS) and the traveling salesman problem (TSP) and it has been observed that it is possible to achieve superlinear speedups using the algorithm.

References

[1]

Greening, Daniel R., Parallel simulated annealing techniques, Physica D 42 (1990), 293-306.

Digital Library

[2]

Van Laarhoven, P. J. M., Aarts, E. H. L., and Lenstra, Jan Karel. Job shop scheduling by simulated annealing. In Operation Research, Vol. 40. 1992, pp. 113-125.

Digital Library

[3]

Janaki Ram, D., and Ganeshan, K. DiPS: A system for implementing and analyzing distributed algorithms. Tech. Rep. IITM-CSE-93-001, Indian Institute of Technology, Madras.

[4]

French, Simon. Sequencing and Scheduling: An Introduction to the Mathematics of Job Shop. Wiley, New York.

[5]

Eglese, R. W. Simulated annealing: A tool for operation research. In Eur. J. Oper. Res. 46 (1990), 271-281.

[6]

Allwright, James R. A., and Carpenter, D. B., A distributed implementation of simulated annealing for the traveling salesman problem. In Parallel Comput. 10 (1989), 335-338.

[7]

Decker, Keith S., Distributed problem solving techniques: A survey. In IEEE Trans. Systems Man Cybernet. 17 (1987), 729-739.

Digital Library

[8]

Adams, J., Balas, E., and Zawack, D. The shifting bottleneck procedure for job shop scheduling. Mgmt. Sci. 34 (1988), 391-401.

Digital Library

[9]

Abramson, David. A very high speed architecture for simulated annealing. IEEE Comput. (May 1992), 27-36.

[10]

Ganeshan, K. Designing and implementing flexible distributed problem solving systems. M.S. Thesis, Department of Computer Science and Engineering, Indian Institute of Technology, Madras, 1993.

[11]

Syswerda, Gilbert. Schedule optimization using genetic algorithms. In Davis, L. (Ed.). Handbook of Genetic Algorithms. pp. 332-349.

[12]

Krishan, K. Ganeshan, and Ram, D. Janaki. Distributed simulated annealing algorithms for job shop scheduling. IEEE Trans. Systems Man Cybernet. 25, 7 (July 1995), 1102-1109.

[13]

Gu and Huang, X. Efficient local search with search space smoothing. IEEE Trans. Systems Man Cybernet. 24, 5 (May 1994), 728-735.

[14]

Whitley, Darrel, Starkweather, Timothy, and Shaner, Daniel. Schedule optimization using genetic algorithms. In Davis, Lawrence (Ed.). pp. 351-357.

[15]

Nowicki, E., and Smutnicki, C. A fast tabu search algorithm for the job shop problem. Report 8/93, Institute of Engineering Cybernetics, Technical University of Wroclaw, 1993. To appear in ORSA J Comput.

Cited By

Almeida ALima JCarvalho M(2022)Systematic Literature Review on Parallel Trajectory-based MetaheuristicsACM Computing Surveys10.1145/355048455:8(1-34)Online publication date: 23-Dec-2022
https://dl.acm.org/doi/10.1145/3550484
Franceschi PMutti SPedrocchi N(2022)Optimal design of robotic work-cell through hierarchical manipulability maximizationRobotics and Computer-Integrated Manufacturing10.1016/j.rcim.2022.10240178:COnline publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1016/j.rcim.2022.102401
Vousden MBragg GBrown A(2022)Asynchronous simulated annealing on the placement problemJournal of Parallel and Distributed Computing10.1016/j.jpdc.2022.07.001169:C(242-251)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1016/j.jpdc.2022.07.001
Show More Cited By

Recommendations

A Simulated Annealing Approach to Bicriteria Scheduling Problems on a Single Machine

In this paper, we apply a simulated annealing approach to two bicriteria scheduling problems on a single machine. The first problem is the strongly NP-hard problem of minimizing total flowtime and maximum earliness. The second one is the NP-hard problem ...
Application of particle swarm optimization and simulated annealing algorithms in flow shop scheduling problem under linear deterioration

This paper studies a permutation flow shop scheduling problem with deteriorating jobs. Deteriorating jobs are the jobs which the processing time depends on the waiting time before process starts. A particle swarm optimization algorithm with and without ...
Simulated annealing and genetic algorithm for unrelated parallel machine scheduling considering set-up times

This paper presents the comparative use of Simulated Annealing (SA) and Genetic Algorithm (GA) in a scheduling problem of unrelated parallel machines with set-up times. The problem accounts for allotting batched work parts to the unrelated parallel ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Parallel and Distributed Computing

Journal of Parallel and Distributed Computing Volume 37, Issue 2

Sept. 15, 1996

99 pages

ISSN:0743-7315

Editors:
Allan Gottlieb
NEC Research Institute, Princeton, NJ
,
Kai Hwang
Univ. of Hong Kong, Hong Kong
,
Sartaj Sahni
Univ. of Florida, Gainesville

Issue’s Table of Contents

Copyright © Academic Press.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 15 September 1996

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Almeida ALima JCarvalho M(2022)Systematic Literature Review on Parallel Trajectory-based MetaheuristicsACM Computing Surveys10.1145/355048455:8(1-34)Online publication date: 23-Dec-2022
https://dl.acm.org/doi/10.1145/3550484
Franceschi PMutti SPedrocchi N(2022)Optimal design of robotic work-cell through hierarchical manipulability maximizationRobotics and Computer-Integrated Manufacturing10.1016/j.rcim.2022.10240178:COnline publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1016/j.rcim.2022.102401
Vousden MBragg GBrown A(2022)Asynchronous simulated annealing on the placement problemJournal of Parallel and Distributed Computing10.1016/j.jpdc.2022.07.001169:C(242-251)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1016/j.jpdc.2022.07.001
Bravo FBarrio AAyala JDurak U(2019)A study on the parallelization of moeas to predict the patient's response to the onabotulinumtoxina treatmentProceedings of the 2019 Summer Simulation Conference10.5555/3374138.3374162(1-12)Online publication date: 22-Jul-2019
https://dl.acm.org/doi/10.5555/3374138.3374162
Ion ALindlbauer DHerholz PAlexa MBaudisch PBrewster SFitzpatrick GCox AKostakos V(2019)Understanding Metamaterial MechanismsProceedings of the 2019 CHI Conference on Human Factors in Computing Systems10.1145/3290605.3300877(1-14)Online publication date: 2-May-2019
https://dl.acm.org/doi/10.1145/3290605.3300877
Ye ZXiao KGe YDeng Y(2019)Applying Simulated Annealing and Parallel Computing to the Mobile Sequential RecommendationIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2018.282704731:2(243-256)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1109/TKDE.2018.2827047
Jung JJayakrishnan RPark J(2016)Dynamic Shared-Taxi Dispatch Algorithm with Hybrid-Simulated AnnealingComputer-Aided Civil and Infrastructure Engineering10.5555/2926400.292640431:4(275-291)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.5555/2926400.2926404
(2016)Parallel simulated annealing using an adaptive resampling intervalParallel Computing10.1016/j.parco.2016.02.00153:C(23-31)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1016/j.parco.2016.02.001
Jha SMenon V(2014)BbmTTPProceedings of the High Performance Computing Symposium10.5555/2663510.2663513(1-7)Online publication date: 13-Apr-2014
https://dl.acm.org/doi/10.5555/2663510.2663513
Du XCheng LCheng G(2014)A heuristic search algorithm for the multiple measurement vectors problemSignal Processing10.5555/2592316.2592682100(1-8)Online publication date: 1-Jul-2014
https://dl.acm.org/doi/10.5555/2592316.2592682
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents