# A Parallel Algorithm for Scheduling a Two-Machine Robotic Cell in Bicycle Frame Welding Process
## 6 Parallel Algorithm
### Algorithm Description
```
1 PathToAssignment(\(n\), \(\boldsymbol{\mu}\))
2 input : Instance size \(n\), highlighted path \(\boldsymbol{\mu}\)
3 output : The assignment P, corresponding to the path \(\boldsymbol{\mu}\)
4 if\(|\boldsymbol{\mu}|=1\)then /* Single-machine assignment */
5 Broadcast \(\mu_{1}^{\text{mach}}\) to all elements of P;
6 return P
7 Broadcast \(n\) and \(|\boldsymbol{\mu}|\);
8 parfor\(p=1,2,\ldots,n\)do
9P[\(p\)] \(\leftarrow\) -1;
10 if\(p\leq|\boldsymbol{\mu}|\)then /* Initialize P */
11P[\(((\mu_{p}^{job}-1)\mod n)+1]\leftarrow\mu_{p}^{\text{mach}}\);
12 elseIddle;
13 Synchronize;
14T[\(p\)] \(\leftarrow\) -1 ; /* Initialize TO */
15 if\(p\leq|\boldsymbol{\mu}|\)then
16 if\(p\
eq 1\)then
17T[\(((\mu_{p}^{job}-1)\mod n)+1]\leftarrow\mu_{p-1}^{\text{mach}}\);
18 else
19T[\(((\mu_{p}^{job}-1)\mod n)+1]\leftarrow\mu_{|\boldsymbol{\mu}|}^{\text{mach}}\)
20 elseIddle;
21 Synchronize;
22 maxSteps \(\leftarrow\) \(\lceil\log_{2}n\rceil\);
23 for\(i=1,2,\ldots,\max\)Steps do
24 shift \(\gets 2^{i-1}\);
25 if\(\textbf{p}[p]\
eq-1\)then
26 index \(\gets\)\(p-\) shift;
27 if\(p-\) shift \(<1\)then
28 index \(\leftarrow\)\(n+\) index;
29 ifindex \(>\) T[\(p\)] then
30P[index] \(\leftarrow\) P[\(p\)];
31T[index] \(\leftarrow\) T[\(p\)];
32 elseIddle;
33 Synchronize;
34
35 return P
```  
**Algorithm 2**Building an assignment corresponding to a highlighted path  
The method is designed so that it can be performed on a machine where a concurrent memory access is impossible. First, in lines 2-4, a special case when all the jobs are assigned to the same machine is handled. Then, if it is not the case, basic information is broadcasted in parallel to each of \(n\) processors in line 5. The following code is performed on each processor separately. The Synchronize command indicates the place in the logic where the processors should synchronize the execution. It can be achieved, e.g., by placing Iddle commands so that each branch requires the same number of processor cycles. In lines 7-10, an array P is initialized. The array will contain the assignment constructed by the method. During the initialization, only the assignments directly contained in \(\boldsymbol{\mu}\) are written. Other elements of the array are filled with \(-1\). Similarly, an array TO is initialized in lines 12-18. The array contains information required to avoid conflicts during copying data into P.  
Each element of TO contains a left-side bound a certain assignment should be copied up to. In other words, ignoring edge cases, if \(\texttt{TO}[i]=j\), then jobs from \(j+1\) to \(i\) should be assigned to the machine \(\texttt{P}[i]\). The following part of the algorithm is divided into sequential steps, iterations of the loop in line 21. The number of steps is computed in line 20. In line 22, a shift is computed. The shift determines which element of P will be modified in a given step. Then, if a processor \(p\) is \"active\" (e.g., if \(\texttt{P}[p]\
eq-1\)) and left-side bound in TO is satisfied, a next value is written into P and TO. Each step of the algorithm is concluded by a synchronization. Refer to Example 3 for a step-by-step analysis of the contents of P and TO during a run of the algorithm. **Example 3**. : _Consider CAP instance with \(n=20\) and \(m=2\). Let \(\mathbf{\mu}=((5,2),(8,1),(19,2))\) be a highlighted path in the graph \(\mathcal{A}\), constructed for this instance. Figure 4 shows the memory during the construction of the assignment corresponding to \(\mathbf{\mu}\), using Algorithm 2. The first two rows represent the nodes of \(\mathbf{\mu}\). The following two rows represent the state of arrays P and TO after synchronization in line 19. Each of the following pairs of rows represent the state after synchronizations in line 35. Finally, the arrows on the figure represent the write operations performed by the processors in each iteration of loop in line 21._