A global-local neighborhood search algorithm and tabu search for flexible job shop scheduling problem

PeerJ Comput Sci. 2021 May 27:7:e574. doi: 10.7717/peerj-cs.574. eCollection 2021.

Abstract

The Flexible Job Shop Scheduling Problem (FJSP) is a combinatorial problem that continues to be studied extensively due to its practical implications in manufacturing systems and emerging new variants, in order to model and optimize more complex situations that reflect the current needs of the industry better. This work presents a new metaheuristic algorithm called the global-local neighborhood search algorithm (GLNSA), in which the neighborhood concepts of a cellular automaton are used, so that a set of leading solutions called smart-cells generates and shares information that helps to optimize instances of the FJSP. The GLNSA algorithm is accompanied by a tabu search that implements a simplified version of the Nopt1 neighborhood defined in Mastrolilli & Gambardella (2000) to complement the optimization task. The experiments carried out show a satisfactory performance of the proposed algorithm, compared with other results published in recent algorithms, using four benchmark sets and 101 test problems.

Keywords: Cellular automata; Job shop scheduling; Local search; Simplified neighborhood; Tabu search.

Grants and funding

This study was supported by the National Council for Science and Technology (CONACYT) with project number CB- 2017-2018-A1-S-43008, and Nayeli J. Escamilla Serna was supported by CONACYT with grant number 1013175. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.