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

HAL
open science

# Robust scheduling of assembly lines with and without parallel workstations

Xavier Schepler, André Rossi, Evgeny Gurevsky, Alexandre Dolgui

► To cite this version:

Xavier Schepler, André Rossi, Evgeny Gurevsky, Alexandre Dolgui. Robust scheduling of assembly lines with and without parallel workstations. 18th Congress of the French Society of Operations Research and Decision Aid (ROADEF 2017), Feb 2017, Metz, France. hal-01474542

HAL Id: hal-01474542

https://hal.science/hal-01474542

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
Robust scheduling of assembly lines
with and without parallel workstations

Xavier Schepler¹, André Rossi¹, Evgeny Gurevsky², Alexandre Dolgui³

1 LERIA, Université d'Angers, France

² LS2N, Université de Nantes, France

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

**Keywords** : assembly line balancing, paralleling workstations, robustness, uncertainty.

Context

The design of assembly lines is an important industrial challenge that includes several issues
dealing with optimization aspects, named in the literature as *balancing problems*. In gen-
eral (see, for example, the survey [4]), they consist in a partition of the set of all necessary
production tasks among workstations with respect to a given production goal and subject to
some technological restrictions such as precedence, cycle time, exclusion, inclusion or space
constraints. One of the important goals at the assembly line design stage is the anticipation
of the task time variability in order to construct a robust line configuration for a long term
usage.

Since 2012 (see [1, 2, 3]), we study and popularize an alternative robust approach for evalu-
ating assembly lines in such a situation. This approach is based on a specific indicator, called
as the *stability radius*. Given a feasible assembly line configuration with already assigned tasks,
it is calculated as the maximal amplitude of the deviations of the uncertain task times from
their nominal values for which the system admissibility remains respected. The most practical
advantage of using this indicator comparing with stochastic and fuzzy approaches consists in
the fact that there is no need to possess reliable historical data on the variability of processing
task times.

Design an assembly line configuration with the greatest stability radius is a new difficult
combinatorial optimization problem that has been recently introduced and studied in our
work [3] for simple assembly lines and represents an important object of study from both
practical and algorithmic points of view. One of the goals of our work enrolls the perspectives
of that paper and will be dedicated to the optimal design of assembly lines with extra large
task time variations that can even be greater than the cycle time. In response, the only
technological solution, but still very expensive, is the installation of parallel workstations with
duplicated tasks that conducts us to consider new complex industrial optimization problems
aiming to minimize the number of parallel workstations and seeking the trade-off between the
corresponding stability radius to be maximized.

Research directions

This communication will be at first dealt with the description and motivation of our project.
Then, we will present four dedicated problems, noted respectively as *P*, *Q*, *R* and *S*. For all
these problems, the common restrictions are the precedence and cycle time constraints. Given
a fixed number of linearly ordered workstations, the problem *P* seeks an assignment of tasks
to them so as to maximize the value of stability radius. As concerns the problem *Q*, it aims,
at the contrary, to minimize the total number of used workstations, provided that the stability
radius is not less than some desired value.

Compared with *P* and *Q*, the paralleling of workstations is authorized for *R* and *S*. Adding one workstation in parallel to an already existing one allows to double its maximal working time locally, adding two workstations to triple it, etc. The problem *R* is identical to *P*, except that there exists an established limit on the number of workstations, which can be added in parallel. Unlike *R*, the problem *S* is to minimize the total number of workstations added in parallel, provided, as for the problem *Q*, that the stability radius has at least a given value.

We will report advancements of the development of exact methods and corresponding nu-
merical results for these problems, based on their compact formulations as mixed-integer linear
programs, and on extended formulations, obtained by Dantzig-Wolfe decomposition. We will
also provide the computational complexity for some combinatorial optimization sub-problems
that can be appeared in. Upper/lower bounds on optima, efficient dominance properties and
appropriate branching techniques will be investigated as well.

**Acknowledgement** This research is conducted in the framework of the programme «RFI AtlanSTIC 2020», supported by the French Region «Pays de la Loire» and the European Regional Development Fund.

References

[1] Gurevsky, E., Battaïa, O., Dolgui, A., 2012. Balancing of simple assembly lines under variations of task processing times. Annals of Operations Research 201 (1), 265-286.

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

[3] 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.

[4] Scholl, A., Becker, C., 2006. State-of-the-art exact and heuristic solution procedures for simple assembly line balancing. European Journal of Operational Research 168 (3), 666-693.