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||Abstract:||
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 Nov 27, 2022
checked on Nov 28, 2022
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.