<figure><img src="image_1.png" /></figure>

HAL
open science

# Restrict-and-Fix Heuristics for Large Robotic Assembly Line Balancing Problem. ★

Yikun Hu, Simon Thevenin, Nadjib Brahimi, Hamidreza Rezaei

► To cite this version:

Yikun Hu, Simon Thevenin, Nadjib Brahimi, Hamidreza Rezaei. Restrict-and-Fix Heuristics for Large Robotic Assembly Line Balancing Problem. ★. IFAC MIM 2025, Jun 2025, Trondheim, Norway. hal-05192973

HAL Id: hal-05192973

https://hal.science/hal-05192973v1

Submitted on 16 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Restrict-and-Fix Heuristics for Large
Robotic Assembly Line Balancing
Problem.*

Yikun HU* Simon Thevenin* Nadjib Brahimi**
Hamidreza Rezaei*

* IMT Atlantique, Nantes, 44300 France (e-mail: {yikun.hu, simon.thevenin, hamidreza.rezaei} @imt-atlantique.fr).

** Rennes School of Business, Rennes, France, (e-mail: nadjib.brahimi@rennes-sb.com)

**Abstract:**

The rapid advancements in robotics and automation have revolutionized the manufacturing industry, introducing new complexities in the design and balancing of robotic assembly lines. The Robotic Assembly Line Balancing Problem (RALBP) extends the classical assembly line balancing problem by incorporating equipment selection for each workstation. In other words, RALBP requires tasks to be grouped based on shared equipment needs. As RALBP is an NP-hard problem, efficient metaheuristics or heuristics must be developed to design realistic assembly lines because such lines can span several kilometers. This paper tackles these challenges by introducing a novel Restrict-and-Fix (RF) method, inspired by the Relax-and-Fix framework. The proposed heuristic decomposes the RALBP into smaller, manageable subproblems, solving them iteratively to find good quality solutions within reasonable computational times. Numerical results demonstrate the method's strong performance and scalability. Furthermore, as the method relies on mixed-integer linear models, it can easily be extended to account for a wide range of practical constraints.

**Keywords:** Robotic assembly line design, Restrict-and-Fix method

# 1. INTRODUCTION

The rapid evolution of robotics and automation technologies has revolutionized the manufacturing industry, particularly in the realm of flexible assembly lines. In this era of automation, the design and optimization of robotic assembly lines have emerged as pivotal research areas. A robotic assembly line consists of a series of workstations, each equipped with robotic arms that perform specific tasks on a product as it moves along a conveyor belt. This paper addresses the critical challenges in designing such lines, which is the robotic assembly line balancing problem (RALBP) with the aim of balancing the workload among workstations to minimize equipment cost, while also respecting constraints such as task precedence and equipment-task compatibility. Moreover, as the scale of production increases, the complexity of the RALBP grows exponentially, making it difficult to solve using traditional methods.

The motivation behind this research lies in the need of developing efficient algorithms that can solve large-scale instances of the RALBP. Existing methods, such as Branch-and-Bound (Rubinovitz et al. (1993), Bukchin and Tzur (2000)) and genetic algorithms (Levitin et al. (2006), Daoud et al. (2014)), have limitations in terms of scalability and computational efficiency, leading to several

challenges in providing practical solutions for real-world applications.

The interest in this field is further fueled by the ongoing advancements in robotics and automation. As technology progresses, robotic arms become more sophisticated and capable of performing a wider range of tasks. This increased flexibility, however, also introduces additional complexity in terms of task assignment and workstation configuration. Therefore, there is a growing demand for research that can help manufacturers navigate these complexities and optimize their robotic assembly lines for maximum productivity and cost-effectiveness.

In this paper, we introduce a Restrict-and-Fix (RF) method for solving the RALBP. This method is based on the Relax-and-Fix framework, which is known for its ability to handle large-scale optimization problems efficiently. By splitting the RALBP into smaller and more manageable subproblems and solving them iteratively, we aim to develop a heuristic solution that can provide high-quality results within a reasonable computational time.

