# A Parallel Algorithm for Scheduling a Two-Machine Robotic Cell in Bicycle Frame Welding Process
## 6 Parallel Algorithm
### Algorithm Description  
The algorithm is based on the sequential method proposed in [12] and is designed for computing machines with large number of processors and a shared memory that can be used for communication (e.g., GPUs). The pseudocode for the algorithm is presented in Algorithm 1. In stage 1, the graph \(\mathcal{A}\) is build in parallel. The procedure starts with calculating prefix sums to accelerate the computations later. In lines 1-3, setup times and processing times are copied to arrays S and P. Then, in lines 4-5, prefix sums are computed  
\[\texttt{P}[a,i]=\sum_{k=1}^{i}p_{k}^{a},\qquad\texttt{S}[a,i]=\sum_{k=1}^{i}s _{k-1,k}^{a}, \tag{21}\]  
Figure 3: An example of a highlighted path (marked in red) for CAP instance with \(n=6\) and \(m=2\); the path corresponds to \(P=(2,1,1,2,1,2)\). for \(a\in\mathcal{M}\) and \(i\in\{1,2,\ldots,2n\}\) (note the indexes up to \(2n\)). Prefix sums are used to calculate the weights of the graph \(\mathcal{A}\), in lines 7-11. The weights are stored in a 4-dimensional array D, such that for any arc \(\big{(}(i,a),(j,b)\big{)}\in E\),  
\[\texttt{D}[i,a,j,b] =d\big{(}\big{(}(i,a),\ (j,b)\big{)}\big{)}\] \[=p_{i}^{a}+s_{i,j+1}^{a}+\sum_{k=i+1}^{j-1}\big{(}p_{k}^{b}+s_{k,k +1}^{b}\big{)}.\] \[=p_{i}^{a}+s_{i,j+1}^{a}+\sum_{k=1}^{j-1}p_{k}^{b}-\sum_{k=1}^{i}p _{k}^{b}+\sum_{k=1}^{j-1}s_{k,k+1}^{b}-\sum_{k=1}^{i}s_{k,k+1}^{b}\] \[=p_{i}^{a}+s_{i,j+1}^{a}+\texttt{P}[b,j-1]-\texttt{P}[b,i]+ \texttt{S}[b,j]-\texttt{S}[b,i+1]. \tag{22}\]  
For any combination of indexes \(i,j,a,b\), not representing a valid arc, an infinity is written into the array. Stage 1 is concluded, and the graph \(\mathcal{A}\) is constructed, with its arcs represented in the array D.  
```
input : CAP instance with \(n\) jobs and \(m=2\) machines output : Optimal assignment \(P^{*}\) /* Stage 1: Build the graph \(\mathcal{A}\). */
1 parfor\(i=1,2,\ldots,2n\); \(a=1,2\)do
2\(\texttt{S}[a,i]\gets s_{i-1}^{a}\);
3\(\texttt{P}[a,i]\gets p_{i}^{a}\);
4 parfor\(a=1,2\)do
5 PrefixSum(S\([a,\ldots]\));
6 PrefixSum(P\([a,\ldots]\));
7
8 parfor\(i,j=1,2,\ldots,2n\); \(a,b=1,2\)do
9 if\((i\leq n\ \land\ i<j<i+n\ \land\ b\
eq a)\lor(a=b\ \land\ i=n\ \land\ j=2n)\)then
10\(\texttt{D}[i,a,j,b]\gets p_{i}^{a}+s_{i,j+1}^{a}+\texttt{P}[b,j-1]- \texttt{P}[b,i]+\texttt{S}[b,j]-\texttt{S}[b,i+1]\);
11
12 else
13\(\texttt{D}[i,a,j,b]\leftarrow\infty\);
14
15
16 /* Stage 2: Find a highlighted path with lowest weight. */
17 SolveAPSP(D);
18 Find such \(i\in\mathcal{J}\), \(a\in\mathcal{M}\), that \(\texttt{D}[i,a,i+n,a]\) is minimal;
19 Build path with lowest weight \(\mu\), from \((i,a)\) to \((i+n,a)\); /* Stage 3: Build an optimal assignment. */
20\(P^{*}\leftarrow\texttt{PathToAssignment}(n,\mu)\);
21 return\(P^{*}\)
```  
**Algorithm 1**Parallel exact algorithm for CAP  
The goal of stage 2 is to compute a highlighted path with the lowest weight. For this purpose, APSP is solved in line 12 (by a chosen algorithm) in the graph \(G=(V,E_{g})\), described by D. This graph has the same set of nodes as \(\mathcal{A}\), however it is fully connected (a complete digraph). Graph \(G\) is analogous to \(\mathcal{A}\), however non-existent arcs from \(\mathcal{A}\) are represented by arcs with infinite weights:  
\[d\big{(}((i,a),\ (j,b))\big{)}=\texttt{D}[i,a,j,b],\quad\text{for: }\big{(}(i,a),(j,b)\big{)}\in E_{g}. \tag{23}\]  
It is assumed, that APSP solving algorithm writes distances between nodes into D. Then, in line 13, a pair of nodes constituting a start and end of a highlighted path with lowest weight is computed. Finally, in line 14, the path is constructed. The exact method is derived from the APSP algorithm used. Stage 3 of the algorithm transforms the highlighted path found in stage 2, into the optimal assignment. For the ease of presentation, the method is summarized in a separate pseudocode, in Algorithm 2.