## 3 Resolution Approaches
### Approximate Approaches
#### 3.2.3 Simulated Annealing  
We consider a third heuristic for solving this problem: the simulated annealing procedure [35]. This approach starts from an initial solution and then moves to close neighbors across multiple iterations. During each iteration, the neighboring solution replaces the current one if it improves the objective function. Non-improving solutions may also replace the previous solution with a probability that is proportional to the performance difference and taking into account a temperature parameter. This parameters is initially set to a high value and decreases at each iteration. High values increase the probability of accepting non-improving solutions, and low values do not. Therefore, the approach starts by exploring the search space and ends by intensifying its search. The performance of the simulated annealing approach is heavily dependent on the choice of the initial temperature and the rate at which it decreases, also called an annealing schedule. Usually, the annealing schedule requires a significantly time-consuming tuning phase in order for the approach to perform well on a new problem. Variants of this approach, where the annealing schedule adapts and requires no tuning, have been proposed, and we therefore consider one such approach here. Namely, we focus on the adaptive annealing schedule known as modified LAM [36]. This adaptive simulated annealing (ASA) using the modified LAM annealing schedule is outlined in Algorithm 2. ```
1\(S\leftarrow\mathit{GenerateInitialSolution}()\)
2\(S^{\prime}\gets S\)
3\(T\gets 0.5\)
4\(\mathit{AcceptRate}\leftarrow\frac{1}{500}(499\cdot\mathit{AcceptRate}+1)\)
5 forit\(\in 1\dots\mathit{iterations}\)do
6\(S^{\prime\prime}\leftarrow\mathit{PickNeighbor}(S^{\prime})\)
7 if\(\mathit{Cost}(S^{\prime\prime})>\mathit{Cost}(S^{\prime})\) or \(\mathit{Random}(0,1)<e^{\frac{\mathit{Cost}(S^{\prime\prime})\cdot\mathit{Cost }(S^{\prime})}{t}}\)then
8\(S^{\prime}\gets S^{\prime\prime}\)
9\(\mathit{AcceptRate}\leftarrow\frac{1}{500}(499\cdot\mathit{AcceptRate}+1)\)
10 else
11\(\mathit{AcceptRate}\leftarrow\frac{1}{500}(499\cdot\mathit{AcceptRate})\)
12 if\(\frac{it}{\mathit{iterations}}<0.15\)then
13\(\mathit{LamRate}\leftarrow 0.44+0.56\cdot 560^{-it/iterations}/0.15\)
14 else
15\(\mathit{LamRate}\leftarrow 0.44+0.54\cdot 440^{-(it/iterations}\cdot 0.65)/0.35\)
16 if\(\mathit{AcceptRate}>\mathit{LamRate}\)then
17\(T\leftarrow 0.999\cdot T\)
18 else
19\(T\gets T/0.999\)
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
39
39
40
410
42
43
44
44
45
46
47
48
491
492
40
40
42
493
44
45
494
46
47
488
495
496
497
498
499
50
510
520
530
540
521
541
552
56
571
582
599
60
531
542
543
555
564
572
583
590
591
592
50
504
505
565
573
584
595
596
597
598
599
610
500
511
502
503
512
513
514
515
516
517
518
519
522
532
543
544
555
566
574
575
588
598
599
620
593
5 The algorithm starts by initializing the solution \(S\) using the greedy constructive heuristic presented in Section 3.2.1 (line 1). A copy is also generated in the form of \(S^{\prime}\) (line 2). The temperature parameter \(T\) and an \(AcceptRate\) parameter are both set to 0.5 (lines 3 and 4). Throughout this algorithm, a solution of the problem is encoded using:

* _ordj:_ the sequence of jobs;
* _AMJ_: the assignment of machines to jobs;
* _ARJ_: the assignment of resources to jobs. For the initial solution, these elements correspond to those used by the constructive heuristic from Section 3.2.1. In order to evaluate a solution, a decoding function that generates all of the elements of the solution (\(ST\)), \(FT\)), \(STM\), \(FTM\), \(STR\), \(FTR\), \(AMJ\), \(AR\)) is used; however, for simplicity, we do not include these elements in the presentation of the algorithm. Initial values for the temperature and the acceptance rate are also set at this point. We continue with the main loop of the algorithm (line 5 onward), which performs a preset number of iterations. Each iteration begins by generating a neighbor of solution \(S^{\prime}\).