In Section 3, we formulate a mathematical model aimed at minimizing equipment costs while accounting for the constraints of the RALBP. Subsequently, in Section 4, we delve into the definition of RF and elucidate how to integrate them into our specific problem. Furthermore, we conduct several experiments to illustrate the influence of various parameters on the performance of RF. Given that

<footnote>* This paper is financed by ALICIA project.</footnote>
the efficacy of RF hinges on its configuration, we present a user-defined parameter selection strategy to determine the optimal parameters and the methodology for dividing the original problem.

## 2. LITERATURE REVIEW

The RALBP was first introduced by Rubinovitz (1991), focusing on optimizing the assignment of tasks to stations by selecting the efficient equipment to minimize the number of workstations for a given cycle time. This problem is inherently complex and belongs to the class of NP-hard problems, meaning that finding an optimal solution is computationally challenging.

To address this optimization challenge, Rubinovitz et al. (1993) proposed both a heuristic and an exact Branch-and-Bound method using the Frontier Search approach to minimize the number of workstations in robotic assembly line balancing problem. In this paper, the robotic assembly line balancing problem (RALBP) is modeled by considering the precedence relationships among assembly tasks, deterministic task durations that depend on the assigned robot (including material handling, loading, and unloading times), the assignment of a single robot to each station, and the balancing of the line for a single product.

Bukchin and Tzur (2000) reformulated the robotic assembly line balancing problem with the objective of minimizing total equipment cost. They employed a branch-and-bound algorithm for solving small instances and developed a branch-and-bound-based heuristic for larger cases. This class of problems, which seeks to minimize either the number of workstations or the total cost, is categorized as RALBP-I. The model we study makes similar assumptions as RALBP-I: a predefined set of equipment types, each with specific purchasing and operational costs; precedence relations among tasks; indivisibility of tasks; compatibility constraints that allow tasks to be executed at any station equipped with compatible machinery, provided all precedence requirements are satisfied; and the assignment of a single piece of equipment to each station.

Another group of problems, known as RALBP-II, aims to minimize the cycle time. Levitin et al. (2006) developed a genetic algorithm with two assignment procedures: a recursive assignment procedure and a consecutive assignment procedure. Results of their work were further improved through the use of a work-piece exchange procedure (hill climbing). The approach can solve the problem with the size up to 297 tasks with 50 equipments. Subsequently, Daoud et al. (2014) successfully combined the ant colony algorithm with guided local search to avoid getting trapped in local optima during the meta-heuristic process.

Although meta-heuristic approaches can provide feasible solutions for large RALBP instances, they are often too time-consuming in practice. Moreover, there is a lack of simple, easy-to-implement tools to assist practitioners in designing optimal robotic assembly lines. To address this gap, we propose a generalized version of the Relax-and-Fix heuristic, namely the Restrict-and-Fix method to efficiently tackle large-scale RALBP problems.

Relax-and-fix (Pochet and Wolsey (2006)) provides a heuristic method for solving large mixed-integer programs.

The method consists of a decomposition of integer variables into some distinct subsets with a defined order. Then, the MILP is solved with only one of these subsets keeping their integrality while the other subsets are relaxed to continuous variables. After solving the MILP at an iteration, integer variables of the subset are fixed with their current values. The algorithm continues until all the integer variables are fixed, which are considered as the final solution.

The Restrict-and-Fix approach proposed by Joncour et al. (2023) is a generalized version of the Relax-and-Fix heuristic for solving mixed-integer programs. It operates by decomposing the variable space and solving a sequence of simpler subproblems. At each iteration, a subset of decision variables is optimized while the remaining variables are fixed to values obtained from previous subproblem solutions. This iterative process progressively constructs a solution to the original problem. The number of subproblems is denoted by $α$. Each subproblem retains the same constraints, objective function, and global variables as the original problem, but considers only a subset of the local decision variables. The effectiveness of this method has been demonstrated by Joncour et al. (2023) through successful applications to the capacitated multi-item lot-sizing problem, the vehicle routing problem, the bin packing problem, and the quadratic portfolio optimization problem. Given its constructive nature and demonstrated efficiency, applying this heuristic to the RALBP represents a promising direction for obtaining high-quality solutions to large-scale instances.

## 3. MATHEMATICAL MODEL

