A Large Neighborhood Search Metaheuristic for the Stochastic Mixed Model Assembly Line Balancing Problem with Walking Workers

This work proposes a Large Neighborhood Search Metaheuristic for solving a mixed-model assembly line balancing problem with walking workers and dynamic task assignment. The considered problem is a multi-stage stochastic program with integer recourse. These problems are very hard to solve because the number of binary variables increases exponentially with the number of production cycles. We study different decomposition approaches, and our results suggest that re-optimizing for a sub-tree outperforms other decompositions, such as model-based or station decomposition.