A Branch-and-Price Algorithm for Balancing Two-Sided Assembly Lines with Zoning Constraints
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 t...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2021-01-01
|
| Series: | Journal of Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2021/4196228 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832545904110862336 |
|---|---|
| author | Qidong Yin Xiaochuan Luo Julien Hohenstein |
| author_facet | Qidong Yin Xiaochuan Luo Julien Hohenstein |
| author_sort | Qidong Yin |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-19ce7b76b65e4ff7b6da4fddde6b3c8e |
| institution | Kabale University |
| issn | 2314-4785 |
| language | English |
| publishDate | 2021-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Mathematics |
| spelling | doaj-art-19ce7b76b65e4ff7b6da4fddde6b3c8e2025-02-03T07:24:16ZengWileyJournal of Mathematics2314-47852021-01-01202110.1155/2021/4196228A Branch-and-Price Algorithm for Balancing Two-Sided Assembly Lines with Zoning ConstraintsQidong Yin0Xiaochuan Luo1Julien Hohenstein2College of Information Science and EngineeringCollege of Information Science and EngineeringiFactory Munich, BMW AGTwo-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.http://dx.doi.org/10.1155/2021/4196228 |
| spellingShingle | Qidong Yin Xiaochuan Luo Julien Hohenstein A Branch-and-Price Algorithm for Balancing Two-Sided Assembly Lines with Zoning Constraints Journal of Mathematics |
| title | A Branch-and-Price Algorithm for Balancing Two-Sided Assembly Lines with Zoning Constraints |
| title_full | A Branch-and-Price Algorithm for Balancing Two-Sided Assembly Lines with Zoning Constraints |
| title_fullStr | A Branch-and-Price Algorithm for Balancing Two-Sided Assembly Lines with Zoning Constraints |
| title_full_unstemmed | A Branch-and-Price Algorithm for Balancing Two-Sided Assembly Lines with Zoning Constraints |
| title_short | A Branch-and-Price Algorithm for Balancing Two-Sided Assembly Lines with Zoning Constraints |
| title_sort | branch and price algorithm for balancing two sided assembly lines with zoning constraints |
| url | http://dx.doi.org/10.1155/2021/4196228 |
| work_keys_str_mv | AT qidongyin abranchandpricealgorithmforbalancingtwosidedassemblylineswithzoningconstraints AT xiaochuanluo abranchandpricealgorithmforbalancingtwosidedassemblylineswithzoningconstraints AT julienhohenstein abranchandpricealgorithmforbalancingtwosidedassemblylineswithzoningconstraints AT qidongyin branchandpricealgorithmforbalancingtwosidedassemblylineswithzoningconstraints AT xiaochuanluo branchandpricealgorithmforbalancingtwosidedassemblylineswithzoningconstraints AT julienhohenstein branchandpricealgorithmforbalancingtwosidedassemblylineswithzoningconstraints |