In this section, a mathematical model to formulate the RALBP is explained with the assumptions.

### 3.1 Decision variables and parameters

Consider a robotic assembly line for a specific product with a set of tasks $I$. $\pi_{ii'}$ is a binary parameter to describe the precedence relation between tasks $i$ and $i' \in I$, which means that task $i'$ should always be executed after the completion of task $i$ when $\pi_{ii'} = 1$. To perform tasks, robotic arms are required as the assembly equipment. Depending on the lifting capacity and reaching spaces, robots can be distinguished as different types $j \in J$. Some tasks can only be performed with specific equipment due to weight lifting or mobility limitations. Parameter $\kappa_{ij}$ represents the compatibility between task $i$ and equipment $j$. Workstation $k$ is a piece of working area in an assembly line that contains a specific robotic arm. Using the conveyor belt, the unfinished product is passed through all the workstations. Each task is associated with a processing time $t_i$.

Here we list all the assumptions before the construction of the model:

(1) Each workstation contains one type of robotic arm to perform a specific task.

(2) If different types of equipment are capable of performing one task, the difference of speeds between the equipment is negligible. Thus, the task processing time is independent of the type of equipment.
(3) The time of installing equipment and changing tools on a robotic arm, as well as the transportation time of the unfinished product unit between workstations, are included in the task processing time.

(4) The cost of equipment $\rho_j$ includes both the purchasing cost and installation cost of equipment j.

Two groups of decision variables are:

• $x_{ijk} = 1$ if the task i is assigned to the station k with equipment j, 0 otherwise.

• $y_{jk} = 1$ if a unit of equipment j is assigned to station k, 0 otherwise.

## 3.2 Objective function and constraints

Equations (1) to (7) represent the problem modeled as a mixed-integer linear program (MILP). The objective of the model is to minimize the cost of equipment while ensuring the production demand.

$$ \text{Min} \quad \sum_{j \in J} \sum_{k \in K} \rho_j y_{jk} \quad (1) $$

$$ \sum_{\kappa_{ij}=1}^{J} \sum_{k \in K} k \cdot x_{ijk} \leq \sum_{\kappa_{i'j}=1}^{J} \sum_{k' \in K} k' \cdot x_{i'jk'}, \quad (2) $$

$$ \forall i, i' \in I \text{ if } \pi_{ii'} = 1. $$

$$ \sum_{\kappa_{ij}=1}^{J} \sum_{k \in K} x_{ijk} = 1, \quad \forall i \in I. \quad (3) $$

$$ \sum_{i \in I} x_{ijk} \cdot t_i \leq c \cdot y_{jk}, \quad \forall k \in K. \quad (4) $$

$$ \sum_{j \in J} y_{jk} \leq 1, \quad \forall k \in K. \quad (5) $$

$$ x_{ijk} = 0, 1 \quad \forall i \in I, j \in J, k \in K. \quad (6) $$

$$ y_{jk} = 0, 1 \quad \forall j \in J, k \in K. \quad (7) $$

The constraint set (2) ensures the precedence relations between tasks with respect to the task-equipment compatibility. The constraint set (3) limits a task to be performed only once in the line. The Constraints (4) ensure that the workload of each station does not violate the cycle time. The constraint set (5) represents that each of the workstations can be assigned only one type of equipment. Constraint sets (6) and (7) define that the decision variables are binary.

# 4. METHOD

## 4.1 Restrict-and-Fix Method

In this paper, decision variables $x_{ijk} \in \mathbb{Z}^{|I|} \times \mathbb{Z}^{|J|} \times \mathbb{Z}^{|L|}$ are local variables because the set of tasks I will be split into $\alpha$ blocks, while $y_{jk}$ are global variables remaining the same variable space during iterations.

To define the subproblem in the implementation of Restrict-and-Fix method, a policy of splitting variable space is proposed. First, a sequence of tasks is constructed according to the precedence graph by implementing two topological sorting approaches denoted as $\gamma$: Breadth-First

<figure><img src="image_3.png" /><figcaption>Fig. 1. Breadth-First Search(BFS) topological sorting of task sequence according to the precedence graph</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 2. Depth-First Search(DFS) topological sorting of task sequence according to the precedence graph</figcaption></figure>

