# A Parallel Algorithm for Scheduling a Two-Machine Robotic Cell in Bicycle Frame Welding Process
## 4 Mixed Integer Linear Formulation  
In this section, a first MILP-formulation for CAP is introduced. Solving methods for scheduling problems commonly utilize MILP (e.g., refer to the related work in Section 2); and as such--this approach can constitute a valid point of reference for the presented dedicated exact algorithm.  
The Equations (5), (6) and (8) define an objective function of CAP. They can be almost directly transformed into the following MILP formulation:  
\[\min_{\mathbf{x},\mathbf{s}}\sum_{a\in\mathcal{M}}\sum_{i\in\mathcal{J}}x_{i} ^{a}p_{i}^{a}+\sum_{i\in\mathcal{J}}\mathbf{s}_{i}, \tag{9}\]subject to:  
\[\forall i\in\mathcal{J}\quad\sum_{a\in\mathcal{M}}x_{i}^{a}=1, \tag{10}\] \[\forall a\in\mathcal{M}\;\;\forall i,j\in\mathcal{J},\,j<i\quad \mathbf{s}_{i}\geq s_{j\to i}^{a}-\underbrace{M(2-x_{i}^{a}-x_{j}^{a})}_{0\text { if }P(i)=P(j)=a}-\underbrace{M\sum_{d=j+1}^{i-1}x_{d}^{a}}_{0\text{ if }P(i)=P(j)=a}\] (11) \[\forall a\in\mathcal{M}\;\;\forall i,j\in\mathcal{J},\,j\geq i\quad \mathbf{s}_{i}\geq s_{j\to i}^{a}-\underbrace{M(2-x_{i}^{a}-x_{j}^{a})}_{1\text { if }P(i)=P(j)=a}-\underbrace{M\Bigl{(}\sum_{k=0}^{i-1}x_{k}^{a}+\sum_{k=j+1}^{a}x_{ k}^{a}\Bigr{)}}_{0\text{ if }P(\text{ proceeds }i}), \tag{12}\]  
where \(M\in\mathbb{R}^{+}\) is a large number and \(\mathbf{x}\in\mathbb{Z}^{m\times n}\) and \(\mathbf{s}\in\mathbb{R}^{n}\) are decision variables. \(\mathbf{x}\) encodes an assignment and for any \(a\in\mathcal{M}\) and \(i\in\mathcal{J}\),  
\[x_{i}^{a}=\begin{cases}1&\text{if job $i$ is assigned to machine $a$,}\\ 0&\text{otherwise.}\end{cases} \tag{13}\]  
On the other hand, \(\mathbf{s}\) encodes the duration of setups performed before the jobs, i.e., for any \(i\in\mathcal{J}\), \(\mathbf{s}_{i}=setup(P,i)\), where \(P\) must be consistent with \(\mathbf{x}\). Constraint (10) ensures each job is assigned to exactly one machine. Constraints (11) and (12) are used to compute setup times before the jobs. For any machine \(a\in\mathcal{M}\) and jobs \(i,j\in\mathcal{J}\), the right hand side of the constraints is a negative number, except if according to the current \(\mathbf{x}\), both job \(i\) and \(j\) are assigned to machine \(a\) and job \(j\) directly precedes \(i\) on \(a\). Then, right side is equal to \(s_{j\to i}^{a}\), thus ensuring the correct value of \(\mathbf{s}_{i}\). Resulting MILP model consists of \(2n\) binary and \(n\) continuous variables; and \(n^{2}+n\) constraints.  
When \(m=2\), the number of variables and constraints can be further reduced easily. Consider the assignment encoded in \(\mathbf{x}^{\prime}\in\mathbb{Z}^{n}\), with  
\[x_{i}^{\prime}=\begin{cases}0&\text{if job $i$ is assigned to machine $1$,}\\ 1&\text{if job $i$ is assigned to machine $2$.}\end{cases} \tag{14}\]  
Then, one can substitute \(\mathbf{x}_{i}^{1}\coloneqq-(\mathbf{x}_{i}^{\prime}-1)\) and \(\mathbf{x}_{i}^{2}\coloneqq\mathbf{x}_{i}^{\prime}\) in Equations (9), (11) and (12); then constrain \(\mathbf{x}^{\prime}\) to be a vector of binary variables, instead of using (10). Reformulated MILP model consists of \(n\) binary and \(n\) continuous variables; and \(n^{2}+n\) constraints (\(n\) constraints on \(\mathbf{x}^{\prime}\) being binary, i.e., \(n^{2}\) constraints and \(n\) bounds).