A Parallel Algorithm for Scheduling a Two-Machine Robotic Cell in Bicycle Frame Welding Process
Welding frames with differing geometries is one of the most crucial stages in the production of high-end bicycles. This paper proposes a parallel algorithm and a mixed integer linear programming formulation for scheduling a two-machine robotic welding station. The time complexity of the introduced p...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-08-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/11/17/8083 |
| _version_ | 1797521636268703744 |
|---|---|
| author | Andrzej Gnatowski Teodor Niżyński |
| author_facet | Andrzej Gnatowski Teodor Niżyński |
| author_sort | Andrzej Gnatowski |
| collection | DOAJ |
| description | Welding frames with differing geometries is one of the most crucial stages in the production of high-end bicycles. This paper proposes a parallel algorithm and a mixed integer linear programming formulation for scheduling a two-machine robotic welding station. The time complexity of the introduced parallel method is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><msup><mo form="prefix">log</mo><mn>2</mn></msup><mi>n</mi><mo>)</mo></mrow></semantics></math></inline-formula> on an <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mi>n</mi><mn>3</mn></msup></semantics></math></inline-formula>-processor Exclusive Read Exclusive Write Parallel Random-Access Machine (EREW PRAM), where <i>n</i> is the problem size. The algorithm is designed to take advantage of modern graphics cards to significantly accelerate the computations. To present the benefits of the parallelization, the algorithm is compared to the state of art sequential method and a solver-based approach. Experimental results show an impressive speedup for larger problem instances—up to 314 on a single Graphics Processing Unit (GPU), compared to a single-threaded CPU execution of the sequential algorithm. |
| first_indexed | 2024-03-10T08:15:21Z |
| format | Article |
| id | doaj.art-1d059547bfce453ab20877fe5583836f |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-10T08:15:21Z |
| publishDate | 2021-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-1d059547bfce453ab20877fe5583836f2023-11-22T10:21:15ZengMDPI AGApplied Sciences2076-34172021-08-011117808310.3390/app11178083A Parallel Algorithm for Scheduling a Two-Machine Robotic Cell in Bicycle Frame Welding ProcessAndrzej Gnatowski0Teodor Niżyński1Department of Control Systems and Mechatronics, Wrocław University of Science and Technology, 50-370 Wrocław, PolandDepartment of Control Systems and Mechatronics, Wrocław University of Science and Technology, 50-370 Wrocław, PolandWelding frames with differing geometries is one of the most crucial stages in the production of high-end bicycles. This paper proposes a parallel algorithm and a mixed integer linear programming formulation for scheduling a two-machine robotic welding station. The time complexity of the introduced parallel method is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><msup><mo form="prefix">log</mo><mn>2</mn></msup><mi>n</mi><mo>)</mo></mrow></semantics></math></inline-formula> on an <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mi>n</mi><mn>3</mn></msup></semantics></math></inline-formula>-processor Exclusive Read Exclusive Write Parallel Random-Access Machine (EREW PRAM), where <i>n</i> is the problem size. The algorithm is designed to take advantage of modern graphics cards to significantly accelerate the computations. To present the benefits of the parallelization, the algorithm is compared to the state of art sequential method and a solver-based approach. Experimental results show an impressive speedup for larger problem instances—up to 314 on a single Graphics Processing Unit (GPU), compared to a single-threaded CPU execution of the sequential algorithm.https://www.mdpi.com/2076-3417/11/17/8083robotic cellcyclic productionflexible productionschedulingparallel computingframe welding |
| spellingShingle | Andrzej Gnatowski Teodor Niżyński A Parallel Algorithm for Scheduling a Two-Machine Robotic Cell in Bicycle Frame Welding Process Applied Sciences robotic cell cyclic production flexible production scheduling parallel computing frame welding |
| title | A Parallel Algorithm for Scheduling a Two-Machine Robotic Cell in Bicycle Frame Welding Process |
| title_full | A Parallel Algorithm for Scheduling a Two-Machine Robotic Cell in Bicycle Frame Welding Process |
| title_fullStr | A Parallel Algorithm for Scheduling a Two-Machine Robotic Cell in Bicycle Frame Welding Process |
| title_full_unstemmed | A Parallel Algorithm for Scheduling a Two-Machine Robotic Cell in Bicycle Frame Welding Process |
| title_short | A Parallel Algorithm for Scheduling a Two-Machine Robotic Cell in Bicycle Frame Welding Process |
| title_sort | parallel algorithm for scheduling a two machine robotic cell in bicycle frame welding process |
| topic | robotic cell cyclic production flexible production scheduling parallel computing frame welding |
| url | https://www.mdpi.com/2076-3417/11/17/8083 |
| work_keys_str_mv | AT andrzejgnatowski aparallelalgorithmforschedulingatwomachineroboticcellinbicycleframeweldingprocess AT teodornizynski aparallelalgorithmforschedulingatwomachineroboticcellinbicycleframeweldingprocess AT andrzejgnatowski parallelalgorithmforschedulingatwomachineroboticcellinbicycleframeweldingprocess AT teodornizynski parallelalgorithmforschedulingatwomachineroboticcellinbicycleframeweldingprocess |