Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Battaïa, O., et al.: Workforce minimization for a mixed-model assembly line in the automotive industry. Int. J. Prod. Econ. 170, 489–500 (2015). https://doi.org/10.1016/j.ijpe.2015.05.038
Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming. Springer, New York (2011). https://doi.org/10.1007/978-1-4614-0237-4
Boysen, N., Schulze, P., Scholl, A.: Assembly line balancing: what happened in the last fifteen years? Eur. J. Oper. Res. 301(3), 797–814 (2022). https://doi.org/10.1016/j.ejor.2021.11.043
Gurobi Optimization, LLC: Gurobi Optimizer Reference Manual (2023). https://www.gurobi.com
Hashemi-Petroodi, S.E., Thevenin, S., Kovalev, S., Dolgui, A.: The impact of dynamic tasks assignment in paced mixed-model assembly line with moving workers. In: Lalic, B., Majstorovic, V., Marjanovic, U., von Cieminski, G., Romero, D. (eds.) APMS 2020. IAICT, vol. 592, pp. 509–517. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-57997-5_59
Hashemi-Petroodi, S.E., Thevenin, S., Kovalev, S., Dolgui, A.: Model-dependent task assignment in multi-manned mixed-model assembly lines with walking workers. Omega 113, 102688 (2022). https://doi.org/10.1016/j.omega.2022.102688
Otto, A., Otto, C., Scholl, A.: Systematic data generation and test design for solution algorithms on the example of SALBPGen for assembly line balancing. Eur. J. Oper. Res. 228(1), 33–45 (2013). https://doi.org/10.1016/j.ejor.2012.12.029
Pisinger, D., Ropke, S.: Large neighborhood search. In: Gendreau, M., Potvin, J.-Y. (eds.) Handbook of Metaheuristics. ISORMS, vol. 272, pp. 99–127. Springer, Cham (2019). https://doi.org/10.1007/978-3-319-91086-4_4
Rekiek, B., Delchambre, A.: Assembly Line Design: The Balancing of Mixed-Model Hybrid Assembly Lines with Genetic Algorithms. Springer Series in Advanced Manufacturing, Springer, London (2006). https://doi.org/10.1007/b138846
Shaw, P.: Using constraint programming and local search methods to solve vehicle routing problems. In: Maher, M., Puget, J.-F. (eds.) CP 1998. LNCS, vol. 1520, pp. 417–431. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-49481-2_30
Sikora, C.G.S.: Balancing mixed-model assembly lines for random sequences. Eur. J. Oper. Res. 314(2), 597–611 (2024). https://doi.org/10.1016/j.ejor.2023.10.008
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Thompson, J.O., Lahrichi, N., Meyer, P., Mohammadi, M., Thevenin, S. (2024). A Large Neighborhood Search Metaheuristic for the Stochastic Mixed Model Assembly Line Balancing Problem with Walking Workers. In: Sevaux, M., Olteanu, AL., Pardo, E.G., Sifaleras, A., Makboul, S. (eds) Metaheuristics. MIC 2024. Lecture Notes in Computer Science, vol 14754. Springer, Cham. https://doi.org/10.1007/978-3-031-62922-8_24
Download citation
DOI: https://doi.org/10.1007/978-3-031-62922-8_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-62921-1
Online ISBN: 978-3-031-62922-8
eBook Packages: Computer ScienceComputer Science (R0)