# Solution Merging in Matheuristics for Resource Constrained Job Scheduling
## 3 Methods
### Parallel Ant Colony Optimisation  
An ACO model for the RCJS was originally proposed by [27]. This approach was extended to a parallel method in a multi-core shared memory architecture by [29]. For the sake of completeness, the details of the ACO implementation are provided here. As in the case of the constructive heuristic, a solution in the ACO model is represented by a permutation of all tasks (\(\pi\)). This is because there are potentially too many parameters if the ACO model is defined to explicitly learn the finishing times of the tasks. Given a permutation, a serial scheduling heuristic (see [35]) can be used to generate a resource and precedence feasible schedule consisting of finishing times for all tasks in a well-defined way. This is described in Section 3.3.1,  
Figure 4: This example considers the same toy instance, as in Figure 2, in which three jobs have to execute on three machines. The variable values (with respect to Model 1) are indicated for the same three solutions as those displayed in Figure 2.  
below. Moreover, based on the finishing times, the MS/CMSA solutions can be derived. The objective function value of an ACO solution \(\pi\) is denoted by \(f(\pi)\). The pheromone model of our ACO approach is similar to that used by [36]--that is, the set of pheromone values (\(\Phi\)) consist of values \(\tau_{ij}\) that represent the desirability of selecting job \(j\) for position \(i\) in the permutations to be built. Ant colony system (ACS) [37] is the specific ACO-variant that was implemented. The ACO algorithm is shown in Algorithm 3. An instance of the problem and the set of pheromone values \(\Phi\) are provided as input. Additionally, a solution (\(\pi^{bs}\)) can be provided as an input which serves the purpose of initially guiding the search towards this solution. If no solution is provided, \(\pi^{bs}\) is initialised to be an empty solution. ```
1:input: An RCJS instance, \(\Phi\), \(\pi^{bs}\) (optional)
2: Initialise \(\pi^{bs}\) (if given as input, otherwise not)
3:while termination conditions not satisfied do
4:for\(j=1\) to \(n_{ants}\)do\(\pi^{j}:=\text{ConstructSolution}(\Phi)\)
5:\(\pi^{ib}:=\text{arg}\min_{j=1\ldots n_{ants}}f(\pi^{j})\)
6:\(\pi^{ib}:=\text{Improve}(\pi^{ib})\)
7:\(\pi^{bs}:=\text{Update}(\pi^{ib})\)
8:\(\text{PheromoneUpdate}(\Phi\), \(\pi^{bs})\)
9:endwhile
10:output: \(\pi^{bs}\) (converted into a MS/CMSA solution)
```  
**Algorithm 3** ACO for the RCJS problem. The main loop of the algorithm at Lines 3-9 runs until a time or iteration limit is exceeded. Within the main loop, a number of solutions (\(n_{\text{ants}}\)) are constructed (\(\text{ConstructSolution}(\Phi)\)). Hereby, a permutation \(\pi\) is built incrementally from left to right by selecting, at each step, a task for the current position \(i=1,\ldots,n\), making use of the pheromone values. Henceforth, \(\hat{\mathcal{J}}\) denotes the tasks that can be chosen for position \(i\)--that is, \(\hat{\mathcal{J}}\) consists of all tasks not assigned already to an earlier position of \(\pi\). In ACS, a task is selected in one of two ways. A random number \(q\in(0,1]\) is generated and a task is selected deterministically if \(q<q_{0}\). That is, task \(k\) is chosen for position \(i\) of \(\pi\) using  
\[k=\underset{j\in\mathcal{J}}{\operatorname{argmax}}\,\tau_{ij}\enspace. \tag{24}\]  
Otherwise, a probabilistic selection is used where job \(k\) is selected according to  
\[P(\pi_{i}=k)=\frac{\tau_{ik}}{\sum_{j\in\mathcal{J}}\,\tau_{ij}}\enspace. \tag{25}\]  
Every time a job \(k\) is selected at position \(i\), a local pheromone update is applied:  
\[\tau_{ik}\leftarrow\max((1.0-\rho)\times\tau_{ik},\tau_{min})\enspace, \tag{26}\]  
where \(\tau_{min}=0.001\) is a small value that ensures that a job \(k\) may always be selected for position \(i\). After the construction of \(n_{\text{ants}}\) solutions, the iteration-best solution \(\pi^{ib}\) is determined (Line 5). This solution is improved by way of local search (\(\text{Improve}(\pi^{ib})\)), as discussed in [29].