2020/04/28 by Nícolas P. Campana, Nicolas P. Campana, Manuel Iori +5
Engineering · Mathematics · #Assembly Line Balancing Optimization #Combinatorics (math.CO) #FOS: Mathematics #Manufacturing Process and Optimization #Optimization and Control (math.OC) #Scheduling and Optimization Algorithms #math.CO #math.OC
paper · pdf · doi:10.48550/arxiv.2004.13396
arxiv created 2020/04/28 · openalex publication_date 2020/04/28 · arxiv updated 2020/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper proposes new algorithms for the assembly line balancing problem with hierarchical worker assignment (ALBHW). The ALBHW appears in real industrial contexts where companies deal with a multi-skilled workforce. It considers task execution times that vary depending on the worker type to whom the task is assigned. Qualification levels among workers are ranked hierarchically, where a lower qualified worker costs less but requires larger execution times. The aim is to assign workers and tasks to the stations of an assembly line, in such a way that cycle time and precedence constraints are satisfied, and the total cost is minimized. In this paper, we first present a mathematical model and improve it with preprocessing techniques. Then, we propose a constructive heuristic and a variable neighborhood descent that are useful to solve large instances. Extensive computational experiments on benchmark instances prove the effectiveness of the algorithms.