Production planning problems in modern industrial environments are characterized by a large number of work steps and complex constraints. In order to remain competitive in the market, it is crucial for companies to create efficient and precise production plans in a short time. To overcome these challenges, innovative approaches are researched or existing solutions are further improved to achieve optimal results. Tabu search is a popular metaheuristic for solving complex optimization problems, which is also used in production planning. In this article, an extension of this algorithm is presented that enables a significant improvement in performance. The central concept of this extension is to collect valuable solution information during the search and to identify promising solution patterns. If it becomes necessary to vary the search behavior of the tabu search to explore a broader spectrum of the solution space, these identified promising solution parts are retained and integrated into the further search process.
The accurate and efficient derivation of production plans is critical in today’s manufacturing environment. The underlying production planning problems are often difficult optimization problems of different sizes. The approaches available for solving them can be roughly divided into exact methods and metaheuristics. Exact algorithms always find an optimal solution and can prove their optimality. However, the computing time can increase significantly with the size of the problem. Although they do not guarantee that an optimal solution will be found, metaheuristics offer a good compromise between solution quality and computing time as well as a high degree of flexibility when implementing the restrictions of the optimization problem.
Tabu search is a metaheuristic that was first introduced by Fred W. Glover in 1986 and formalized in 1989. Shortly afterwards, together with simulated annealing and genetic algorithms, it was considered extremely promising for practical applications [1]. Tabu search has since found numerous and widespread successful applications and continues to be used to solve difficult combinatorial optimization problems.
Tabu search starts from an initial admissible solution and uses local search methods to explore the solution space. It does this by moving from an admissible solution to an improved solution in its neighborhood. The search terminates when a termination criterion is met (e.g. a maximum number of iterations or an evaluation threshold), but in most cases with no guarantee of solution quality. Local search methods tend to get stuck in suboptimal regions or plateaus where no improved neighbors are available. To solve this problem, tabu search uses memory structures with different time spans that allow the algorithm to leave local minima and explore new regions of the search space. The simplest example of this is the tabu list, which records recently visited solutions to ensure that they are not revisited (https://en.wikipedia.org/wiki/Tabu_search).
The success of metaheuristics in obtaining high-quality solutions to difficult optimization problems depends on the development of appropriate intensification and diversification strategies and a balancing mechanism between the two.
To illustrate the two terms, let’s take the example of a vacation stay in a city with the aim of finding the best restaurant. The search is initially limited to an area of 2 km around the accommodation. The intensification means that the restaurants are only looked at in this area. After some time, you can try to explore other areas of the city that are further away from the accommodation. This would diversify the search.
Intensification and diversification are found in other areas of decision making than exploitation and exploration. The balancing act between the two is known as the exploration and exploitation dilemma.
A first attempt to diversify a tabu search algorithm is to change the size of the tabu list. For some small applications, this is all that is necessary. For more complicated applications, however, effective diversification strategies rely on longer-term memory. One possible approach is based on the rationale that by making only small changes to the solution in each iteration, you may not visit other promising areas of the solution space. Instead, they use very large shifts that can rearrange up to 30-40% of the candidate solution. These approaches are “remove-insert” operations, also known as “destroy-and-repair” operations:
In [2], an optimization framework based on tabu search was proposed for solving real-world scheduling problems with complex constraints and dynamic properties, which can be easily adapted to different scheduling problems. This highly extensible tabu search algorithm has been successfully used by RISC Software GmbH to solve production scheduling problems.
The underlying production planning problem involves the sequence of work steps and their allocation to machines. These work steps are linked by predecessor/successor relationships and must not be interrupted by other work steps. They have a number of compatible machines and machine-dependent capacity requirements, setup, processing and teardown times. In addition, they may have defined overlaps, waiting times and transportation times.
Figure 1: Nine work steps, in five orders, and two machines (top) and a possible allocation to machines (bottom)
The size of production scheduling problems solved with the tabu search framework ranges from 850 work steps to about 20,000 total work steps and from about 50 machines to 110 machines. One of the challenges in solving such large scheduling problems with a metaheuristic approach is to design a diversification strategy that allows to reach more promising areas of the solution space sufficiently fast and in an intelligent way.
The Memory-Based Perturbation Framework (MBP) is an extension of the existing tabu search optimization framework and consists of a diversification strategy with solution memory [4]. Specifically, it contains two operators with different parameters that identify parts of the solutions as promising in the first step. The other solution parts are removed in subsequent steps and added again according to a specific mechanism. The framework has proven to be effective in solving the described scheduling problem of different sizes.
Figure 2: The first three and the last step were identified as promising solution parts, the other steps are removed and added again (below is the resulting plan).
The main components of this framework are briefly described below:
The motivation for this framework was to solve real, dynamic scheduling problems with extensive restrictions, as provided by an industrial partner of RISC Software GmbH. The MBP framework was evaluated on such an instance with 905 work steps and 67 machines and proved to be effective. The two implemented operators of the MBP framework, with the best possible parameter settings, bring significant improvements to the considered target functions, see Figure 3 for such an example.
Figure 3: The progression of an objective function value for the real use case from industry for the two new operators of the Memory-Based Perturbation Framework (drawn in red and green) in comparison to two other available operators.
The promising results form the basis for further applications of the Tabu Search algorithm with the MBP framework to other real-world planning problems. With larger scope and more complex objective functions, these planning problems target other relevant production goals.
In addition to all its advantages, the digitalization of production also brings with it an increased complexity of scheduling problems and the need for intelligent solutions to overcome these challenges. Solution approaches based on metaheuristics such as tabu search are still used in this area. The design and implementation of good frameworks for intensification and diversification, and the definition of the trade-off between the two, are key components for the success of these approaches. The promising results of integrating the MBP framework into the existing tabu search algorithm show that they are suitable to tackle complex scheduling problems in production.
The MBP framework and the results were presented by M. Schlenkrich at the ICORES 2024 conference (13th International Conference on Operations Research and Enterprise Systems).
Acknowledgements. Parts of the work described in this paper have been funded by the State of Upper Austria, Austria, as part of the program ,,#upperVISION2030″ within the project ,,Secure Prescriptive Analytics”. Project number: Wi-2021-305601/18-Au.
1 F. Glover, E. Taillard, E. de Werra, A user’s guide to tabu search, Annals of Operations Research 41 (1993), 3-28.
2 F. Glover, Z. Lü, J.-K. Hao, Diversification-driven tabu search for unconstrained binary quadratic problems. J. Oper Res (2010), 8:239-253.
3 M. Bögl, A. Gattinger, I, Knospe, M. Schlenkrich, R. Stainko. Real-life scheduling with rich constraints and dynamic properties – an extendable approach. Proceedings of the 2nd International Conference on Industry 4.0 and Smart Manufacturing (ISM 2020), 180:534-544.
4 M. Schlenkrich, M. Bögl, A. Gattinger, I. Knospe, S. Parragh. Integrating Memory-Based Perturbation Operators into a Tabu Search Algorithm for Real-World Production Scheduling Problems. In Proceedings of the 13th International Conference on Operations Research and Enterprise Systems – ICORES; ISBN 978-989-758-681-1; ISSN 2184-4372, SciTePress, 213-220. DOI: 10.5220/0012271900003639
Mathematical Optimization Engineer
Mathematical Optimization Engineer
