Enhanced Parallel Cooperative Model for Trajectory Based Metaheuristics: A Scalability Analysis

This paper studies the scalability properties of a enhanced parallel cooperative model for trajectory based metaheuristics. Algorithms based on the exploration of the neighborhood of a single solution like simulated annealing (SA) have offered very accurate results for a large number of real-world problems. Although this kind of algorithms are quite efficient, more improvements are needed to tackled with the large temporal complexity of the industrial problems. One possible way to improve the performance is the utilization of parallel methods. The field of parallel models for trajectory methods has not deeply been studied (at least, in comparison with the parallel model for population based techniques). In this work, we focus on studying the scalability of a recently proposed parallel cooperative model for single solution techniques that allows to reduce the global execution time and to improve the efficacy of the method. We test this model using a larger number of instances with different size of a well-known NP-hard problem, the MAXSAT.