Authors: Davidović, Tatjana 
Crainic, Teodor Gabriel
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Parallel Local Search to schedule communicating tasks on identical processors
Journal: Parallel Computing
Volume: 48
First page: 1
Last page: 14
Issue Date: 1-Oct-2015
Rank: M21
ISSN: 0167-8191
DOI: 10.1016/j.parco.2015.04.002
This paper reports on the analysis of parallelization strategies for Local Search (LS) when the neighborhood size varies throughout the search. The Multiprocessor Scheduling Problem with Communication Delays (MSPCD) is used as benchmark for illustrating the methodology and results. The dynamic load distribution strategy implemented within a supervisor-worker framework is shown to offer the best performance. Experimental results on several sets of instances with up to 500 tasks show excellent speedups (super-linear in most cases) while preserving the quality of the final solution. The proposed parallel LS is incorporated into Multistart Local Search and Variable Neighborhood Search meta-heuristic frameworks to analyze its efficiency in a more complex environment. The comparison between the sequential and parallel versions of each meta-heuristic, using various numbers of processors, shows improvement in the solution quality within proportionally smaller CPU time.
Keywords: Directed acyclic graph | Distributed memory multiprocessors | Load balancing | Meta-heuristics | Neighborhood decomposition
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 24, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




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