Sevkli, Mehmet; Aydin, M. Emin Parallel variable neighbourhood search algorithms for job shop scheduling problems. (English) Zbl 1177.90182 IMA J. Manag. Math. 18, No. 2, 117-133 (2007). Summary: Variable neighbourhood search (VNS) is one of the most recent metaheuristics used for solving combinatorial optimization problems in which a systematic change of neighbourhood with a local search is carried out. However, as happens with other metaheuristics, it takes a long time to reach some useful solutions while solving some sort of hard combinatorial problems such as job shop scheduling (JSS). Parallelization is one of the most considerable policies to overcome this matter. In this paper, firstly, a number of VNS algorithms are examined for JSS problems and then four different parallelization policies are taken into account to determine efficient parallelization for VNS algorithms. The experimentation reveals the performance of various VNS algorithms and the efficiency of policies to follow in parallelization. In the end, the unilateral-ring topology, a noncentral parallelization method, is found as the most efficient policy. Cited in 8 Documents MSC: 90B35 Deterministic scheduling theory in operations research 68W10 Parallel algorithms in computer science 90C59 Approximation methods and heuristics in mathematical programming Keywords:variable neighbourhood search; parallel neighbourhood search; job shop scheduling PDFBibTeX XMLCite \textit{M. Sevkli} and \textit{M. E. Aydin}, IMA J. Manag. Math. 18, No. 2, 117--133 (2007; Zbl 1177.90182) Full Text: DOI