Multi-operator communication based differential evolution with sequential Tabu Search approach for job shop scheduling problems

This paper develops a multi-operator based differential evolution with a communication strategy (MCDE) being integrated with a sequential Tabu Search (MCDE/TS) to solve the job shop scheduling problem (JSSP) with the objective of minimizing makespan. The three variants of DE which are implemented in the proposed algorithm evolve as independent sub-populations, which relate to a communication strategy that maintains the diversity and quality of each sub-population by employing a proposed mixed selection strategy to avoid premature convergence. The best solution order obtained from MCDE is then passed to Tabu Search (TS) and the evolution process is continued, creating neighbour solutions with N7 neighbourhood structure. This algorithm ensures the population diversity with curving the premature convergence but experiences faster convergence. The design of experiment for parameter tuning is employed for the best combination of the proposed algorithm's parameter. The performance of the proposed MCDE/TS algorithm is evaluated against a number of state-of-the-art algorithms to show its competence in solving 122 standard benchmark instances. (C) 2021 Elsevier B.V. All rights reserved.

Automated summary

This study develops an algorithm that combines multi-operator based differential evolution and communication strategy for solving the job shop scheduling problem, and further optimizes the best solution order with sequential Tabu Search to maintain population diversity, avoid premature convergence, and improve convergence speed.