# Solution Merging in Matheuristics for Resource Constrained Job Scheduling
## 3 Methods
### Construct, Solve, Merge and Adapt  
Algorithm 2 presents the pseudo-code of the CMSA heuristic for the RCJS problem. The inputs to the algorithms are (1) an RCJS problem instance, (2) the number of solutions constructed per iteration (\(n_{s}\)), (3) the total computational (wall-clock) time (\(t_{\text{total}}\)), (4) the wall-clock time limit of the MIP-solver at each iteration (\(t_{\text{iter}}\)), and (5) the maximum age limit (\(a_{\max}\)). The algorithm maintains a set of variables, \(V^{\prime}\), which is a subset of the total set of variables in the MIP model, denoted by \(V\). In contrast to MS, CMSA uses Model 1 for the restricted MIP solved at each iteration. In the context of CMSA, a valid solution \(S\) to the RCJS problem is a subset of \(V\)--that is, \(S\subseteq V\). The corresponding solution is obtained by assigning the value 1 to all variables in \(S\) and 0 to all variables in \(V\setminus S\). Again, \(f(S)\) represents the objective function value of solution \(S\).  
```
1:input: An RCJS instance, \(n_{s}\), \(t_{\text{total}}\), \(t_{\text{iter}}\), \(a_{\max}\)
2:Initialisation: \(V^{\prime}:=\emptyset\), \(S^{bs}:=\emptyset\), \(a_{jt}:=0\)\(\forall\)\(x_{jt}\in V\)
3:while time limit \(t_{\text{total}}\) not expired do
4:for\(i=1,2,\ldots,n_{s}\)do# note that this is done in parallel
5:\(S_{i}:=\mathsf{GenerateSolution()}\)
6:\(V^{\prime}:=V^{\prime}\cup\{S_{i}\}\)
7:endfor
8:\(S^{ib}\leftarrow\mathsf{Apply\_MIP\_Solver}(V^{\prime},S^{bs},t_{iter})\)
9:if\(f(S^{ib})<f(S^{bs})\)then\(S^{bs}:=S^{ib}\)end if
10:\(\mathsf{Adapt}(V^{\prime},S^{bs},a_{max})\)
11:endwhile
12:OUTPUT:\(S^{bs}\)
```  
**Algorithm 2** CMSA for the RCJS problem.  
The algorithm starts by initialising relevant variables and parameters: (1) \(V^{\prime}:=\emptyset\), where \(V^{\prime}\) is the subset of variables that should be considered by the restricted MIP, (2) \(S^{bs}:=\emptyset\)--that is, no best-so-far solution exists, (3) \(a_{jt}:=0\)\(\forall\)\(x_{jt}\in V\), where \(a_{jt}\) is the so-called age value of variable \(x_{jt}\). With this last action, all age values are initialized to zero.  
Between Lines 3 and 11, the main algorithm executes. The algorithm runs up to a time limit and, as mentioned earlier, this is one hour of wall-clock time. As in MS, \(n_{s}\) solutions are constructed at each iteration. Remember that the variables contained in a solution \(S\) indicate the completion times of every job. As specified earlier, for the purpose of this study, we investigate a constructive heuristic and ACO. Each solution that is found is incorporated in \(V^{\prime}\) (Line 6) by setting a flag for the associated variables to be free when solving the restricted MIP in function \(\mathsf{Apply\_MIP\_Solver}(V^{\prime},S^{bs},t_{iter})\) (Line 8). In other words, the restricted MIP is obtained from the original/complete one by only allowing the variables from \(V^{\prime}\) to take on the value 1. As in the case of MS, solving the restricted MIP is warm-started with the best-so-far solution \(S^{bs}\) (if any). The restricted MIP is solved with a time limit of \(t_{iter}\) seconds and returns a possibly improved solution \(S^{ib}\). Note that this solution is at least as good as the original seed solution. In Line 9, a solution improving on \(S^{bs}\) is accepted as the new best-so-far solution. In \(\mathsf{Adapt}\)\((V^{\prime},S^{bs},a_{max})\), the age parameter of all variables is incremented, except for those that appear in \(S^{bs}\). If a variable's age has exceeded \(a_{max}\), it is removed from \(V^{\prime}\). Moreover, its age value is set back to zero after terminating, the best-so-far solution found is output by the algorithm.