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.