# A Parallel Algorithm for Scheduling a Two-Machine Robotic Cell in Bicycle Frame Welding Process
###### Abstract  
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 \(O(\log^{2}n)\) on an \(n^{3}\)-processor Exclusive Read Exclusive Write Parallel Random-Access Machine (EREW PRAM), where \(n\) 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. robotic cell; cyclic production; flexible production; scheduling; parallel computing; frame welding; GPU +
Footnote †: : 2021: 11, 8083. [[https://doi.org/10.3390/app1178083](https://doi.org/10.3390/app1178083)]([https://doi.org/10.3390/app1178083](https://doi.org/10.3390/app1178083))  
Footnote †: 2021: 11, 8083. [[https://doi.org/10.3390/app11178083](https://doi.org/10.3390/app11178083)]([https://doi.org/10.3390/app11178083](https://doi.org/10.3390/app11178083))  
Footnote †: 2021: 11, 8083. This paper discusses the problem of assigning jobs to machines in a two-machine robotic cell, where the order of jobs is determined (Level 2). Prior to each job, a setup is performed, the length of which depends on the previous job performed on the machine. The problem is inspired by the frame welding in a bicycle factory located in Poland. The factory produces four types of aluminum bicycle frames: Mountain, trekking, city and children's. Moreover, some of the frames are produced in two variants--male and female. The lengths and diameters of the components additionally depend on the dimensions of the frame, which can be standardized or customized on request. The key production stage is welding the frame elements, which is done in a robotic cell (see Figure 1). The cell consists of a welding robot, two positioners and storage fields for product components and ready-made bicycle frames. The frame welding process consists of three stages:  
1. Move the frame elements from the storage field with kit containers and fix them in the positioner. The step is performed by a human operator, and--for safety reasons--with the robot disabled. 2. Perform the welding job by the robotic arm. The time required to complete the job depends on the type and the size of the frame and the parameters of the positioner used. Human operator cannot enter the cell. 3. Retrieve the finished frame and store it in a dedicated field. The step is performed by a human operator, and--for safety reasons--with the robot disabled. The unique feature of the considered problem is that both jobs and setups occupy the robotic cell exclusively (i.e., there is one operator--human or robotic). A batch of products (with a predefined mixture) is manufactured repeatedly, until the demand changes. The problem will be referred to as the Cyclic Assignment Problem (CAP). The CAP corresponds to the second level of the previously described hybrid metaheuristic schema. A sequential, exact algorithm for CAP was proposed in [12]. Unfortunately, despite the polynomial computational complexity, its execution time for CAP instances with a large number of jobs may be unacceptable in practice. Moreover, if the order of jobs also needs to be determined, a fast CAP solving algorithm could be used as a part of a two-stage metaheuristic. This paper presents a parallel exact algorithm designed to employ multi-processor environments, such as modern Graphic Processing Units (GPUs), drastically reducing the computation time required to solve larger problem instances. The main contributions can be summarized as follows:  
1.