Theoretical and practical issues of parallel simulated annealing

Agnieszka Debudaj-Grabysz; Zbigniew J. Czech

doi:10.1007/978-3-540-68111-3_21

Theoretical and practical issues of parallel simulated annealing

Agnieszka Debudaj-Grabysz
, Zbigniew J. Czech

Department of Algorithmics and Software (RAU/RAU5)

Silesian University of Technology
University of Silesia in Katowice

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Citations (Scopus)

Abstract

Several parallel simulated annealing algorithms with different co-operation schemes are considered. The theoretical analysis of speedups of the algorithms is presented. The outcome of the theoretical analysis was verified by practical experiments whose aim was to investigate the influence of the co-operation of parallel simulated annealing processes on the quality of results. The experiments were performed assuming a constant cost of parallel computations, i.e., searching for solutions was conducted with a given number of processors for a specified period of time. For the experiments a suite of benchmarking tests for the vehicle routing problem with time windows was used.

Original language	English
Title of host publication	Parallel Processing and Applied Mathematics - 7th International Conference, PPAM 2007, Revised Selected Papers
Pages	189-198
Number of pages	10
DOIs	https://doi.org/10.1007/978-3-540-68111-3_21
Publication status	Published - 2008
Event	7th International Conference on Parallel Processing and Applied Mathematics, PPAM 2007 - Gdansk, Poland Duration: 9 Sept 2007 → 12 Sept 2007

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4967 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	7th International Conference on Parallel Processing and Applied Mathematics, PPAM 2007
Country/Territory	Poland
City	Gdansk
Period	9/09/07 → 12/09/07

Keywords

Co-operation of processes
Parallel processing
Simulated annealing
Vehicle routing problem with time windows

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-68111-3_21

Cite this

Debudaj-Grabysz, A., & Czech, Z. J. (2008). Theoretical and practical issues of parallel simulated annealing. In Parallel Processing and Applied Mathematics - 7th International Conference, PPAM 2007, Revised Selected Papers (pp. 189-198). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4967 LNCS). https://doi.org/10.1007/978-3-540-68111-3_21

Debudaj-Grabysz, Agnieszka ; Czech, Zbigniew J. / Theoretical and practical issues of parallel simulated annealing. Parallel Processing and Applied Mathematics - 7th International Conference, PPAM 2007, Revised Selected Papers. 2008. pp. 189-198 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b5407174ad0d4d9d8af830d29cd0e604,

title = "Theoretical and practical issues of parallel simulated annealing",

abstract = "Several parallel simulated annealing algorithms with different co-operation schemes are considered. The theoretical analysis of speedups of the algorithms is presented. The outcome of the theoretical analysis was verified by practical experiments whose aim was to investigate the influence of the co-operation of parallel simulated annealing processes on the quality of results. The experiments were performed assuming a constant cost of parallel computations, i.e., searching for solutions was conducted with a given number of processors for a specified period of time. For the experiments a suite of benchmarking tests for the vehicle routing problem with time windows was used.",

keywords = "Co-operation of processes, Parallel processing, Simulated annealing, Vehicle routing problem with time windows",

author = "Agnieszka Debudaj-Grabysz and Czech, \{Zbigniew J.\}",

year = "2008",

doi = "10.1007/978-3-540-68111-3\_21",

language = "English",

isbn = "3540681051",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "189--198",

booktitle = "Parallel Processing and Applied Mathematics - 7th International Conference, PPAM 2007, Revised Selected Papers",

note = "7th International Conference on Parallel Processing and Applied Mathematics, PPAM 2007 ; Conference date: 09-09-2007 Through 12-09-2007",

}

Debudaj-Grabysz, A & Czech, ZJ 2008, Theoretical and practical issues of parallel simulated annealing. in Parallel Processing and Applied Mathematics - 7th International Conference, PPAM 2007, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4967 LNCS, pp. 189-198, 7th International Conference on Parallel Processing and Applied Mathematics, PPAM 2007, Gdansk, Poland, 9/09/07. https://doi.org/10.1007/978-3-540-68111-3_21

Theoretical and practical issues of parallel simulated annealing. / Debudaj-Grabysz, Agnieszka; Czech, Zbigniew J.
Parallel Processing and Applied Mathematics - 7th International Conference, PPAM 2007, Revised Selected Papers. 2008. p. 189-198 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4967 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Theoretical and practical issues of parallel simulated annealing

AU - Debudaj-Grabysz, Agnieszka

AU - Czech, Zbigniew J.

PY - 2008

Y1 - 2008

N2 - Several parallel simulated annealing algorithms with different co-operation schemes are considered. The theoretical analysis of speedups of the algorithms is presented. The outcome of the theoretical analysis was verified by practical experiments whose aim was to investigate the influence of the co-operation of parallel simulated annealing processes on the quality of results. The experiments were performed assuming a constant cost of parallel computations, i.e., searching for solutions was conducted with a given number of processors for a specified period of time. For the experiments a suite of benchmarking tests for the vehicle routing problem with time windows was used.

AB - Several parallel simulated annealing algorithms with different co-operation schemes are considered. The theoretical analysis of speedups of the algorithms is presented. The outcome of the theoretical analysis was verified by practical experiments whose aim was to investigate the influence of the co-operation of parallel simulated annealing processes on the quality of results. The experiments were performed assuming a constant cost of parallel computations, i.e., searching for solutions was conducted with a given number of processors for a specified period of time. For the experiments a suite of benchmarking tests for the vehicle routing problem with time windows was used.

KW - Co-operation of processes

KW - Parallel processing

KW - Simulated annealing

KW - Vehicle routing problem with time windows

UR - https://www.scopus.com/pages/publications/45749091761

U2 - 10.1007/978-3-540-68111-3_21

DO - 10.1007/978-3-540-68111-3_21

M3 - Conference contribution

AN - SCOPUS:45749091761

SN - 3540681051

SN - 9783540681052

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 189

EP - 198

BT - Parallel Processing and Applied Mathematics - 7th International Conference, PPAM 2007, Revised Selected Papers

T2 - 7th International Conference on Parallel Processing and Applied Mathematics, PPAM 2007

Y2 - 9 September 2007 through 12 September 2007

ER -

Debudaj-Grabysz A, Czech ZJ. Theoretical and practical issues of parallel simulated annealing. In Parallel Processing and Applied Mathematics - 7th International Conference, PPAM 2007, Revised Selected Papers. 2008. p. 189-198. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-68111-3_21

Theoretical and practical issues of parallel simulated annealing

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this