×

Parallel variable neighbourhood search algorithms for job shop scheduling problems. (English) Zbl 1177.90182

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.

MSC:

90B35 Deterministic scheduling theory in operations research
68W10 Parallel algorithms in computer science
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI