# U-Shaped Assembly Line Balancing under Uncertainty: A Robust Optimization Model

Öncü Hazir, Alexandre Dolgui

► To cite this version:

Öncü Hazir, Alexandre Dolgui. U-Shaped Assembly Line Balancing under Uncertainty: A Robust Optimization Model. 12e congrès de la société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2011), Mar 2011, Saint Etienne, France. emse-00679618

HAL Id: emse-00679618

https://hal-emse.ccsd.cnrs.fr/emse-00679618

Submitted on 5 Aug 2021

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# U-Shaped Assembly Line Balancing under Uncertainty : A
## Robust Optimization Model

Öncü Hazır¹, Alexandre Dolgui¹

École Nationale Supérieure des Mines de Saint-Étienne

158, cours Fauriel, 42023 Saint-Étienne cedex, France

`{hazir,dolgui}@emse.fr`

**Mots-clés** : assembly line balancing, uncertainty, robust optimization

## 1 Introduction

In this research, we address U-line balancing under uncertainty and propose a robust optimization model to generate assembly lines that are protected against disruptions in operation times. U-shaped layouts have been widely investigated in literature because they are more efficient and flexible than traditional straight assembly lines. They offer more choices for grouping tasks since the same worker could work in different stations which are located at entrance and exit sides of the lines.

Majority of the existing research on assembly line balancing makes a simplifying assumption and models deterministic environments. However, in real life we are subject to various sources of uncertainty, like variability in operation times. To avoid deviations from production targets, we will use robust optimization, which is a fundamental optimization method that hedge against uncertainty. The other approaches are stochastic programming, sensitivity analysis, parametric programming and fuzzy programming.

Robust optimization addresses minmax and minmax regret objectives (see Kouvelis and Yu [1]). However, pessimistic solutions could be generated. To avoid over pessimism, Bertsimas and Sim [2] have proposed a restricted uncertainty model in which only a subset of coefficients are driven to their upper bounds. We use this approach to formulate the robust U-type assembly line problem with minimum number of workstations (UALBP-1). More specifically, we aim to design assembly lines that could are protected against variability in operations times. Cycle time is fixed and variability affect the number of stations installed.

## 2 Robust Optimization Model

A product is required to be assembled within a given cycle time C by installing the minimum number of workstations. Precedence relations among operations should be satisfied. A graph, $G = (N, A)$, where N is the set of nodes and $A \subseteq N \times N$ is the set of arcs, is used to model these relations. U-lines allow both forward and backward assignments to the stations, for this purpose, [3] introduced to add an auxiliary network called as "Phantom network".

We consider interval uncertainty for operation times, that is the uncertain times, $\tilde{t}_j$ can take values in an interval between nominal and upper bound value, i.e. $\tilde{t}_j \in [t_j, \tilde{t}_j]$, $j = 1, \dots, n$. We assume that nominal values are aggressive time estimates so that it is less likely to have values lower than it. In that sense, the deviation, $d_j = \tilde{t}_j - t_j$, defines the the risk that could be faced for operation j.

A mixed integer-programming (MIP) model of robust UALBP-1 could be stated as follows :

$$ \text{Min} \quad \sum_{k=LB+1}^{UB} z_k \qquad (1) $$
subject to

$$ \sum_{k=1}^{UB} (x_{ik} + y_{ik}) = 1, \quad \text{for } i = 1, \dots, n \qquad (2) $$

$$ \sum_{i=1}^{n} t_i (x_{ik} + y_{ik}) + g_k(x, y) \leq C, \quad \text{for } k = 1, \dots, LB \qquad (3) $$

$$ \sum_{i=1}^{n} t_i (x_{ik} + y_{ik}) + g_k(x, y) \leq Cz_k, \quad \text{for } k = LB + 1, \dots, UB \qquad (4) $$

$$ \sum_{k=1}^{UB} (UB - k + 1)(x_{ik} - x_{jk}) \geq 0, \quad \forall (i, j) \in A \qquad (5) $$

$$ \sum_{k=1}^{UB} (UB - k + 1)(y_{jk} - x_{ik}) \geq 0, \quad \forall (i, j) \in A \qquad (6) $$

$$ x_{ik}, y_{ik}, z_k \in \{0, 1\} \quad \forall i, k. \qquad (7) $$

where

$$ g_k(x, y) = \text{Max} \left\{ \sum_{i=1}^{n} d_i (x_{ik} + y_{ik}) u_{ik} : \sum_{i=1}^{n} u_{ik} \leq \Gamma, u_{ik} \in \{0, 1\} \right\}, \forall k \qquad (8) $$

This model considers K stations and n operations. The binary decision variables $x_{ik}$ and $y_{ik}$ assign operation i to station k respectively either to the front or back of the station (7). In addition, binary variable $z_k$ is assigned to 1 if station k is used to process some operations. We minimize the total number of work stations (1), while a unique station is assigned to each operation (2), and precedence constraints are not violated (5) and (6). The constraint sets (3) and (4) are used to define the cycle time. LB and UB respectively denote a lower and upper bound for number of work stations.

We note that $g_k(x, y)$ defines the maximal time deviation for each station k. The set of operations that are subject to uncertainty are determined by the binary vector $u$, i.e. $\{j : u_{jk} = 1, \forall k\}$. These operations will have execution times at their upper bounds. The parameter $\Gamma$ defines the pessimism level of the decision maker. For instance, when $\Gamma = 0$, we reach to the deterministic problem with nominal time values. In contrast, high values of this parameter indicate a risk-averse decision making behavior.

## 3 Conclusion

We address U shaped line balancing under interval uncertainty for operation times in this research and propose an robust optimization model. A decomposition based solution algorithm will be proposed and the efficiency of the algorithm will be tested with some computational experiments. The main contribution of this research is to be a pioneer work on robust U-shaped assembly line balancing and it will serve as a basis work for further research. The model and algorithm could be extended to model robust versions of mixed-model assembly lines.

## Références

[1] Kouvelis, P. and G. Yu. 1997. Robust Discrete Optimization and Its Applications. Norwell : Kluwer Academic Publishers.

[2] Bertsimas, D. and M. Sim. 2003. Robust Discrete Optimization and Network Flows, Mathematical Programming 98 : 49-71.

[3] T. L. Urban, Note. Optimal balancing of U-shaped assembly lines, Management Science, vol. 44, 738-741, 1998.