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

HAL
open science

# Enhanced MILP approach for maximizing the robustness of paced transfer lines with uncertain parallel tasks and fixed number of machines

Aleksandr Pirogov, Evgeny Gurevsky, André Rossi, Alexandre Dolgui

► To cite this version:

Aleksandr Pirogov, Evgeny Gurevsky, André Rossi, Alexandre Dolgui. Enhanced MILP approach for maximizing the robustness of paced transfer lines with uncertain parallel tasks and fixed number of machines. 19th Congress of the French Society of Operations Research and Decision Aid (ROADEF 2018), Feb 2018, Lorient, France. hal-01713722

HAL Id: hal-01713722

https://hal.science/hal-01713722

Submitted on 14 Feb 2023

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.

Public Domain
Enhanced MILP approach for maximizing the robustness of
paced transfer lines with uncertain parallel tasks and fixed
number of machines

Aleksandr Pirogov¹, Evgeny Gurevsky², André Rossi³, Alexandre Dolgui¹

¹ LS2N, Institut Mines-Télécom Atlantique, Nantes, France

² LS2N, Université de Nantes, France

³ LERIA, Université d'Angers, France

**Keywords** : transfer lines, uncertainty, robust optimization, stability radius, optimality-based cuts, MILP

Context

We address a complex combinatorial optimization problem arising in the design of transfer
lines and aiming to handle uncertain production tasks, whose processing time is likely to vary.
The studied transfer line has a fixed number of machines, where each of them is equipped
by blocks. Each block is dedicated to execute several production tasks simultaneously. The
number of tasks per block is limited, and the tasks are subject to the following non-strict
precedence constraints: if task *i* precedes task *j*, then *j* can be assigned to the same block as
*i* or to one of the succeeding blocks. The block time is determined by the longest processing
time among the tasks assigned to it, and the machine load by the sum of the block time over
all the blocks allocated to the machine. Since the considered transfer lines are paced, the load
of any machine cannot be greater than a given duration referred to as the cycle time. Thus,
the addressed design problem is to assign all the tasks to blocks, and allocate these latter to
the machines, determining inside them the order of blocks activation, subject to the mentioned
above constraints so as to stand the uncertainty of task processing time as much as possible.

The transfer lines are designed for a long-term period of usage and have no possibility for
reconfiguration due to its significant cost. Therefore, the classic stochastic approach is not
applicable for handling the uncertain task processing times, because of the absence of reliable
historical data on their variability for establishing the corresponding adequate probability dis-
tributions. Only a subset of tasks, whose processing time is subject to be uncertain without
any additional information, can be identified by experts before the line design stage. As a con-
sequence, for evaluating the designed line configuration in such a situation, a new appropriate
approach is needed.

As it was shown in our previous work [2], dedicated to a similar industrial situation, but
for the case of assembly lines, an approach, based on the concept of *stability radius*, can be
considered as a suitable alternative to stochastic one. Thus, usually measured in the two
classic metrics *l*₁ and *l*∞, the stability radius can be interpreted as the maximal amplitude of
variations for uncertain task processing times, which can be supported by the line configuration
without violating its admissibility. The definition of stability radius follows well the principle of
robustness, since the greater its value, the greater the ability of the intended line configuration
to resist against uncertainty. Consequently, seeking a line configuration with the greatest
stability radius becomes a natural solution for the presented context.
## Proposed approach

In order to solve exactly the mentioned above problem, we firstly construct its compact mixed-integer linear programming (MILP) formulation for each metric of stability radius, $l_1$ and $l_\infty$, and then investigate some useful problem properties permitting to reduce the search space by generating new specific cuts. Namely, based especially on the precedence constraints and the nominal task processing times, it is possible to construct for each task $j$ a set $Q_j$ of blocks able to contain $j$ and for each machine $p$ a set $U_p$ of blocks, known beforehand to be empty. Computing $Q_j$ and $U_p$ in a pre-processing manner reinforces the initial MILP model by taking into account the following constraints:

$$x_{jk} = 0, \forall j \in V, \forall k \notin Q_j,$$

$$y_k = 0, \forall p \in W, \forall k \in U_p,$$

where $V$ is the set of tasks, $W$ is the set of machines, $x_{jk}$ equals 1, if task $j$ is assigned to block $k$ and 0 otherwise, and $y_k$ is 1, if at least one task is assigned to block $k$, 0 otherwise.

The particularity of the studied problem consists in the fact that, based on the same mentioned above problem properties, the availability of a new best feasible solution allows for adjusting the sets $Q_j$ and $U_p$ and, as a consequence, to generate new tighter constraints:

$$x_{jk} = 0, \forall j \in V, \forall k \in Q_j^{(l-1)} \setminus Q_j^{(l)},$$

$$y_k = 0, \forall p \in W, \forall k \in U_p^{(l)} \setminus U_p^{(l-1)},$$

where $Q_j^{(l)}$ and $U_p^{(l)}$ are respectively the states of $Q_j$ and $U_p$ after the detection of the $l$-th new best feasible solution (here, $Q_j^{(0)} = Q_j$ and $U_p^{(0)} = U_p$). The latter constraints can be considered as optimality-based cuts, since they do not remove all optimal solutions of the initial MILP, but are capable to exclude from consideration some feasible ones.

The presentation of this work will be dedicated to presenting in details the concept of stability radius, the used problem properties and the realization of optimality-based cuts generation within the framework of commercial solvers such as IBM ILOG CPLEX, for which an initial feasible solution will be provided by an appropriate heuristic method, described in [1]. The performance of the proposed solution technique and the corresponding computational results on the devoted problem instances will be discussed. Potential improvements and suggestions for future work will be given as well.

## References

[1] Gurevsky, E., Battaïa, O., Dolgui, A., 2013. Stability measure for a generalized assembly line balancing problem. Discrete Applied Mathematics 161(3): 377-394.

[2] Rossi, A., Gurevsky, E., Battaïa, O., Dolgui, A., 2016. Maximizing the robustness for simple assembly lines with fixed cycle time and limited number of workstations. Discrete Applied Mathematics 208: 123-136.