## 3 Resolution Approaches
### Approximate Approaches
#### 3.2.3 Simulated Annealing
In our case, generating a neighbor of \(S^{\prime}\) consists of applying, with equal probability, one of the following operators:

* Swap two randomly selected jobs in \(ordj\);
* Randomly change the machine assignment of one randomly selected job in \(AMJ\);
* Randomly change the resource assignment of one randomly selected job in \(AMJ\). Once a neighbor \(S^{\prime\prime}\) is generated, it is accepted as the new solution and replaces \(S^{\prime}\) if it is better or if a randomly selected value between 0 and 1 is lower than \(e^{\frac{Cat(S^{\prime})^{\mathsf{T}}\cdot Cat(S^{\prime})}{T}}\) (lines 7 and 8). Otherwise, the same solution \(S^{\prime}\) will be used during the next iteration. The \(AcceptRate\) and \(LamRate\) parameters correspond to the modified LAM annealing schedule from [36], which the interested reader is referred to for further insight. Briefly speaking, this annealing schedule adapts the temperature so that the acceptance rate linearly decreases from 100% to 44% during the first 15% iterations of the algorithm, then fixes it at 44% during the following 50% iterations, while, for the remaining 35%, it drops linearly towards 0%. ## 4 Empirical Validation

In order to validate the algorithmic approaches for solving the presented problem, we devised a series of experiments. ### Benchmark Generation

For a given problem size (\(n\), \(m\), and \(k\) are known), we built 20 instances where the problem parameters are generated as integer values using the following rules:

* \(p_{j}\sim U(1000,10,000)\), \(\forall j\in 1\ldots n\);
* \(pc_{j}=\alpha\cdot p_{j},\forall j\in 1\ldots n\), where \(\alpha\sim U(0.1,0.5)\);
* \(fc_{j}=\beta\cdot(p_{j}-pc_{j}),\forall j\in 1\ldots n\), where \(\beta\sim U(0.2,0.5)\);
* \(d_{j}\sim U(50,200),\forall j\in 1\ldots n\);
* \(d_{j}=\gamma\cdot d_{j},\forall j\in 1\ldots n\), where \(\gamma\sim U(1,1.2)\);
* \(tc_{j}\sim U(1,10),\forall j\in 1\ldots n\);
* \(rcm_{i}\sim U(10,50),\forall i\in 1\ldots m\);
* \(mwtm_{i}\sim U(10,100),\forall i\in 1\ldots m\);
* \(l_{r}\sim U(1,5),\forall r\in 1\ldots k\);
* \(rcr_{r}\sim U(10,50),\forall r\in 1\ldots k\);
* \(trtr_{r}=\delta\cdot trcr_{r}\), where \(\delta\sim U(1.0,0.3),\forall r\in 1\ldots k\);
* \(t_{ij}\sim U(5,50),\forall j\in 1\ldots n,\forall i\in 1\ldots m\);
* \(rcj_{ij}\sim U(10,50),\forall j\in 1\ldots n,\forall i\in 1\ldots m\);
* \(rtrl_{ij}=\theta\cdot trcl_{ij}\), where \(\theta\sim U(0.1,0.3),\forall j\in 1\ldots n,\forall i\in 1\ldots m\);\(a_{jr}\sim U(0,1),\forall j\in 1\ldots n,\forall r\in 1\ldots k\). When generating parameter \(a\), we made sure that each resource type \(r\) is required by at least one job. ### Experiments and Results

We present below the results from several numerical experiments using the exact and approximate approaches for solving the proposed scheduling problem. The experiments were conducted on an Intel Xeon Gold CPU with 80 cores at 2.00 GHz, and with 64 Gb RAM. All algorithms were implemented in julia 1.6.1 [37]. The MILP approach used the JuMP package and the the Gurobi 9.0.1 solver [38]. It was also allowed to use up to 16 cores and as much as 32 GB RAM, whereas, when executing each heuristic approach, we only used a single core. We considered problem instances containing between 10 and 50 jobs (\(n\)), 10 and 20 machines (\(m\)), and 5 resource types (\(k\)). A total of 20 instances of each size were generated (all instances are available at github.com/aolteanu/UPMSP-NAJ-NAM-RR, accessed on 15 November 2022.) and tested, and the execution times were limited to 3600 seconds. We begin by reporting the average gap and its standard deviation for all approaches in Table 10. The gap is given here by \(\frac{best-actual}{best}\), where \(actual\) is the objective value given by one algorithm execution on one problem instance, and \(best\) is the best objective value found by any algorithm on that problem instance. The best average values are indicated in bold face.