# Solution Merging in Matheuristics for Resource Constrained Job Scheduling
## 3 Methods
### Merge Search  
Algorithm 1 presents an implementation of MS for the resource constrained job scheduling (RCJS) problem. The algorithm has five input parameters, which are (1) an RCJS problem instance, (2) the number of solutions (\(n_{s}\)), (3) the total computational (wall-clock) time (\(t_{\text{total}}\)), (4) the wall-clock time limit of the mixed integer programming (MIP) solver at each iteration (\(t_{\text{iter}}\)), and (5) the number of random subsets generated from a set of variables (\(K\)). Note that our implementation of MS is based on the MIP model from Section 2.4--that is, on Model 2. The reasons for that will be outlined below. In the following section, \(V\) denotes the set of variables of the complete MIP model--that is, \(V:=\{z_{jl}\mid j=1,\ldots,n\,t\in\mathcal{T}\}\). Moreover, in the context of MS, a valid solution \(S\) to the RCJS problem consists of a value for each variable from \(S\) (such that all constraints are fulfilled). In particular, the value of a variable \(z_{jl}\) in a solution \(S\) is henceforth denoted by \(S_{jl}\). The objective function value of solution \(S\) is denoted by \(f(S)\). ```
1:input: RCJS instance, \(n_{s}\), \(t_{total}\), \(t_{iter}\), \(K\)
2:Initialisation: \(S^{bs}:=\textsc{null}\)
3:while time limit \(t_{\text{total}}\) not expired do
4:if\(S^{bs}\
eq\textsc{null}\)then\(\mathcal{S}:=\{S^{bs}\}\) else\(\mathcal{S}:=\emptyset\) endif
5:for\(i=1,2,\ldots,n_{s}\)do # note that this is done in parallel
6:\(S:=\textsf{GenerateSolution}(S^{bs})\)
7:\(\mathcal{S}\leftarrow\mathcal{S}\cup S\)
8:endfor
9:\(\mathcal{P}:=\textsf{Partition}(\mathcal{S})\)
10:\(\mathcal{P}^{\prime}:=\textsf{RandomSplit}(\mathcal{P},\ K)\)
11:\(S^{ib}:=\textsf{Apply\_MIP\_Solver}(\mathcal{P}^{\prime},S^{bs},t_{iter})\)
12:if\(S^{bs}=\textsc{null}\)or\(f(S^{ib})<f(S^{bs})\)then\(S^{bs}:=S^{ib}\) endif
13:endwhile
14:OUTPUT:\(S^{bs}\)
```  
**Algorithm 1** MS for RCJS. First, the algorithm initialises the best-so-far solution to null--that is, \(S^{bs}:=\textsc{null}\). The main loop of the algorithm executes between Lines 3-12 until a terminating criteria is attained. For the experiments in this study, we impose a time limit of one hour of wall-clock time. A number of feasible solutions (\(n_{s}\)) is constructed between Lines 5 and 8 and all solutions found are added to the solution set \(\mathcal{S}\), which only contains the best-so-far solution \(S^{bs}\) at the start of each iteration (if \(S^{bs}\
eq\textsc{null}\)). In this study, we consider two methods of generating solutions: (1) a constructive heuristic and (2) ACO. The details of both methods are provided in the subsequent sections. Additionally, in both methods, the \(n_{s}\) solutions are constructed in parallel, leading to a very quick solution generating procedure. In the case of ACO, \(n_{s}\) threads execute \(n_{s}\) independent of ACO colonies, leading to \(n_{s}\) independent solutions (see Section 3.3 for full details). The variables from \(V\) are then partitioned on the basis of the solutions in \(\mathcal{S}\). In particular, a partition \(\mathcal{P}=\{P_{1},\ldots,P_{p}\}\) is generated, such that:  
1. \(P_{i}\cap P_{j}=\emptyset\) for all \(P_{i},P_{j}\in\mathcal{P}\). 2. \(\bigcup_{i=1}^{p}P_{i}=V\). 3. \(S_{jt}=S_{rt}\), \(\forall\,S\in\mathcal{S}\), \(\forall\,z_{jt},z_{rt}\in P_{i}\), \(\forall\,P_{i}\in\mathcal{P}\). That is, for each solution \(S\in\mathcal{S}\), the values of all the variables in each partition of \(\mathcal{P}\) have the same value. Partition \(\mathcal{P}\) is generated in function \(\mathsf{Partition}(\mathcal{S})\) (see Line 9 of Algorithm 1). Depending on the solutions in \(\mathcal{S}\), the number of the partitions in \(\mathcal{P}\) can vary greatly. For example, a large number of similar solutions will lead to very few partitions. Hence, an additional step is used in function \(\mathsf{RandomSplit}\) (\(\mathcal{P}\), \(K\)) to (potentially) augment the number of partitions depending on parameter \(K\).