Search (BFS) (see Fig. 1 as an example) and Depth-First Search (DFS) (see Fig. 2 as an example). By implementing the BFS, tasks can be sorted from the root task in the precedence graph, then all its direct successors will be reached until the leaf node in the precedence graph. On the contrary, DFS reaches the node from the root to the leaf alongside a branch in each iteration, then loops through every branch until nodes in all the branches are reached. Then we split the task sequence into $\alpha$ subsequences. The overlapping rate, denoted by $\beta$, represents the ratio of overlapped part with its previous subsequence. Thus, a subsequence with the overlapping partition includes $|I_{sub}^+| = \lceil |I|/\alpha \rceil + \lfloor |I|/\beta \rfloor$ elements. Especially, the last subsequence includes the residual tasks while the first.
<figure><img src="image_5.png" /><figcaption>Fig. 3. Subsequences of tasks with $\alpha = 3$</figcaption></figure>

The subproblem shares the same constraints and objective function as original problem formulated as (1)-(7), the only difference is that the space of decision variables is limited to $x_{ijk} \in \mathbb{Z}^{|I_{sub}|} \times \mathbb{Z}^{|J|} \times \mathbb{Z}^{|L|}$. The sub-problem is denoted as $MILP_1$, $l \in \{1, 2, 3, ..., \alpha\}$. In each iteration, we solve the subproblem in the given variable spaces by fixing decision variables associated with the previous task subsequences except the current overlapped partition.

**Algorithm 1 Restrict-and-Fix Algorithm**

1: **procedure** RESTRICTANDFIXALGORITHM($\alpha, \beta, \gamma$)

2: Sort the set of tasks by implementing $\gamma$ and get the task sequence $I$

3: Split the task sequence $I$ into $\alpha$ basic subsequences $I_1, I_2, ..., I_\alpha$

4: Add the overlapped partition, which are the last several variables of the previous subsequence, at the beginning of current subsequence according to the overlapping rate $\beta$, from which we can derive the number of overlapped tasks $\omega = [\beta \cdot I_{sub}]$. The subsequence with the addition of overlapping partition is denoted as $I_{sub}^+$. Especially, $I_1^+ = I_1$, while $I_n^+ = I_n + I_{n-1}[-\omega:]$

5: $l = 1$

6: **while** $l \le \alpha$ **do**

7: Restrict local decision variables $x_{ijk}$, $\forall i \in I_l^+$, $j \in J$, $k \in [1, \sum_{s=1}^l |I_s|]$.

8: Create global decision variables $y_{jk}$, $\forall j \in J$, $k \in [1, \sum_{s=1}^l |I_s|]$

9: Solve the subproblem with the given local variables and global variables

10: Fix currently restricted and solved local decision variables excluding the overlapping elements with next iteration $x_{ijk}$, $\forall i \in I_l[0: -n]$, $j \in J$, $k \in [1, \sum_{s=1}^l |I_s|]$

11: Update the fixed local variable $x_{ijk}$ and the global variable $y_{jk}$

12: **end while**

13: **return** Solution

14: **end procedure**

Fig. 3 illustrates the procedure on an example. In each iteration, the blue cycles represent the basic task subsequence including tasks to be assigned in this iteration. The red cycles are locked tasks which will be assigned in future

iterations. Green cycles without dash are already assigned tasks of which the decision of assignment on these tasks is fixed in this iteration. Green cycles with dash means the overlapped tasks, which have been assigned in the previous iteration but are not fixed in the current iteration.

The sorted task sequence is split into $\alpha$ subsequences $\{I_1, I_2, ..., I_\alpha\}$. As a result, the associated decision variables $x_{ijk}$ are split into $\alpha$ parts as well while $y_{ij}$ remains the same. To finish solving the RF problem, $\alpha$ times of iterations are required. At first iteration, we solve the $MILP_1$ within the limited local variable associated with $I_1$. In the next iteration, the set of tasks to be assigned consists of $I_2$ including the overlapped part of the sequence of $I_1$. Thus, the overlapped sequence $I_2^+$ is the union of the last 2 elements of $I_1$ and the full sequence $I_2$. The rest of the element in sequence $I_1$ forms the $I_1^-$. Then we solve the aforementioned integer linear programming again with two conditions:

