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

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.