# Solution Merging in Matheuristics for Resource Constrained Job Scheduling
## Appendix A Construction Heuristic  
Using a constructive heuristic (in a probabilistic way) is one of the options of generating solutions at each iteration. The constructive heuristic that we developed builds a sequence of all jobs from left to right. For that purpose it starts with an initially empty sequence \(\pi\). At each construction step it chooses exactly one of the so-far unscheduled jobs, and it appends this job to \(\pi\). Henceforth, let \(\mathcal{J}_{\pi}\subseteq\mathcal{J}\) be the set of jobs that are already scheduled with respect to a partial sequence \(\pi\). For the technical description of the heuristic, let \(\max_{t}:=\max_{j=1}^{n}r_{j}+\sum_{j=1}^{n}p_{j}\). Note that \(\max_{t}\) is a crude upper bound for the Makespan of any feasible solution. Moreover, let \(\mathcal{C}_{j}\) be the set of jobs that--according to the precedence constraints in \(\mathcal{C}\)--must be executed before \(j\), and let \(\mathcal{M}_{m_{h}}\subseteq\mathcal{J}\) be the subset of jobs that must be processed on machine \(m_{h}\), \(h=1,\ldots,l\). Furthermore, given a partial solution \(\pi\), let \(g_{\pi,t}\geq 0\) be the sum of the already consumed resource at time \(t\). Given a partial sequence \(\pi\), the set of feasible jobs--that is, the set of jobs from which the next job to be scheduled can be chosen--is defined as follows: \(\hat{\mathcal{J}}:=\{j\in\mathcal{J}\setminus\mathcal{J}_{\pi}\mid\mathcal{C} _{j}\cap\mathcal{J}_{\pi}=\mathcal{C}_{j}\}\). In words, the set of feasible jobs consists of those jobs that (1) are not scheduled yet and (2) whose predecessors with respect to \(\mathcal{P}\) are already scheduled. A time step \(t^{\prime}\geq 0\) is a feasible starting time for a job \(j\in\hat{\mathcal{J}}\), if and only if  
1. \(t^{\prime}\geq s_{k}+p_{k}\), for all \(k\in\mathcal{J}_{\pi}\ \cap C_{j}\);
2. \(t^{\prime}\geq s_{k}+p_{k}\), for all \(k\in\mathcal{M}_{m_{j}}\cap\mathcal{J}_{\pi}\) (remember that \(m_{j}\) refers to the machine on which job \(j\) must be processed);
3. \(g_{\pi,t}+g_{j}\leq\mathcal{G}\), for all \(t=t^{\prime},\ldots,t^{\prime}+p_{j}\). Here, \(T^{\prime}\) is the set of feasible starting times for a job \(j\in\hat{\mathcal{J}}\) and the earliest starting time \(s_{j}\) is defined as \(s_{j}:=\min\{t^{\prime}\mid t^{\prime}\in T^{\prime}\}\). Finally, for choosing a feasible job at each construction step, the jobs from \(j\in\hat{\mathcal{J}}\) are ordered in the following way. First, a job \(j\) has priority over a job \(k\), if \(s_{j}<s_{k}\). In the case of a tie, job \(j\) has priority over job \(k\) if \(w_{j}>w_{k}\). Finally, in the case of a further tie, job \(j\) has priority over job \(k\) if \(d_{j}<d_{k}\). If there is still a tie, the order between \(j\) and \(k\) is randomly chosen. The jobs from \(\hat{\mathcal{J}}\) are ordered in this way, and this job order is stored in sequence \(\pi^{\prime}\). The first job in \(\pi^{\prime}\) is then chosen to be scheduled next. A pseudo-code of the heuristic is provided in Algorithm 1. Finally, note that a solution constructed by the heuristic can be easily transformed into a Merge search (MS) (respectively, construct, merge, solve and adapt (CMSA)) solution. This is because the heuristic derives starting times for all jobs. The finishing time of each job is calculated by addingits processing time to its starting time. The corresponding variable values of both mixed integer programming (MIP) models can then be derived on the basis of the finishing times. This heuristic is used in a probabilistic way, as follows. Instead of choosing, at each construction step, the first job from \(\pi^{\prime}\) and appending it to \(\pi\), the following procedure is applied. First, a random number \(r\in[0,1]\) is produced. If \(r\leq d_{\text{rate}}\), the first job from \(\pi^{\prime}\) is chosen and appended to \(\pi\). Hereby, \(d_{\text{rate}}\) is a parameter which we set to value \(Y\) for all experiments.