(1) The values of local decision variables $x_{ijk}$ associated with the tasks in sequence $I_1^-$ are fixed.

(2) The binary integer linear programming with the local decision variables $x_{ijk}$ associated with the tasks in the sequence $I_2^+$ is solved.

(3) By solving the subproblem, a new solution of global variables $y_{jk}$ is obtained.

Then we loop through until the $\alpha^{th}$ iteration is finished. At the end of the algorithm, all the decision variables are fixed, resulting in the full solution.

To perform the algorithm while solving the original integer linear programming problem, parameters such as the number of iterations $\alpha$, overlapping rate $\beta$, and the task sequence sorting approaches $\gamma$, can have a significant influence on the algorithm performance. This will be discussed in the next section.

## 5. NUMERICAL EXPERIMENTS

### 5.1 Experiment data

We utilize the benchmark data produced by Otto et al. (2013) in their seminal work. Each dataset instance within this comprehensive collection encompasses detailed information about task numbering, cycle duration, precedence relationships, the order strength of precedence graphs, and the processing times for individual tasks. To conduct our tests, we have randomly selected 20 instances from each of the four distinct instance sizes: 20, 50, 100, and 1000. Furthermore, each instance is accompanied by a qualitative assessment: labeled as trivial, less tricky, tricky, very tricky, or extremely tricky. The guiding principle behind our instance selection in this paper is to ensure an inclusive representation of all trickiness categories.

To generate the compatibility parameter $\kappa_{ij}$, we introduce a flexibility factor of equipment $F_j$, $j \in J$. This ratio determines the number of tasks that equipment $j$ can perform as a proportion of the total number of tasks.

$$F_j = \frac{\sum_{i \in I} \kappa_{ij}}{|I|}, \quad \forall j \in J \qquad (8)$$
For each element of $\kappa_{ij}$, a random value $r$ with the range $[0, 1]$ is generated, if $r \le F_j$, then we assign it a value of 1, and 0 otherwise. To avoid the case that there is no compatible equipment to operate a task, we check whether $\kappa_{ij}$ for each task sums to 0 over all machines, and if this occurs, we randomly select a type of equipment $j \in J$ with probability $\sum_{j \in J} \frac{F_j}{F_j}$ to be able to process task $i$.

## 5.2 Results

The tests are executed on the CCIPL (Centre de Calcul Intensif des Pays de la Loire) utilizing the Inter 2630v4 processor (operating at 2.2 GHz). Each test is constrained to utilize a single thread of the processor and is subject to a time limit of 7200 seconds.

The experiment consists of two parts: the control experiment of solving the entire model formulated as equations with CPLEX, which refers to the MILP method, and also the RF experiment explained in section 4.1. Tests are conducted with different parameter combinations $(\alpha, \beta, \gamma)$.

First, we conduct experiments with MILP and RF for instances of 20, 50, and 100 tasks, respectively, and each experiment investigates the effect of one RF parameter among $(\alpha, \beta, \gamma)$ on the results and compares it with the MILP results, to analyse the optimal RF parameter selection. We can then apply the RF with the optimal parameter selection policy to larger instances: the 1000-task instances. All of these instances have been labelled as extremely tricky in the benchmark dataset, which are therefore difficult for MILP to solve to optimality within reasonable time.

<table><caption>Table 1. Comparison between MILP and the best RF results</caption><thead><tr><th rowspan="2">|I|</th><th colspan="2">MILP</th><th colspan="4">RF</th></tr><tr><th>t<sub>sol</sub></th><th>Gap (%)</th><th>(α*, β*, γ*)</th><th>δ(%)</th><th>t<sub>sol</sub></th><th>Gap (%)</th></tr></thead><tbody><tr><td>20</td><td>185</td><td>0</td><td>(3, 0.5, BFS)</td><td>7.6</td><td>0.08</td><td>0</td></tr><tr><td rowspan="2">50</td><td rowspan="2">7200</td><td rowspan="2">7.6</td><td>(2, 0.4, BFS)</td><td>2.7</td><td>4589</td><td>0</td></tr><tr><td>(3, 0.5, BFS)</td><td>5.7</td><td>405</td><td>0</td></tr><tr><td rowspan="3">100</td><td rowspan="3">7200</td><td rowspan="3">10.2</td><td>(2, 0.5, BFS)</td><td><b>-1.1</b></td><td>7200</td><td>8.2</td></tr><tr><td>(4, 0.5, BFS)</td><td>1.7</td><td>4229</td><td>0</td></tr><tr><td>(5, 0.5, BFS)</td><td>3.1</td><td>1115</td><td>0</td></tr></tbody></table>

