# A Parallel Algorithm for Scheduling a Two-Machine Robotic Cell in Bicycle Frame Welding Process
## 5 Sequential Algorithm
### Graph Model  
A graph model for a two-machine CAP was first introduced and analyzed in [12], where it was used to build the exact solving algorithm. For the completeness, the model is summarized below. Note that \(m=2\) is assumed.  
Let \(\mathcal{A}=(V,E)\) be a directed graph, where \(V=\mathcal{W}\cup\mathcal{W}^{\prime}\) is a set of nodes and \(E=\mathcal{E}\cup\mathcal{E}^{\prime}\cup\mathcal{E}^{\prime\prime}\) is a set of arcs, where:\[\mathcal{W} =\bigcup_{i\in\mathcal{M}}\bigcup_{j=1}^{n}\{(j,i)\}, \mathcal{W}^{\prime} =\bigcup_{i\in\mathcal{M}}\bigcup_{j=n+1}^{2n}\{(j,i)\} \tag{15}\] \[\mathcal{E} =\bigcup_{a\in\mathcal{M}}\bigcup_{i=1}^{n-1}\bigcup_{j=i+1}^{n} \{((i,a),(j,\overline{a}))\}, \mathcal{E}^{\prime} =\bigcup_{a\in\mathcal{M}}\bigcup_{i=2}^{n}\bigcup_{j=n}^{n-1+1} \{((i,a),(j,\overline{a}))\},\] (16) \[\mathcal{E}^{\prime\prime} =\bigcup_{a\in\mathcal{M}}\{((n,a),(2n,a))\}, \overline{a} =\begin{cases}1&\text{if $a=2$,}\\ 2&\text{if $a=1$.}\end{cases} \tag{17}\]  
**Example 1**.: _Consider CAP instance with \(n=5\) and \(m=2\). The corresponding graph \(\mathcal{A}\) is shown in Figure 2. Arcs from the set \(\mathcal{E}\) are marked in black, arcs from the set \(\mathcal{E}^{\prime}\) are marked blue and arcs from the set \(\mathcal{E}^{\prime\prime}\) are marked red._  
Any node \((i,a)\in V\) represents a job \(i\) or \(i-n\) (depending on the cycle), performed on a machine \(a\). Arcs, on the other hand, represent sequences of jobs assigned to the same machine, preceded by a job assigned to a different machine. More precisely, any arc \(((i,a),\ (j,b))\in E\) corresponds to a sequence of assignments \(P(i)=a\), \(P(i+1)=b\),..., \(P(j-1)=b\), \(P(j)=b\), if \(i,j\leq n\). For \(j>n\), the indexes of assignments beyond \(n\) are reduced by \(n\) (refer to Example 2).  
Nodes are unweighted, while the weight of arcs reflect the duration of the jobs and setups they represent. To simplify the notation, the definition of job and setup durations is extended for all the indexes of nodes in \(\mathcal{A}\)  
\[s^{a}_{i,j} \coloneqq s^{a}_{((i-1)\bmod n)+1,\ ((j-1)\bmod n)+1} \text{for: }i,j>n,\ a\in\mathcal{M}, \tag{18}\] \[p^{a}_{i} \coloneqq p^{a}_{((i-1)\bmod n)+1} \text{for: }i>n,\ a\in\mathcal{M}. \tag{19}\]  
For example, if \(n=5\), then \(p^{1}_{11}=p^{1}_{1}\) and \(s^{a}_{2\to 6}=s^{a}_{2\to 1}\). With the extended indexing, the weights of arcs in \(\mathcal{A}\) are given by  
\[d\big{(}((i,a),\ (j,b))\big{)}=p^{a}_{i}+s^{a}_{i,j+1}+\sum_{k=i+1}^{j-1} \big{(}p^{b}_{k}+s^{b}_{k,k+1}\big{)}\quad\text{for: }((i,a),\ (j,b))\in E. \tag{20}\]  
**Definition 1**.: _Any path from \((i,a)\) to \((i+n,a)\) in graph \(\mathcal{A}\), for any \(a\in\mathcal{M}\), \(i\in\mathcal{J}\), is called a highlighted path. A set of all such paths is denoted by \(\mathcal{L}\)._  
Each highlighted path corresponds to exactly one assignment, and each assignment corresponds to exactly one highlighted path. An assignment corresponding to a given highlighted path can be constructed by transforming each arc in the path into its corresponding assignments (for a rigorous formula refer to [12]).  
Figure 2: Graph \(\mathcal{A}\) for CAP instance with \(n=5\) and \(m=2\).  
**Example 2**.: _Consider a CAP instance with \(n=6\) and \(m=2\). A graph \(\mathcal{A}\) build for this instance is shown on Figure 3. A highlighted path \(\left((1,2),(3,1),(4,2),(5,1),(7,2)\right)\), constructed for \(P=(2,1,1,2,1,2)\) is marked in red. Black dots represent job-machine assignments._  
**Theorem 1** ([12]).: _In graph \(\mathcal{A}\), the weight of highlighted path with the minimum weight is equal to the minimal cycle time._  
Based on Theorem 1, the highlighted paths can be used to find an optimal solution of CAP. Such method is described in the following subsection.