# A Parallel Algorithm for Scheduling a Two-Machine Robotic Cell in Bicycle Frame Welding Process
## 8 Concluding Remarks  
The paper considered Cyclic Assignment Problem (CAP) in a two machine robotic cell, the problem inspired by a bicycle frame welding station. Two solving methods were introduced: One based on a Mixed Integer Linear Programming (MILP) model and a dedicated parallel algorithm. The algorithm was designed to benefit from a large number of processors, available, e.g. in modern GPUs. The proposed method efficiently transforms CAP into All Pairs Shortest Path (APSP) problem, allowing the user to utilize a vast literature on shortest path problems. The algorithm was analyzed theoretically, showing the computational complexity of up to \(O(\log n+T_{\text{APSP}})\), where \(n\) is the size of the problem and \(T_{\text{APSP}}\) is the computational complexity of the APSP solving method used. For a well-known, parallel APSP solving algorithm, the overall computational complexity of the proposed algorithm is \(O(\log^{2}n)\) on \(n^{3}\)-processor Exclusive Read Exclusive Write Parallel Random-Access Machine (EREW PRAM).  
The computational experiments shown CAP to be relatively hard for the solver-based approach. MILP formulation, solved by Gurobi Optimizer, performed much worse than the dedicated methods. The solver was unable to find any optimal solutions for instances with \(n\geq 128\) jobs in 2 h, while the dedicated algorithms solved the instances with \(n=128\) in milliseconds. For the smaller instances, the solver was from \(10^{4}\) to \(10^{7}\) times slower on  
Figure 5: Computation time required to solve CAP instances using different algorithms.  
Figure 6: Speedup of the parallel algorithm executed on GPU, in relation to the sequential algorithm executed on a single CPU thread.  
average than the sequential algorithm. The proposed parallel algorithm executed on a Graphics Processing Unit (GPU) was shown to achieve up to 314 speedup, compared to a sequential, state of art algorithm executed on CPU. The new method scheduled instances consisting of 8192 jobs in under 18 s and can be used both to solve larger instances and to shorten the computations for medium-sized ones. In practice, it allows to quickly re-assign the machines on the fly, when the demand changes. Alternatively, when the order of jobs is also to be determined, more potential orders can be evaluated by quickly finding the optimal assignments for each one (e.g., within a two-level metaheuristics described in Section 1).  
A promising direction for future work is to address robotic cells with more than \(m=2\) machines. While a very large \(m\) might be unrealistic (only a single machine processes jobs at any time; the remaining ones are idle), a moderate values \(2<m<11\) can model various specialized pieces of equipment available at the workstation. Another interesting direction is to research compound problems, where CAP is a part of a larger production environment, similar to the one considered in [12].  
Conceptualization, A.G. and T.N.; formal analysis: A.G.; methodology, A.G.; software, A.G. and T.N.; validation, A.G.; investigation, A.G.; resources, A.G. and T.N.; data curation, A.G. and T.N.; writing--original draft preparation, A.G. and T.N.; writing--review and editing, A.G. and T.N.; visualization, A.G.; supervision, A.G.; funding acquisition, T.N. Both authors have read and agreed to the published version of the manuscript.  
The paper was partially supported by the National Science Centre of Poland, grant OPUS No. 2017/25/B/ST7/02181.  
Not applicable.  
The data presented in this study are available on request from the corresponding author.  
The authors declare no conflict of interest.