A multi-disjunctive-graph model-based memetic algorithm for the distributed job shop scheduling problem

With the influence of the digital economy, the traditional manufacturing model is undergoing a shift towards a distributed manufacturing model. This transition involves multiple workshops across diverse geographic regions. The core of distributed manufacturing is the concept of decentralized management and execution, which includes various stages, resources, and tasks within the production process. A key technology in this domain is the distributed shop scheduling problem. Notably, the distributed job shop scheduling problem (DJSSP), considering job shops, is widespread in real distributed manufacturing processes and is difficult to solve as an NP-hard problem. Although several heuristic solvers and metaheuristic algorithms have attempted to address this problem, currently two sub-problems included in the problem, factory allocation and sequence of operations, are treated separately and the description of the problem is incomplete. This paper introduces a multi-disjunctive-graph model-based memetic algorithm (MDGMBMA) developed for DJSSP to minimize the makespan. The multi-disjunctive-graph model is proposed to fully represent the DJSSP solution space. Additionally, an innovative encoding method is proposed to achieve an adequate search of the solution space, and two decoding strategies are proposed to address the search and evaluation demands of the algorithm. Furthermore, based on the property of critical job exchange between factories, a specialized critical job exchange-based neighborhood structure is designed to enhance the efficiency of the tabu search. To evaluate the performance of the MDGMBMA, numerical results from 240 large instances (ranging from 2 to 4 factories) derived from well-known JSSP benchmarks are compared against recently published discrete metaheuristic algorithms. The experimental results indicate that the proposed algorithm performs effectively in solving DJSSP.