# Solution Merging in Matheuristics for Resource Constrained Job Scheduling
## 2 Resource Constrained Job Scheduling
### Network Design Formulation  
This problem can be thought of as a network design problem to create a directed, acyclic graph representing a partial ordering of the job start times (see Figure 1). Here, node \(0\) represents the start of the schedule. For any pair of jobs \(i\to j\) that have a precedence there is an arc with duration \(p_{i}\) separating the start time of the two jobs. Additionally, for any job \(i\) that has a release time which is not already implied by the precedence relationships, the graph contains arcs \(0\to i\) of duration \(r_{i}\). To capture the tardiness we also introduce an additional dummy node \(i^{\prime}\) for each \(i\in\mathcal{J}\).  
The problem can now be formulated as follows using variables \(s_{i}\) to denote the start time of node (job) \(i\) with \(u_{i}\), the completion time or due date for job \(i\) (this associated with the dummy node \(i^{\prime}\)). Finally the binary variables \(y_{ij}\) are one if arc \(i\to j\) is to be added to the graph. Using these variables we can write the network design problem:  
Figure 1: The precedence graph of an instance of the RCJS problem.  
\[\min\ \sum_{i\in\mathcal{J}}w_{i}(u_{i}-d_{i})-(\sum_{i\in I}w_{i})s_{0} \tag{2}\] \[s.t. s_{i}-s_{0}\geq r_{i} \forall\ i\in\mathcal{J}\] (3) \[u_{i}-s_{i}\geq p_{i} \forall\ i\in\mathcal{J}\] (4) \[u_{i}-s_{0}\geq d_{i} \forall\ i\in\mathcal{J}\] (5) \[s_{j}-s_{i}\geq p_{i}y_{ij}-M(1-y_{ij}) \forall\ i,j\in\mathcal{J}:i\
ot\to j\] (6) \[y_{ij}=1 \forall\ i,j\in\mathcal{J}:i\to j\] (7) \[y_{ij}+y_{ji}=1 \forall\ i,j\in\mathcal{J}:m_{i}=m_{j}\] (8) \[y_{ij}+y_{ji}\leq 1 \forall\ i,j\in\mathcal{J}:m_{i}\
ot=m_{j}\] (9) \[\sum_{i\in K}\sum_{j\in\mathcal{K}\setminus\{i\}}y_{ij}\geq 1 \forall\ K\in\mathcal{K}\] (10) \[y_{ij}\in\{0,1\} \forall\ i,j\in\mathcal{J}.\]  
Here \(\mathcal{K}\) is the set of all minimal cliques \(K\) in the complement of the precedence graph (that is collection of jobs that do not have a given precedence relationship) such that each of the jobs belongs to a different machine and \(\sum_{i\in K}\mathcal{S}_{i}>\mathcal{G}\). It should be noted that constraints (3)-(5), which capture the release times, processing time and due date requirement, all have the same form of difference between two variables greater than a constant. The same also applies for (6) for fixed values of the \(y\) variables. Hence, for given \(y\) variables, this is simply the dual of a network flow problem. This means that, for integer data, the optimal times \(u_{i}\) and \(s_{i}\) will all be integers. Note that the objective (2) includes a constant term (\(\sum_{i}w_{i}d_{i}\)) and has the variable \(s_{0}\) with a constant, such that adding a constant to all of the \(s\) and \(u\) variables does not change the objective. (Without this the problem would be unbounded). Alternatively we could arbitrarily fix \(s_{0}=0\). Constraints (7) fix in the given precedence arcs of the network. The remaining constraints on \(y\) variables relate to the network design part of the problem. Constraints (8) and (9) enforce a total ordering of jobs on the same machine and a partial ordering amongst the remaining jobs, respectively. Finally, (10) prevents more jobs from running simultaneously (without an ordering) than can be accommodated within the resource limit.  
This formulation, while illustrating the network design nature of the problem, suffers from somewhat poor computational performance. While (10) includes a lot of constraints, these can be added as lazy constraints. However the main problem is due to the \"big-M\" constraints (6), which are very weak. To make this problem more computationally tractable, we will look at time discretization-based formulations next.