A new upper bound based on Dantzig-Wolfe decomposition to maximize the stability radius of a simple assembly line under uncertainty
Shibasaki, Rui S.; Rossi, André; Gurevsky, Evgeny (2024), A new upper bound based on Dantzig-Wolfe decomposition to maximize the stability radius of a simple assembly line under uncertainty, European Journal of Operational Research, 313, 3, p. 1015-1030. 10.1016/j.ejor.2023.08.046
TypeArticle accepté pour publication ou publié
External document linkhttps://u-picardie.hal.science/hal-04192659
Journal nameEuropean Journal of Operational Research
MetadataShow full item record
Author(s)Shibasaki, Rui S.
Modélisation, Information et Systèmes - UR UPJV 4290 [MIS]
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Laboratoire des Sciences du Numérique de Nantes [LS2N]
Abstract (EN)This work presents a new upper bounding approach, based on Dantzig-Wolfe decomposition and column generation, for a relatively novel problem of designing simple assembly lines to maximize their stability radius under uncertainty in task processing times. The problem considers task precedence constraints, a fixed cycle time, and a fixed number of workstations. This NP-hard optimization problem aims to assign a given set of assembly tasks to workstations in order to find the most robust feasible line configuration. The robustness of the configuration is measured by the stability radius with respect to its feasibility, i.e., the maximum increase in task processing times, for which the cycle time constraint remains satisfied. The reformulation resulting from the Dantzig-Wolfe decomposition is enhanced with valid inequalities and tight assignment intervals are used to reduce the solution space of pricing sub-problems. In addition, a bisection method is proposed as a pre-processing technique to improve the initial upper bound on the stability radius, which is an input for the pricing sub-problem. Computational experiments show that the proposed approach can significantly improve the upper bound on the stability radius for the most challenging instances.
Subjects / KeywordsManufacturing; Assembly line balancing; Robustness; Stability radius; Dantzig-Wolfe decomposition
Showing items related by title and author.
Gurevsky, Evgeny; Rasamimanana, Andry; Pirogov, Aleksandr; Dolgui, Alexandre; Rossi, André (2022) Article accepté pour publication ou publié
Robust balancing of transfer lines with blocks of uncertain parallel tasks under fixed cycle time and space restrictions Pirogov, Aleksandr; Gurevsky, Evgeny; Rossi, André; Dolgui, Alexandre (2019) Article accepté pour publication ou publié
Caprara, Alberto; Furini, Fabio; Malaguti, Enrico; Traversi, Emiliano (2016) Article accepté pour publication ou publié