Authors: Davidović, Tatjana 
Crainic, Teodor Gabriel
Title: MPI Parallelization of Variable Neighborhood Search
Journal: Electronic Notes in Discrete Mathematics
Volume: 39
First page: 241
Last page: 248
Issue Date: 1-Dec-2012
ISSN: 1571-0653
DOI: 10.1016/j.endm.2012.10.032
We analyze five parallelization strategies for the Variable Neighborhood Search (VNS) meta-heuristic. They are based on the asynchronous cooperative execution of several threads on different processors. Some of them are adapted from the recent literature, while the others are the newly proposed. We test parallelization on various levels, and we compare centralized and non-centralized information exchange. The implemented parallel searches are applied to benchmark problem instances for Multiprocessor Scheduling Problem with Communication Delays (MSPCD). We achieve not only the improvement of the solution quality but also the reduction in the execution time. The generality of proposed strategies and straightforward implementation make them easy for the application to various difficult combinatorial optimization problems.
Keywords: Asynchronous Cooperation | Information Exchange | Multiprocessor Scheduling
Publisher: Elsevier
Project: Graph theory and mathematical programming with applications in chemistry and computer science 
Mathematical Modelas and Optimization Methods on Large-Scale Systems 

Show full item record


checked on May 23, 2024

Page view(s)

checked on May 10, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.