Table 1 shows objective values of selected RF heuristic method laying on the Pareto Front compared to MILP method. For the instances with 100 tasks, 15 points lying on the Pareto front are observed. We select three of them (see in Fig. 4) to present their exact values in Table 1 for discussion. $|I|$ represents the number of tasks. The values in each row of this table are the average of results of the selected 20 instances of the given size $|I|$. The MILP results are the control experiment, where $t_{sol}$ is the average solution times, and the Gap represents the gap of the CPLEX solver. For heuristic result columns, $\delta$ represents the deviation between heuristic results and MILP results, explained by the equation (9).

$$ \delta = \frac{\text{RF} - \text{MILP}}{\text{MILP}} \qquad (9) $$

Since there is a CPLEX gap associated with each iteration when we solve the subproblem by implementing the Branch-and-Bound method, the column labeled Gap provides the average CPLEX gap across all iterations.

<figure><img src="image_6.png" /><figcaption>Fig. 4. Scatter plot of 100 task instances with highlighted Pareto Front</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 5. Box plot of 100 task instance results with different number of iterations and decomposition approaches</figcaption></figure>

The column $(\alpha^*, \beta^*, \gamma^*)$ is the parameter combinations of which the results lie on the Pareto Front.

Fig. 4 illustrates 100 task instance results. In this figure, each point corresponds to one parameter combination $(\alpha, \beta, \gamma)$ and the projection of the point position on the x axis and y axis represents $t_{sol}$ and $\delta$, respectively. 15 points in orange lie on the Pareto front, derived by the fact that they are not dominated by other points. In this way, practitioners can choose the best trade-off configuration of the RF to meet their actual requirements. The MILP result point is highlighted in red. It's $\delta$ equals 1 since it is the control data of the experiment.

From the results data in Table 1, the following conclusions can be drawn:

First, the BFS outperforms the DFS sorting approach, since all points on the Pareto front are BFS. More precisely, see Fig. 5 as an example of 100 task instances illustrating the distribution of gap $\delta$ on the x axis of the number of iterations $\alpha$. This result corresponds to intuition: at each iteration of the RF method, BFS leads to a more compact assignment of tasks to workstations, which results in fewer workstations required in the assembly line.

Moreover, the RF method shows that the maximum gap with the MILP results is not greater than 7.6%. Especially, the heuristic method outperforms MILP in 100 task instances with parameter combination (2, 0.5, BFS). As a result, we can trust the proposed approach to solve the larger problem, which is difficult to get a good solution.
Furthermore, the heuristic configuration with a small $\alpha$ and a large $\beta$ generally results in a long solving time but a low gap with the MILP result. With a large subproblem, RF is less likely to fall into suboptimal solutions. The overlap rate $\beta$ works as a disturbance that can also help the algorithm escape the trap of sub-optimality. The ideal is to select the smallest $\alpha$ and the biggest $\beta$ that produce enough fast computations.

<table><caption>Table 2. Result table of 1000 task instances</caption><thead><tr><th colspan="2">MILP</th><th colspan="3">RF</th></tr><tr><th>t<sub>sol</sub></th><th>Gap</th><th>(α*, β*, γ*)</th><th>Obj. Value</th><th>t<sub>sol</sub></th><th>Gap (%)</th></tr></thead><tbody><tr><td>-</td><td>-</td><td>(20, 0.5, BFS)</td><td>13.13 × 10<sup>6</sup></td><td>7478</td><td>1.7</td></tr><tr><td>-</td><td>-</td><td>(50, 0.5, BFS)</td><td>13.41 × 10<sup>6</sup></td><td>2797</td><td>0</td></tr><tr><td>-</td><td>-</td><td>(50, 0, BFS)</td><td>13.76 × 10<sup>6</sup></td><td><b>420</b></td><td>0</td></tr></tbody></table>

