Integrating Memory-Based Perturbation Operators into a Tabu Search Algorithm for Real-World Production Scheduling Problems

Production scheduling problems, arising in real-world use cases, are characterized by a very large number of operations and complex constraints. In order to handle such problems, practical solution approaches need to be generic enough, to capture all relevant restrictions, while being able to calculate good solutions in a short amount of time. Metaheuristic methods, especially combinations of trajectory and population-based approaches, are promising techniques to meet this criterion. In this work, we develop a framework for deriving and integrating memory-based perturbation operators into a highly flexible Tabu Search algorithm for scheduling problems, in order to enhance its overall performance. The perturbation operators are inspired by evolutionary algorithms and collect valuable solution information during the Tabu Search procedure via an elite solution pool. This information is used in a destroy-and-repair step integrated into the Tabu Search procedure, aiming to preserve promising solution structures. We investigate several parameters and perform computational experiments on job-shop benchmark instances from literature, as well as on a real-world industry use case. Integrating the developed memory-based perturbation operators into the Tabu Search algorithm leads to significant performance improvements on the real-world problem. The benchmark evaluations demonstrate the robustness of the approach, when dealing with sensitive parameters.