Parallel Local Search to schedule communicating tasks on identical processors

• We parallelized Local Search (LS) in variable sized neighborhoods.
• The best performing strategy is dynamic fine-grained neighborhood partition.
• We implemented it on distributed memory master–slave multiprocessor system.
• We test it on Multiprocessor Scheduling Problem with Communication Delays (MSPCD).
• We illustrate benefits for the neighborhood based meta-heuristics (MLS and VNS).

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.