A new upper bound based on Dantzig-Wolfe decomposition to maximize the stability radius of a simple assembly line under uncertainty

Rui S. Shibasaki, André Rossi and Evgeny Gurevsky

European Journal of Operational Research, 2024, vol. 313, issue 3, 1015-1030

Abstract: 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.

Keywords: Manufacturing; Assembly line balancing; Robustness; Stability radius; Dantzig-Wolfe decomposition (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723006756
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:313:y:2024:i:3:p:1015-1030

DOI: 10.1016/j.ejor.2023.08.046

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().