# A Parallel Algorithm for Scheduling a Two-Machine Robotic Cell in Bicycle Frame Welding Process
## 6 Parallel Algorithm
### Computational Complexity  
Algorithms are usually analyzed theoretically in the context of the so-called abstract machines. They are simplified models of computer systems (in particular, the hardware),  
Figure 4: Memory during computations in Algorithm 2 for \(n=20\) and \(\mathbf{\mu}=((5,2),(8,1),(19,2))\). that allow to predict various properties of the software executed on real machines [42], such as computation time or memory requirements. For the analysis, Parallel Random Access Machine (PRAM) [43; 44] model will be used, which is an extension of the sequential RAM model. The PRAM model is one of the most widely used models of parallel machines ([45], pp. 18-19), and has been the subject of numerous scientific publications (examples of which can be found in ([46], pp. 74-76)). In simple terms, the PRAM model assumes the existence of \(k\) processors having access to a shared memory of an unlimited size at a constant time. The processors have synchronized clocks, i.e., execute the instructions simultaneously, with each processor being allowed to execute a different instruction. The instructions are limited to read/write and simple local variable operations such as comparison or summation. Due to additional limitations related to the access to the shared memory, there are four general subclasses of PRAM models: EREW, CREW, ERCW and CRCW (in the abbreviations, \"E\" stands for exclusive, \"C\" for concurrent, \"R\" for read and \"W\" for write). In EREW PRAM, both read and write operations are exclusive, i.e., any memory cell can be accessed by a single processor at a time. The model is restrictive, but closely reassembles many hardware implementations. Another popular model is CREW PRAM, where concurrent read is allowed. CREW is a good approximation of systems where shared memory access is not a bottleneck. Note that any algorithm suitable for EREW, can also be executed on CREW. For that reason, EREW PRAM will be applied for the analysis whenever possible. **Lemma 1**. : _Consider a highlighted path in graph \(\mathcal{A}\), build for a CAP instance with \(n\) jobs and \(m=2\) machines. The corresponding assignment can be calculated in \(O(\log n)\) time on \(n\)-processor EREW PRAM._  
Proof. : The assignment corresponding to any highlighted path can be found using Algorithm 2, analyzed further for computational complexity on EREW PRAM. Assume there are \(n\) processors available. Broadcasting any scalar information from a single processor, to all processors can be performed in \(O(\log n)\) time (lines 3, 5). Then, a special case check in lines 2-4 can be performed in \(O(\log n)\) time. Operations in the main, parallel loop from lines 6-32 are designed to prevent conflicts in memory access. The synchronization is achieved by tuning the number of processor cycles for each branch in logic, which does not bring an additional overhead. Thus, operations in lines 7-20 take \(O(1)\) time on \(n\) processors (assuming \(\log_{2}n\) can be computed in constant time, otherwise the operation would have to be performed outside the parallel region). Loop from lines 21-32 has \(O(\log n)\) iterations, and each can be performed in constant time on each processor. As a result, the final computational complexity of the algorithm is in \(O(\log n)\) on \(n\)-processor EREW PRAM. **Theorem 2**. : _Consider a CAP instance with \(n\) jobs and \(m=2\) machines. The optimal solution for that instance can be found in_  
\[O\big{(}\log n+T_{\text{APSP}}\big{)}\]  
_time, on \(\max\{n^{2},P_{\text{APSP}}\}\)-processor EREW PRAM, where \(T_{\text{APSP}}\), \(P_{\text{APSP}}\) are time and number of processors required to solve APSP on the graph \(\mathcal{A}\) build for that instance._  
Proof. : The problem can be solved using Algorithm 1. The algorithm is divided into three stages. Stage one starts with calculating prefix sums. Write operations from lines 1-3 can be performed in \(O(\lceil n/k\rceil)\) time on \(k\) processors (assigning 8 write operations for each processor).