With an increase in the size of the problem, the solving time easily reaches the time limit. In Table 2, a feasible solution of 1000 task instances is impossible to obtain within the time limit. However, by implementing the heuristic method, a feasible solution can be found in 420 s with the parameters $(\alpha, \beta, \gamma) = (50, 0, BFS)$. While more computational time was allowed, the RF with the chosen parameter combination $(20, 0.5, BFS)$ can provide better objective function values.

In practice, when implementing the proposed method to solve the RALBP model, practitioners can select the most suitable combination of RF parameters based on their priorities—whether minimizing computational time or reducing the deviation from optimality. This choice depends on the sensitivity to solving time versus solution quality. When the instance size is small enough to be solved directly by a solver within a user-defined time limit, using the RF method can significantly reduce computational time while still providing a high-quality approximation. Conversely, when the instance size is too large for exact solvers like CPLEX to perform efficiently, the RF method can even achieve better objective values within the same time frame, thereby offering an overall improved solution.

## 6. CONCLUSION

In this paper, we propose a RF method to address the scalability issue of the flexible robotic assembly line balancing problem. Our experimental results show that the proposed approach performs well since it obtains close to optimal solution on small size instances, and it can take instances with up to 1000 tasks.

This approach can also be applied to solve the stochastic model of the design of robotic assembly lines with uncertain product family evolution. Modern assembly lines often need to periodically change the line configuration to cope with the evolution of the product. In this case, we first need to generate a scenario tree that contains the set of tasks, precedence constraints, task execution times, compatibility matrices, and equipment information, and compute the optimal configuration for each scenario one by one. The size of the decision variable space of the model increases rapidly as a result of the expansion of the scenario tree. This makes it difficult to solve the problem using the traditional branch-and-bound method. The RF algorithm is a good approach to address the dimensionality issue. By decomposing the scenario tree or

the decision variable space in each scenario and solving the sub-problems sequentially, the RF algorithm has great potential to be applied to large-scale uncertain assembly line design problems.

## ACKNOWLEDGEMENTS

This paper is financed by the ALICIA project of HORI-ZON.2.4 - Digital, Industry and Space (https://doi.org/10.3030/101091577). This research used resources of the GLiCID Computing Facility (Ligerien Group for Intensive Distributed Computing, https://doi.org/10.60487/glicid, Pays de la Loire, France)

## REFERENCES

* Bukchin, J. and Tzur, M. (2000). Design of flexible assembly line to minimize equipment cost. *Iie transactions*, 32(7), 585–598.

* Daoud, S., Chehade, H., Yalaoui, F., and Amodeo, L. (2014). Solving a robotic assembly line balancing problem using efficient hybrid methods. *Journal of Heuristics*, 20(3), 235–259.

* Joncour, C., Kritter, J., Michel, S., and Schepler, X. (2023). Generalized relax-and-fix heuristic. *Computers & Operations Research*, 149, 106038.

* Levitin, G., Rubinovitz, J., and Shnits, B. (2006). A genetic algorithm for robotic assembly line balancing. *European Journal of Operational Research*, 168(3), 811–825.

* Otto, A., Otto, C., and Scholl, A. (2013). Systematic data generation and test design for solution algorithms on the example of salbpgen for assembly line balancing. *European Journal of Operational Research*, 228(1), 33–45.

* Pochet, Y. and Wolsey, L.A. (2006). *Production planning by mixed integer programming*, volume 149. Springer.

* Rubinovitz, J. (1991). Design and balancing of robotic assembly lines. In *Proceedings of the Fourth World Conference on Robotics Research, Pittsburgh, PA, 1991*.

* Rubinovitz, J., Bukchin, J., and Lenz, E. (1993). Ralb-a heuristic algorithm for design and balancing of robotic assembly lines. *CIRP annals*, 42(1), 497–500.