# A Recursive Optimization Approach for Buffer Allocation in Large Production Lines
## 2 Literature Review
Metaheuristics are high-level problem-independent algorithmic frameworks that provide a set of guidelines to develop heuristic optimization algorithms. Metaheuristics algorithms applied to BAPs include simulated annealing [27], genetic algorithms [28], tabu search [29], ant colony optimization [30], artificial immune [31], and big bang-big crunch [32], among others. Some researchers proposed hybrid algorithms that combine multiple metaheuristics algorithms [33], or combine metaheuristics with other search algorithms [34]. The main disadvantage of metaheuristics is that they do not make use of problem-specific properties [2,3]. Dynamic programming methods [35; 36; 37] decompose the BAP into sub-problems, which are solved recursively along the forward or backward path of a production line. The existing dynamic programming methods have to be used in conjunction with specific performance evaluation methods. As a result, their applications are limited. Search methods are based on mathematical principles or heuristic rules to find optimal or near-optimal buffer allocations. Unlike metaheuristics, search methods typically exploit some specific properties of BAPs. For example, several gradient search algorithms assume the production rate function is continuous, monotonic, and concave [7,8; 38]. It can be expected that the gradient algorithms that exploit these properties are more efficient than the metaheuristics algorithms that do not. However, gradient algorithms may lead to non-integer solutions, and thus, some rounding techniques have to be employed. Other search methods include [PERSON]'s method [39], the Hooke and Jeeves method [40], rule-based local search algorithms [41], and heuristic algorithms [42; 43]. Artificial intelligence is one of the digital technologies emerging from Industry 4.0 [44] and shows great potential in manufacturing system optimization [45]. [PERSON] and [PERSON] [46] obtain training datasets of buffer allocations for neural networks by a genetic algorithm. [PERSON] et al. [47] propose an artificial neural network-based decision support system for solving the buffer allocation problem in reliable production lines. Recently, several researchers have proposed decomposition-based search methods for solving BAPs in large production lines. [PERSON] and [PERSON] [48] developed a segmentation approach for BAPs, which divides a production line into several overlapping sub-lines. These sub-lines are optimized separately under the constraint of the original line. The optimal solutions of the sub-lines are combined to obtain a near optimal solution of the original line. [PERSON] et al. [49] proposed employing three-machine, two-buffer systems as building blocks for optimizing long production lines. The original BAP is solved by decomposing a long line into a group of overlapping three-machine, two-buffer systems and solving the simple BAPs in the decomposed subsystems. [PERSON] et al. [25] divided a large production line into multiple disconnected subsystems using conditional variables. The subsystems are optimized independently under additional conditions, and their solutions are integrated to achieve a near-optimal solution for the original line. This paper proposes two novel decomposition-based search algorithms for BAPs. Unlike the existing methods, we decompose a production line into sub-lines in a recursive manner, and the original BAP is solved by recursively solving the BAPs in the sub-lines. Numerical experiments show the recursive algorithms are very efficient for optimizing long production lines.