A Benders’ Decomposition Algorithm for Balancing and Sequencing of the Mixed-Model Multi-Manned Assembly Lines

Assembly lines of large-size products usually allow multiple workers to process tasks simultaneously on the same product. Meanwhile, due to the increasing demand of customized products, a diverse product mix with more product models and optional features is necessary. Although line balancing and model sequencing are interwoven, only the balancing problem of the mixed-model multi-manned assembly lines (MMALs) has been explored. In this study, a new mixed-integer linear programming model is proposed for balancing and sequencing of MMALs to minimize the number of workers, the number of stations, and the amount of utility work. An innovative approach based on Benders' decomposition algorithm (BDA) is developed. Valid inequalities based on maximal cliques are generated to deal with the incompatible tasks which cannot be assigned to the same station to tighten and reduce the size of the formulation. An initial solution based on the greedy algorithm feeds the BDA to accelerate the convergence. Only one branch-and-search tree is built for the master problem to speed up the algorithm, and optimality cuts based on the subproblems are used as lazy cuts. The effectiveness of the proposed BDA is demonstrated by numerical results.