A Branch-and-Price Algorithm for Balancing Two-Sided Assembly Lines with Zoning Constraints. (14th December 2021)

• Record Type: Journal Article
• Authors: Yin, Qidong; Luo, Xiaochuan; Hohenstein, Julien
• Other Names: Papadopoulos Basil Academic Editor.
• Is Part Of: Journal of mathematics. Volume 2021(2021)
• Publication Date: 2021-12-14
• Subjects: Mathematics -- Periodicals; Mathematics; Periodicals; 510
• DOI: 10.1155/2021/4196228
• Languages: English
• ISSNs: 2314-4629

Abstract

Abstract : Two-sided assembly lines are widely used in the large-size product manufacturing industry, especially for automotive assembly production. Balancing the assembly line is significant for assembly process planning and assembly production. In this study, we develop a novel and exact method to optimize the two-sided assembly line balancing problem with zoning constraints (TALBz), in which the aim is to minimize the number of mated-stations considering the task restrictions. A mixed-integer programming model is employed to exactly describe the TALBz problem. To strengthen the computational efficiency, we apply Dantzig–Wolfe decomposition to reformulate the TALBz problem. We further propose a branch-and-price (B&P) algorithm that integrates the column generation approach into a branch-and-bound frame. Both the benchmark datasets with zoning constraints and without zoning constraints are tested to evaluate the performance of the B&P algorithm. The numerical results show that our proposed approach can obtain optimal solutions efficiently on most cases. In addition, experiments on the real-world datasets originating from passenger vehicle assembly lines are conducted. The proposed B&P algorithm shows its advantage in tackling practical problems with the task restrictions. This developed methodology therefore provides insight for solving large-scale TALBz problems in practice.